Input-Erasing Two-Way Finite Automata
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910901787951104 |
|---|---|
| author | Meduna, Alexander Nejedlý, Dominik Křivka, Zbyněk |
| author_facet | Meduna, Alexander Nejedlý, Dominik Křivka, Zbyněk |
| contents | The present paper introduces and studies an alternative concept of two-way finite automata called input-erasing two-way finite automata. Like the original model, these new automata can also move the reading head freely left or right on the input tape. However, each time they read a symbol, they also erase it from the tape. The paper demonstrates that these automata define precisely the family of linear languages and are thus strictly stronger than the original ones. Furthermore, it introduces a variety of restrictions placed upon these automata and the way they work and investigates the effect of these restrictions on their acceptance power. In particular, it explores the mutual relations of language families resulting from some of these restrictions and shows that some of them reduce the power of these automata to that of even linear grammars or even ordinary finite automata. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_01720 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Input-Erasing Two-Way Finite Automata Meduna, Alexander Nejedlý, Dominik Křivka, Zbyněk Formal Languages and Automata Theory 68Q45 F.4.3; F.1.1 The present paper introduces and studies an alternative concept of two-way finite automata called input-erasing two-way finite automata. Like the original model, these new automata can also move the reading head freely left or right on the input tape. However, each time they read a symbol, they also erase it from the tape. The paper demonstrates that these automata define precisely the family of linear languages and are thus strictly stronger than the original ones. Furthermore, it introduces a variety of restrictions placed upon these automata and the way they work and investigates the effect of these restrictions on their acceptance power. In particular, it explores the mutual relations of language families resulting from some of these restrictions and shows that some of them reduce the power of these automata to that of even linear grammars or even ordinary finite automata. |
| title | Input-Erasing Two-Way Finite Automata |
| topic | Formal Languages and Automata Theory 68Q45 F.4.3; F.1.1 |
| url | https://arxiv.org/abs/2504.01720 |