Anzeige
Erschienen in:
2014 | OriginalPaper | Buchkapitel
Recognition of Labeled Multidigraphs by Spanning Tree Automata
verfasst von : Akio Fujiyoshi
Erschienen in: Implementation and Application of Automata
Verlag: Springer International Publishing
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In this paper, we study tree automata recognizing labeled multidigraphs. We define that a labeled multidigraph is accepted by a tree automaton if and only if the graph has a spanning tree accepted by the tree automaton. We call this automaton a spanning tree automaton. The membership problem of labeled multidigraphs for a spanning tree automaton is NP-complete because the Hamiltonian path problem can be easily reduced to it. However, it will be shown that the membership problem is solvable in linear time for graphs of bounded tree-width.