Graph-Walking Automata: From Whence They Come, and Whither They are Bound

Alexander Okhotin

doi:10.1007/978-3-030-23679-3_2

Graph-Walking Automata: From Whence They Come, and Whither They are Bound

Alexander Okhotin

Факультет математико-механический

Research output › › peer-review

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 Nature
Pages	10-29
Number of pages	20
ISBN (Print)	9783030236786
DOIs	https://doi.org/10.1007/978-3-030-23679-3_2
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

Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-030-23679-3_2

http://www.scopus.com/inward/record.url?scp=85069478519&partnerID=8YFLogxK

Fingerprint Dive into the research topics of 'Graph-Walking Automata: From Whence They Come, and Whither They are Bound'. Together they form a unique fingerprint.

Cite this

Okhotin, A. (2019). Graph-Walking Automata: From Whence They Come, and Whither They are Bound. In M. Hospodár, & G. Jirásková (Eds.), Implementation and Application of Automata - 24th International Conference, CIAA 2019, Proceedings (pp. 10-29). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11601 LNCS). Springer Nature. https://doi.org/10.1007/978-3-030-23679-3_2

Okhotin, Alexander. / Graph-Walking Automata: From Whence They Come, and Whither They are Bound. Implementation and Application of Automata - 24th International Conference, CIAA 2019, Proceedings. editor / Michal Hospodár ; Galina Jirásková. Springer Nature, 2019. pp. 10-29 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{934ab9945d4245248a25b8cf172faaa5,

title = "Graph-Walking Automata: From Whence They Come, and Whither They are Bound",

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.",

author = "Alexander Okhotin",

year = "2019",

month = jul,

day = "1",

doi = "10.1007/978-3-030-23679-3_2",

language = "English",

isbn = "9783030236786",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Nature",

pages = "10--29",

editor = "Michal Hospod{\'a}r and Galina Jir{\'a}skov{\'a}",

booktitle = "Implementation and Application of Automata - 24th International Conference, CIAA 2019, Proceedings",

address = "Germany",

note = "24th International Conference on Implementation and Application of Automata, CIAA 2019 ; Conference date: 22-07-2019 Through 25-07-2019",

}

Okhotin, A 2019, Graph-Walking Automata: From Whence They Come, and Whither They are Bound. in M Hospodár & G Jirásková (eds), Implementation and Application of Automata - 24th International Conference, CIAA 2019, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11601 LNCS, Springer Nature, pp. 10-29, 24th International Conference on Implementation and Application of Automata, CIAA 2019, Košice, 22/07/19. https://doi.org/10.1007/978-3-030-23679-3_2

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 Nature, 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 › › peer-review

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 Nature

T2 - 24th International Conference on Implementation and Application of Automata, CIAA 2019

Y2 - 22 July 2019 through 25 July 2019

ER -

Okhotin A. Graph-Walking Automata: From Whence They Come, and Whither They are Bound. In Hospodár M, Jirásková G, editors, Implementation and Application of Automata - 24th International Conference, CIAA 2019, Proceedings. Springer Nature. 2019. p. 10-29. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-030-23679-3_2