Name
Abstract | ||
|---|---|---|
We investigate the state size of DFAs accepting the shuffle of two words. We provide words u and v, such that the minimal DFA for u (sic) v requires an exponential number of states. We also show some conditions for the words u and v which ensure a quadratic upper bound on the state size of u v. Moreover, switching only two letters within one of u or v is enough to trigger the change from quadratic to exponential. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.4204/EPTCS.3.7 | ELECTRONIC PROCEEDINGS IN THEORETICAL COMPUTER SCIENCE |
Keywords | Field | DocType |
formal language,discrete mathematics,automata theory,upper bound | Discrete mathematics,Exponential function,Upper and lower bounds,Automaton,Quadratic equation,Mathematics | Journal |
Volume | Issue | ISSN |
3 | 3 | 2075-2180 |
Citations | PageRank | References |
2 | 0.37 | 6 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Franziska Biegler | 1 | 44 | 5.06 |
| Mark Daley | 2 | 166 | 22.18 |
| Ian McQuillan | 3 | 97 | 24.72 |