Partial Derivative Automaton for Regular Expressions with Shuffle
From MaRDI portal
Abstract: We generalize the partial derivative automaton to regular expressions with shuffle and study its size in the worst and in the average case. The number of states of the partial derivative automata is in the worst case at most 2^m, where m is the number of letters in the expression, while asymptotically and on average it is no more than (4/3)^m.
Recommendations
- Automata for regular expressions with shuffle
- Partial derivative automaton by compressing regular expressions
- Partial derivatives of regular expressions and finite automaton constructions
- Partial derivatives of regular expressions and finite automata constructions
- Derivatives and partial derivatives for regular shuffle expressions
- Derivatives for regular shuffle expressions
- Extending regular expressions with iterated shuffle
- On the state complexity of partial derivative automata for regular expressions with intersection
- Location based automata for expressions with shuffle
- Shuffle decomposition of regular languages
Cited in
(9)- Automata for regular expressions with shuffle
- On the size of partial derivatives and the word membership problem
- Derivatives and partial derivatives for regular shuffle expressions
- Location automata for synchronised shuffle expressions
- Derivatives for regular shuffle expressions
- On the state complexity of partial derivative automata for regular expressions with intersection
- Deciding synchronous Kleene algebra with derivatives
- Partial derivatives for context-free languages. From -regular expressions to pushdown automata
- Reordering Derivatives of Trace Closures of Regular Languages.
This page was built for publication: Partial Derivative Automaton for Regular Expressions with Shuffle
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5500676)
