Recognition of a Spanning Tree of Directed Acyclic Graphs by Tree Automata

DOI10.1007/978-3-642-02979-0_14MaRDI QIDQ3637347zbMATH OpenOpenAlexFDO

Authors Akio Fujiyoshi

Publication date 9 July 2009

Published in Implementation and Application of Automata (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-02979-0_14

Mathematics Subject Classification ID

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

Recommendations

• Recognition of directed acyclic graphs by spanning tree automata
• Recognition of labeled multidigraphs by spanning tree automata
• Closure properties and decision problems of dag automata
• Finite Automata on Unranked and Unordered DAGs
• Properties of regular DAG languages

Cites work

• Closure properties and decision problems of dag automata
• Implementation and Application of Automata
• Implementation and Application of 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

Cited in

(7)

• Closure properties and decision problems of dag automata
• Recognition of directed acyclic graphs by spanning tree automata
• A simple extension to finite tree automata for defining sets of labeled, connected 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
• A practical algorithm for the uniform membership problem of labeled multidigraphs of tree-width 2 for spanning tree automata
• Recognition of DFS trees: Sequential and parallel algorithms with refined verifications

This page was built for publication: Recognition of a Spanning Tree of Directed Acyclic Graphs by Tree Automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3637347)