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

DOI10.1007/978-3-319-40946-7_9zbMATH Open1379.68221OpenAlexW2475641334MaRDI QIDQ2830211FDOQ2830211

Authors: Akio Fujiyoshi 

Publication date: 9 November 2016

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

Full work available at URL: https://doi.org/10.1007/978-3-319-40946-7_9

Recommendations

• 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
• An $\mbox{O}(n^{1.75})$ Algorithm for L(2,1)-Labeling of Trees
• A linear time algorithm for \(L(2,1)\)-labeling of trees
• A Linear Time Algorithm for L(2,1)-Labeling of Trees
• An O\((n^{1.75})\) algorithm for \(L(2,1)\)-labeling of trees
• scientific article; zbMATH DE number 2197903
• A technique for recognizing graphs of bounded treewidth with application to subclasses of partial 2-paths
• Characterization results for the \(L(2, 1, 1)\)-labeling problem on trees
• Exact algorithms for \(L(2,1)\)-labeling of graphs

Mathematics Subject Classification ID

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

Cites Work

• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Graph structure and monadic second-order logic. A language-theoretic approach
• Characterization and Recognition of Partial 3-Trees
• Verification of Mathematical Formulae Based on a Combination of Context-Free Grammar and Tree Grammar
• Recognition of a Spanning Tree of Directed Acyclic Graphs by Tree Automata
• Recognition of directed acyclic graphs by spanning tree automata
• Recognition of labeled multidigraphs by spanning tree automata

Cited In (4)

• Finite-dimensional approximations of neutral-type conflict-controlled systems
• 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
• On Hamilton-Jacobi-Isaacs-Bellman equation for neutral type systems

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

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