Constrained expressions and their derivatives
From MaRDI portal
(Redirected from Publication:4589251)
Abstract: This paper proposes an extension to classical regular expressions by the addition of two operators allowing the inclusion of boolean formulae from the zeroth order logic. These expressions are called constrained expressions. The associated language is defined thanks to the notion of interpretation and of realization. We show that the language associated when both interpretation and realization are fixed is stricly regular and can be not regular otherwise. Furthermore, we use an extension of Antimirov partial derivatives in order to solve the membership test in the general case. Finally, we show that once the interpretation is fixed, the membership test of a word in the language denoted by a constrained expression can be undecidable whereas it is always decidable when the interpretation is not fixed.
Recommendations
- The membership problem for regular expressions with unordered concatenation and numerical constraints
- Regular Expressions with Numerical Constraints and Automata with Counters
- Symbolic solving of extended regular expression inequalities
- STACS 2004
- Partial derivatives of an extended regular expression
Cited in
(4)
This page was built for publication: Constrained expressions and their derivatives
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4589251)
