Digraph complexity measures and applications in formal language theory

MaRDI QIDQ5403035zbMATH OpenFDO

Authors Hermann Gruber

Publication date 25 March 2014

Full work available at URL https://arxiv.org/abs/1111.5357, https://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/2107/0.html

zbMATH Keywords

cycle rankdigraphordered coloringregular expressionstar heightvertex ranking

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20) Paths and cycles (05C38) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Approximation algorithms (68W25)

Recommendations

• Finite Automata, Digraph Connectivity, and Regular Expression Size
• scientific article; zbMATH DE number 4213459
• scientific article; zbMATH DE number 3843141
• Distance desert automata and the star height problem
• On the complexity of the relative inclusion star height problem

Cited in

(10)

• Complex systems, complexity measures, grammars and model-inferring
• Structural properties of NFAs and growth rates of nondeterminism measures
• Non-perturbative graph languages, halting problem and complexity
• How to compute digraph width measures on directed co-graphs
• Estimation of expressions' complexities for two-terminal directed acyclic graphs
• An algorithmic metatheorem for directed treewidth
• A slice theoretic approach for embedding problems on digraphs
• Bideterministic weighted automata
• Bideterministic weighted automata
• Hierarchical decompositions and termination analysis for generalized planning

This page was built for publication: Digraph complexity measures and applications in formal language theory

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