Here's a link to the paper and the implementation.

This is the substantially revised and almost completely re-written (paper and implementation) version of our earlier draft.

skip to main |
skip to sidebar
## Friday, 8 June 2012

###
Regular Expression Sub-Matching using Partial Derivatives

## Monday, 4 June 2012

###
Constructive Finite Trace Analysis with Linear Temporal Logic

## Labels

Regular expression sub-matching is the problem of finding for
each sub-part of a regular expression a matching sub-string.
Prior work applies Thompson and Glushkov NFA methods for the construction
of the matching automata. We propose the novel use of derivatives and
partial derivatives for regular expression sub-matching.
Our benchmarking results show that the run-time performance is promising
and that our approach can be applied in practice.

Here's a link to the paper and the implementation.

This is the substantially revised and almost completely re-written (paper and implementation) version of our earlier draft.

Labels:
haskell,
partial derivatives,
regular expressions

We consider linear temporal logic (LTL) for run-time testing
over limited time periods. The technical challenge
is to check if the finite trace produced by the system
under test matches the LTL property.
We present a constructive solution to this problem.
Our finite trace LTL matching algorithm
yields a proof explaining why a match exists.
We apply our constructive LTL matching
method to check if LTL properties are sufficiently covered
by traces resulting from tests.

The paper appeared in TAP'12. Here's a link to the paper and the talk.

The system has been implemented in Haskell and is applied in some real-world projects. Some of the Haskell source code will be made publicly available (later in the year).

Subscribe to:
Posts (Atom)

- actor
- boosting
- communicating FA
- concurrency
- constraint handling rules
- control
- coordination
- dsl
- erlang
- formal methods
- guards
- haskell
- join
- join pattern
- library
- linear temporal logic
- model-checking
- multi-set rewrite rules
- parallelism
- partial derivatives
- partial evaluation
- proofs are programs
- regular expressions
- software transactional memory
- types
- uppaal