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

DOI10.1142/S012905411740007XzbMath1380.68252MaRDI QIDQ4605514

Akio Fujiyoshi

Publication date: 22 February 2018

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

zbMATH Keywords

bounded tree-widthuniform membership problemspanning tree automaton

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Unnamed Item
• Algorithmic meta-theorems for restrictions of treewidth
• The complexity of first-order and monadic second-order logic revisited
• Recognition of directed acyclic graphs by spanning tree automata
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• A Practical Algorithm for the Uniform Membership Problem of Labeled Multidigraphs of Tree-Width 2 for Spanning Tree Automata
• Recognition of Labeled Multidigraphs by Spanning Tree Automata
• Easy problems for tree-decomposable graphs
• Recognition of a Spanning Tree of Directed Acyclic Graphs by Tree Automata
• Characterization and Recognition of Partial 3-Trees
• Verification of Mathematical Formulae Based on a Combination of Context-Free Grammar and Tree Grammar

This page was built for publication: A Practical Algorithm for the Uniform Membership Problem of Labeled Multidigraphs of Tree-Width 2 for Spanning Tree Automata