Recognition of directed acyclic graphs by spanning tree automata

DOI10.1016/j.tcs.2010.06.006zbMath1207.68185OpenAlexW2038955206MaRDI QIDQ1959657

Akio Fujiyoshi

Publication date: 7 October 2010

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2010.06.006

zbMATH Keywords

NP-completenessdirected acyclic graphspanning treeseries-parallel graphtree automatongeneralized series-parallel graph

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10)

Related Items (2)

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

Cites Work

• The complexity of tree automata and XPath on grammar-compressed trees
• Closure properties and decision problems of dag automata
• A partial k-arboretum of graphs with bounded treewidth
• Combinatorial algorithms on a class of graphs
• Recognition of a Spanning Tree of Directed Acyclic Graphs by Tree Automata
• Linear-time computability of combinatorial problems on series-parallel graphs
• Verification of Mathematical Formulae Based on a Combination of Context-Free Grammar and Tree Grammar
• Implementation and Application of Automata

This page was built for publication: Recognition of directed acyclic graphs by spanning tree automata