Digraph complexity measures and applications in formal language theory

zbMATH Open1283.68196arXiv1111.5357MaRDI QIDQ5403035FDOQ5403035

Authors: Hermann Gruber 

Publication date: 25 March 2014

Full work available at URL: https://arxiv.org/abs/1111.5357

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

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)

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
• Hierarchical decompositions and termination analysis for generalized planning
• How to compute digraph width measures on directed co-graphs
• 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)