Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
It is shown that a two-way deterministic finite automaton (2DFA) with n states over an alphabet Σ can be transformed to an equivalent one-way automaton (1DFA) with | Σ| · F(n) + 1 states, where F(n)=maxk=0nkn-k+1≤(n+1)n+1/(ln(n+1)·e1-o(1))n+1. This reflects the fact that, by keeping the last processed symbol in memory, the simulating 1DFA needs to remember only the state from which the 2DFA leaves the prefix read so far for the first time to the right together with a function that maps some n- k states moving to the left from the last processed symbol to some other k states moving to the right from this symbol. This reduces the number of functions describing the behaviour of the 2DFA on the prefix read so far. A close lower bound of F(n) states is established using a 5-symbol alphabet. The complexity of transforming a sweeping or a direction-determinate 2DFA to a 1DFA is shown to be exactly F(n).
| Original language | English |
|---|---|
| Title of host publication | Descriptional Complexity of Formal Systems - 23rd IFIP WG 1.02 International Conference, DCFS 2021, Proceedings |
| Editors | Yo-Sub Han, Sang-Ki Ko |
| Publisher | Springer Nature |
| Pages | 26-37 |
| Number of pages | 12 |
| ISBN (Print) | 9783030934880 |
| DOIs | |
| State | Published - 30 Dec 2021 |
| Event | 23rd IFIP WG 1.02 International Conference on Descriptional Complexity of Format Systems, DCFS 2021 - Virtual, Online Duration: 5 Sep 2021 → 5 Sep 2021 |
| Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| Volume | 13037 LNCS |
| ISSN (Print) | 0302-9743 |
| ISSN (Electronic) | 1611-3349 |
| Conference | 23rd IFIP WG 1.02 International Conference on Descriptional Complexity of Format Systems, DCFS 2021 |
|---|---|
| City | Virtual, Online |
| Period | 5/09/21 → 5/09/21 |
ID: 91382899