Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
The paper estimates the number of states in an unambiguous finite automaton (UFA) that is sufficient and in the worst case necessary to simulate an n-state two-way deterministic finite automaton (2DFA). It is proved that a 2DFA with n states can be transformed to a UFA with fewer than 2n· n! states. On the other hand, for every n, there is a language recognized by an n-state 2DFA that requires a UFA with at least Ω((42)n·n-1/2) states. The latter result is proved by estimating the rank of a certain matrix.
| Original language | English |
|---|---|
| Title of host publication | Language and Automata Theory and Applications - 15th International Conference, LATA 2021, Proceedings |
| Editors | Alberto Leporati, Carlos Martín-Vide, Dana Shapira, Claudio Zandron |
| Publisher | Springer Nature |
| Pages | 81-93 |
| Number of pages | 13 |
| ISBN (Print) | 9783030681944 |
| DOIs | |
| State | Published - Feb 2021 |
| Event | 15th International Conference on Language and Automata Theory and Applications, LATA 2021 - Milan, Italy Duration: 1 Mar 2021 → 5 Mar 2021 |
| Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| Volume | 12638 LNCS |
| ISSN (Print) | 0302-9743 |
| ISSN (Electronic) | 1611-3349 |
| Conference | 15th International Conference on Language and Automata Theory and Applications, LATA 2021 |
|---|---|
| Country/Territory | Italy |
| City | Milan |
| Period | 1/03/21 → 5/03/21 |
ID: 78911685