Finite automata as characterizations of minor closed tree families (extended abstract)

DOI10.1007/3-540-56939-1_86MaRDI QIDQ4630274zbMATH OpenOpenAlexFDO

Authors Arvind Kumar Gupta

Publication date 29 March 2019

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-56939-1_86

zbMATH Keywords

finite automatonplanar graphpolynomial time algorithmregular expressionrooted tree

Mathematics Subject Classification ID

Trees (05C05) Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 841653
• scientific article; zbMATH DE number 176761
• Recognition of labeled multidigraphs by spanning tree automata
• scientific article; zbMATH DE number 10087
• Graph minors. II. Algorithmic aspects of tree-width

Cites work

• Easy problems for tree-decomposable graphs
• Graph minors. XX: Wagner's conjecture
• Nonconstructive tools for proving polynomial-time decidability

Cited in

(1)

• scientific article; zbMATH DE number 841653 (Why is no real title available?)

This page was built for publication: Finite automata as characterizations of minor closed tree families (extended abstract)

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