Standard

Homomorphisms on Graph-Walking Automata. / Martynova, Olga; Okhotin, Alexander.

Implementation and Application of Automata - 26th International Conference, CIAA 2022, Proceedings. ed. / Pascal Caron; Ludovic Mignot. Springer Nature, 2022. p. 177-188 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13266 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review

Harvard

Martynova, O & Okhotin, A 2022, Homomorphisms on Graph-Walking Automata. in P Caron & L Mignot (eds), Implementation and Application of Automata - 26th International Conference, CIAA 2022, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13266 LNCS, Springer Nature, pp. 177-188, 26th International Conference on Implementation and Application of Automata, CIAA 2022, Rouen, France, 28/06/22. https://doi.org/10.1007/978-3-031-07469-1_14

APA

Martynova, O., & Okhotin, A. (2022). Homomorphisms on Graph-Walking Automata. In P. Caron, & L. Mignot (Eds.), Implementation and Application of Automata - 26th International Conference, CIAA 2022, Proceedings (pp. 177-188). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13266 LNCS). Springer Nature. https://doi.org/10.1007/978-3-031-07469-1_14

Vancouver

Martynova O, Okhotin A. Homomorphisms on Graph-Walking Automata. In Caron P, Mignot L, editors, Implementation and Application of Automata - 26th International Conference, CIAA 2022, Proceedings. Springer Nature. 2022. p. 177-188. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-031-07469-1_14

Author

Martynova, Olga ; Okhotin, Alexander. / Homomorphisms on Graph-Walking Automata. Implementation and Application of Automata - 26th International Conference, CIAA 2022, Proceedings. editor / Pascal Caron ; Ludovic Mignot. Springer Nature, 2022. pp. 177-188 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{fbcb37380a92444598e9d3f8648571a0,
title = "Homomorphisms on Graph-Walking Automata",
abstract = "Graph-walking automata (GWA) analyze an input graph by moving between its nodes, following the edges. This paper investigates the effect of node-replacement graph homomorphisms on recognizability by these automata. The family of graph languages recognized by GWA is closed under inverse homomorphisms. The main result of this paper is that, for n-state automata operating on graphs with k labels of edge end-points, the inverse homomorphic images require GWA with kn+ O(1 ) states in the worst case. The second result is that already for tree-walking automata, the family they recognize is not closed under injective homomorphisms; here the proof is based on a homomorphic characterization of regular tree languages.",
author = "Olga Martynova and Alexander Okhotin",
note = "Publisher Copyright: {\textcopyright} 2022, Springer Nature Switzerland AG.; 26th International Conference on Implementation and Application of Automata, CIAA 2022 ; Conference date: 28-06-2022 Through 01-07-2022",
year = "2022",
month = jun,
doi = "10.1007/978-3-031-07469-1_14",
language = "English",
isbn = "9783031074684",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Nature",
pages = "177--188",
editor = "Pascal Caron and Ludovic Mignot",
booktitle = "Implementation and Application of Automata - 26th International Conference, CIAA 2022, Proceedings",
address = "Germany",

}

RIS

TY - GEN

T1 - Homomorphisms on Graph-Walking Automata

AU - Martynova, Olga

AU - Okhotin, Alexander

N1 - Publisher Copyright: © 2022, Springer Nature Switzerland AG.

PY - 2022/6

Y1 - 2022/6

N2 - Graph-walking automata (GWA) analyze an input graph by moving between its nodes, following the edges. This paper investigates the effect of node-replacement graph homomorphisms on recognizability by these automata. The family of graph languages recognized by GWA is closed under inverse homomorphisms. The main result of this paper is that, for n-state automata operating on graphs with k labels of edge end-points, the inverse homomorphic images require GWA with kn+ O(1 ) states in the worst case. The second result is that already for tree-walking automata, the family they recognize is not closed under injective homomorphisms; here the proof is based on a homomorphic characterization of regular tree languages.

AB - Graph-walking automata (GWA) analyze an input graph by moving between its nodes, following the edges. This paper investigates the effect of node-replacement graph homomorphisms on recognizability by these automata. The family of graph languages recognized by GWA is closed under inverse homomorphisms. The main result of this paper is that, for n-state automata operating on graphs with k labels of edge end-points, the inverse homomorphic images require GWA with kn+ O(1 ) states in the worst case. The second result is that already for tree-walking automata, the family they recognize is not closed under injective homomorphisms; here the proof is based on a homomorphic characterization of regular tree languages.

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

UR - https://www.mendeley.com/catalogue/6d5098cc-da51-3181-93ec-90f86b6115e4/

U2 - 10.1007/978-3-031-07469-1_14

DO - 10.1007/978-3-031-07469-1_14

M3 - Conference contribution

AN - SCOPUS:85131947794

SN - 9783031074684

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 177

EP - 188

BT - Implementation and Application of Automata - 26th International Conference, CIAA 2022, Proceedings

A2 - Caron, Pascal

A2 - Mignot, Ludovic

PB - Springer Nature

T2 - 26th International Conference on Implementation and Application of Automata, CIAA 2022

Y2 - 28 June 2022 through 1 July 2022

ER -

ID: 96946270