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

Research outputpeer-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 languageEnglish
Title of host publicationImplementation and Application of Automata - 24th International Conference, CIAA 2019, Proceedings
EditorsMichal Hospodár, Galina Jirásková
PublisherSpringer Nature
Pages10-29
Number of pages20
ISBN (Print)9783030236786
DOIs
Publication statusPublished - 1 Jul 2019
Event24th International Conference on Implementation and Application of Automata, CIAA 2019 - Košice
Duration: 22 Jul 201925 Jul 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11601 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference24th International Conference on Implementation and Application of Automata, CIAA 2019
CountrySlovakia
CityKošice
Period22/07/1925/07/19

Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

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