论文标题
图形步行自动机的空虚问题和带有星形子图的瓷砖的复杂性
Complexity of the emptiness problem for graph-walking automata and for tilings with star subgraphs
论文作者
论文摘要
本文证明了两个识别图形的模型的空虚问题的可决定性：图形步行自动机和Star Subgraphs（Star Automata）的图形瓷砖。此外，事实证明，图形步行自动机的非空性问题（也就是说，给定的自动机是否至少接受一个图）是NEXP complete。对于将非确定树自动机推广到图形的Star Automata而言，证明其非空性问题是NP完整的。
This paper proves the decidability of the emptiness problem for two models which recognize 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.
