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

digraphvertex rankingregular expressionordered coloringstar heightcycle rank

Mathematics Subject Classification ID

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

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)

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

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)