A hierarchy of reversible finite automata
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912130111897600 |
|---|---|
| author | Radionova, Maria Okhotin, Alexander |
| author_facet | Radionova, Maria Okhotin, Alexander |
| contents | In this paper, different variants of reversible finite automata are compared, and their hierarchy by the expressive power is established. It is shown that one-way reversible automata with multiple initial states (MRFA) recognize strictly more languages than sweeping reversible automata (sRFA), which are in turn stronger than one-way reversible automata with a single initial state (1RFA). The latter recognize strictly more languages than one-way permutation automata (1PerFA). It is also shown that the hierarchy of sRFA by the number of passes over the input string collapses: it turns out that three passes are always enough. On the other hand, MRFA form a hierarchy by the number of initial states: their subclass with at most $k$ initial states (MRFA$^k$) recognize strictly fewer languages than MRFA$^{k + 1}$, and also MRFA$^k$ are incomparable with sRFA. In the unary case, sRFA, MRFA$^k$ and MRFA become equal in their expressive power, and the inclusion of 1RFA into sRFA remains proper. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_14538 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A hierarchy of reversible finite automata Radionova, Maria Okhotin, Alexander Formal Languages and Automata Theory 68Q45 In this paper, different variants of reversible finite automata are compared, and their hierarchy by the expressive power is established. It is shown that one-way reversible automata with multiple initial states (MRFA) recognize strictly more languages than sweeping reversible automata (sRFA), which are in turn stronger than one-way reversible automata with a single initial state (1RFA). The latter recognize strictly more languages than one-way permutation automata (1PerFA). It is also shown that the hierarchy of sRFA by the number of passes over the input string collapses: it turns out that three passes are always enough. On the other hand, MRFA form a hierarchy by the number of initial states: their subclass with at most $k$ initial states (MRFA$^k$) recognize strictly fewer languages than MRFA$^{k + 1}$, and also MRFA$^k$ are incomparable with sRFA. In the unary case, sRFA, MRFA$^k$ and MRFA become equal in their expressive power, and the inclusion of 1RFA into sRFA remains proper. |
| title | A hierarchy of reversible finite automata |
| topic | Formal Languages and Automata Theory 68Q45 |
| url | https://arxiv.org/abs/2411.14538 |