A Practical Algorithm for the Uniform Membership Problem of Labeled Multidigraphs of Tree-Width 2 for Spanning Tree Automata
| Autor: | Akio Fujiyoshi |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Discrete mathematics
Spanning tree Membership problem Computer science 0102 computer and information sciences 02 engineering and technology 01 natural sciences Automaton Treewidth 010201 computation theory & mathematics Bounded function 0202 electrical engineering electronic engineering information engineering Computer Science (miscellaneous) Practical algorithm 020201 artificial intelligence & image processing Tree automaton |
| Zdroj: | International Journal of Foundations of Computer Science. 28:563-581 |
| ISSN: | 1793-6373 0129-0541 |
| DOI: | 10.1142/s012905411740007x |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|