Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
Complexity of the emptiness problem for graph-walking automata and for tilings with star subgraphs. / Мартынова, Ольга Максимовна.
в: Information and Computation, Том 296, 105127, 01.2024.Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
}
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