Reversible Limited Automata
| Autor: | Martin Kutrib, Matthias Wendlandt |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Discrete mathematics
Algebra and Number Theory Linear bounded automaton 0102 computer and information sciences 02 engineering and technology ω-automaton Nonlinear Sciences::Cellular Automata and Lattice Gases 01 natural sciences Cellular automaton Theoretical Computer Science Mobile automaton Combinatorics Computational Theory and Mathematics Regular language 010201 computation theory & mathematics Continuous spatial automaton 0202 electrical engineering electronic engineering information engineering Computer Science::Programming Languages Automata theory Quantum finite automata 020201 artificial intelligence & image processing Computer Science::Formal Languages and Automata Theory Information Systems Mathematics |
| Zdroj: | Fundamenta Informaticae. 155:31-58 |
| ISSN: | 1875-8681 0169-2968 |
| DOI: | 10.3233/fi-2017-1575 |
| Popis: | A k-limited automaton is a linear bounded automaton that may rewrite each tape square only in the first k visits, where \(k\ge 0\) is a fixed constant. It is known that these automata accept context-free languages only. We investigate deterministic k-limited automata towards their ability to perform reversible computations, that is, computations in which every configuration has at most one predecessor. A first result is that, for all \(k\ge 0\), sweeping k-limited automata accept regular languages only. In contrast to reversible finite automata, all regular languages are accepted by sweeping 0-limited automata. Then we study the computational power gained in the number k of possible rewrite operations. It is shown that the reversible 2-limited automata accept regular languages only and, thus, are strictly weaker than general 2-limited automata. Furthermore, a proper inclusion between reversible 3-limited and 4-limited automata languages is obtained. The next levels of the hierarchy are separated between every k and \(k+3\) rewrite operations. Finally, it turns out that all k-limited automata accept Church-Rosser languages only, that is, the intersection between context-free and Church-Rosser languages contains an infinite hierarchy of language families beyond the deterministic context-free languages. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|