Abstract
Graph-walking automata are finite automata walking on graphs given as an input; tree-walking automata and two-way finite automata are their well-known special cases. Graph-walking automata can be regarded both as a model of navigation in an unknown environment, and as a generic computing device, with the graph as the model of its memory. This paper presents the known results on these automata, ranging from their limitations in traversing graphs, studied already in the 1970s, to the recent work on the logical reversibility of their computations.
| Original language | English |
|---|---|
| Title of host publication | Implementation and Application of Automata - 24th International Conference, CIAA 2019, Proceedings |
| Editors | Michal Hospodár, Galina Jirásková |
| Publisher | Springer |
| Pages | 10-29 |
| Number of pages | 20 |
| ISBN (Print) | 9783030236786 |
| DOIs | |
| Publication status | Published - 1 Jul 2019 |
| Event | 24th International Conference on Implementation and Application of Automata, CIAA 2019 - Košice Duration: 22 Jul 2019 → 25 Jul 2019 |
Publication series
| Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| Volume | 11601 LNCS |
| ISSN (Print) | 0302-9743 |
| ISSN (Electronic) | 1611-3349 |
Conference
| Conference | 24th International Conference on Implementation and Application of Automata, CIAA 2019 |
|---|---|
| Country | Slovakia |
| City | Košice |
| Period | 22/07/19 → 25/07/19 |
Fingerprint
Scopus subject areas
- Theoretical Computer Science
- Computer Science(all)
Cite this
}
Graph-Walking Automata: From Whence They Come, and Whither They are Bound. / Okhotin, Alexander.
Implementation and Application of Automata - 24th International Conference, CIAA 2019, Proceedings. ed. / Michal Hospodár; Galina Jirásková. Springer, 2019. p. 10-29 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11601 LNCS).Research output
TY - GEN
T1 - Graph-Walking Automata: From Whence They Come, and Whither They are Bound
AU - Okhotin, Alexander
PY - 2019/7/1
Y1 - 2019/7/1
N2 - Graph-walking automata are finite automata walking on graphs given as an input; tree-walking automata and two-way finite automata are their well-known special cases. Graph-walking automata can be regarded both as a model of navigation in an unknown environment, and as a generic computing device, with the graph as the model of its memory. This paper presents the known results on these automata, ranging from their limitations in traversing graphs, studied already in the 1970s, to the recent work on the logical reversibility of their computations.
AB - Graph-walking automata are finite automata walking on graphs given as an input; tree-walking automata and two-way finite automata are their well-known special cases. Graph-walking automata can be regarded both as a model of navigation in an unknown environment, and as a generic computing device, with the graph as the model of its memory. This paper presents the known results on these automata, ranging from their limitations in traversing graphs, studied already in the 1970s, to the recent work on the logical reversibility of their computations.
UR - http://www.scopus.com/inward/record.url?scp=85069478519&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-23679-3_2
DO - 10.1007/978-3-030-23679-3_2
M3 - Conference contribution
AN - SCOPUS:85069478519
SN - 9783030236786
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 10
EP - 29
BT - Implementation and Application of Automata - 24th International Conference, CIAA 2019, Proceedings
A2 - Hospodár, Michal
A2 - Jirásková, Galina
PB - Springer
ER -