Name
Abstract | ||
|---|---|---|
We generalize the partial derivative automaton and the position automaton to regular expressions with shuffle, and study their state complexity in the worst, as well as in the average case. The number of states of the partial derivative automaton (Apd) is, in the worst case, at most 2m, where m is the number of letters in the expression. The asymptotic average is bounded by (43)m. We define a position automaton (Apos) that is homogeneous, but in which several states can correspond to a same position, and we show that Apd is a quotient of Apos. The number of states of the position automaton is at most 1+m(2m−1), while the asymptotic average is no more than m(43)m. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1016/j.ic.2017.08.013 | Information and Computation |
Keywords | Field | DocType |
Regular expressions,Shuffle operation,Partial derivatives,Finite automata,Position automata,Average case,Analytic combinatorics | Discrete mathematics,Combinatorics,Continuous automaton,Deterministic automaton,Nondeterministic finite automaton,Reversible cellular automaton,Timed automaton,Mathematics,Probabilistic automaton,Büchi automaton,ω-automaton | Journal |
Volume | Issue | ISSN |
259 | Part | 0890-5401 |
Citations | PageRank | References |
2 | 0.37 | 10 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sabine Broda | 1 | 64 | 13.83 |
| António Machiavelo | 2 | 45 | 8.82 |
| Nelma Moreira | 3 | 180 | 33.98 |
| Rogério Reis | 4 | 140 | 25.74 |