Standard

Complexity of the emptiness problem for graph-walking automata and for tilings with star subgraphs. / Мартынова, Ольга Максимовна.

In: Information and Computation, Vol. 296, 105127, 01.2024.

Research output: Contribution to journal › Article › peer-review

Harvard

Мартынова, ОМ 2024, 'Complexity of the emptiness problem for graph-walking automata and for tilings with star subgraphs', Information and Computation, vol. 296, 105127. https://doi.org/10.1016/j.ic.2023.105127

APA

Мартынова, О. М. (2024). Complexity of the emptiness problem for graph-walking automata and for tilings with star subgraphs. Information and Computation, 296, [105127]. https://doi.org/10.1016/j.ic.2023.105127

Vancouver

Мартынова ОМ. Complexity of the emptiness problem for graph-walking automata and for tilings with star subgraphs. Information and Computation. 2024 Jan;296. 105127. https://doi.org/10.1016/j.ic.2023.105127

Author

Мартынова, Ольга Максимовна. / Complexity of the emptiness problem for graph-walking automata and for tilings with star subgraphs. In: Information and Computation. 2024 ; Vol. 296.

BibTeX

@article{41d57a1020b14e1d904f232e4119f4ff,
title = "Complexity of the emptiness problem for graph-walking automata and for tilings with star subgraphs",
abstract = "This paper proves the decidability of the emptiness problem for two models which recognize finite graphs: graph-walking automata, and tilings of graphs by star subgraphs (star automata). Furthermore, it is proved that the non-emptiness problem for graph-walking automata (that is, whether a given automaton accepts at least one graph) is NEXP-complete. For star automata, which generalize nondeterministic tree automata to the case of graphs, it is proved that their non-emptiness problem is NP-complete.",
author = "Мартынова, {Ольга Максимовна}",
year = "2024",
month = jan,
doi = "10.1016/j.ic.2023.105127",
language = "English",
volume = "296",
journal = "Information and Computation",
issn = "0890-5401",
publisher = "Elsevier",

}

RIS

TY - JOUR

T1 - Complexity of the emptiness problem for graph-walking automata and for tilings with star subgraphs

AU - Мартынова, Ольга Максимовна

PY - 2024/1

Y1 - 2024/1

N2 - This paper proves the decidability of the emptiness problem for two models which recognize finite graphs: graph-walking automata, and tilings of graphs by star subgraphs (star automata). Furthermore, it is proved that the non-emptiness problem for graph-walking automata (that is, whether a given automaton accepts at least one graph) is NEXP-complete. For star automata, which generalize nondeterministic tree automata to the case of graphs, it is proved that their non-emptiness problem is NP-complete.

AB - This paper proves the decidability of the emptiness problem for two models which recognize finite graphs: graph-walking automata, and tilings of graphs by star subgraphs (star automata). Furthermore, it is proved that the non-emptiness problem for graph-walking automata (that is, whether a given automaton accepts at least one graph) is NEXP-complete. For star automata, which generalize nondeterministic tree automata to the case of graphs, it is proved that their non-emptiness problem is NP-complete.

UR - https://www.mendeley.com/catalogue/1129697d-ae37-3c6b-b59f-cbeb46f604f1/

U2 - 10.1016/j.ic.2023.105127

DO - 10.1016/j.ic.2023.105127

M3 - Article

VL - 296

JO - Information and Computation

JF - Information and Computation

SN - 0890-5401

M1 - 105127

ER -

ID: 116607067