A Practical Algorithm for the Uniform Membership Problem of Labeled Multidigraphs of Tree-Width 2 for Spanning Tree Automata

摘要

This paper presents a practical algorithm for the uniform membership problem of labeled multidigraphs of tree-width at most 2 for spanning tree automata. Though the theoretical existence of a linear-time algorithm for the membership problem for graphs of bounded tree-width was shown in the previous study, the implementation of the linear-time algorithm is expected to be impractical because it requires the construction of a finite-state automaton whose size is super-exponential in the size of the tree automaton and the tree-width of graphs. In addition, the tree automaton itself should be a part of the input in practical situations.