Finite Automata, Digraph Connectivity, and Regular Expression Size

DOI10.1007/978-3-540-70583-3_4zbMath1155.68418OpenAlexW1595778895WikidataQ56060439 ScholiaQ56060439MaRDI QIDQ3520302

Hermann Gruber, Markus Holzer

Publication date: 19 August 2008

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

Full work available at URL: https://doi.org/10.1007/978-3-540-70583-3_4

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Directed graphs (digraphs), tournaments (05C20) Connectivity (05C40)

Related Items

Closure properties and descriptional complexity of deterministic regular expressions, The chop of languages, An algorithmic metatheorem for directed treewidth, Computing the zig-zag number of directed graphs, Expressive power and succinctness of the positive calculus of binary relations, Learning from positive and negative examples: dichotomies and parameterized algorithms, Series parallel digraphs with loops, Shuffled languages -- representation and recognition, Expressive Power and Succinctness of the Positive Calculus of Relations, On low tree-depth decompositions, Finite Automata, Digraph Connectivity, and Regular Expression Size, Automata for regular expressions with shuffle, Acyclic automata and small expressions using multi-tilde-bar operators, On the algorithmic effectiveness of digraph decompositions and complexity measures, Language operations with regular expressions of polynomial size, Succinctness of regular expressions with interleaving, intersection and counting, Chrobak Normal Form Revisited, with Applications, Kleene Theorems for Product Systems, Multi-tilde Operators and Their Glushkov Automata, Optimal Lower Bounds on Regular Expression Size Using Communication Complexity, Regular expression length via arithmetic formula complexity, Algorithms for learning regular expressions from positive data, Tight Bounds on the Descriptional Complexity of Regular Expressions, Short Regular Expressions from Finite Automata: Empirical Results, Small Extended Expressions for Acyclic Automata, On the State Complexity of Partial Derivative Automata For Regular Expressions with Intersection

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Algorithms for determining relative star height and star height
• Inherently nonplanar automata
• Complexity measures for regular expressions
• Follow automata.
• Directed tree-width
• Tree-depth, subgraph coloring and homomorphism bounds
• Transition graphs and the star-height of regular events
• Finite Automata, Digraph Connectivity, and Regular Expression Size
• DAG-width
• Graph minors. II. Algorithmic aspects of tree-width
• Distance desert automata and the star height problem
• Regular Expressions and NFAs Without ε-Transitions
• DAG-Width and Parity Games
• Optimal Lower Bounds on Regular Expression Size Using Communication Complexity
• Automata, Languages and Programming
• The loop complexity of pure-group events
• Logic for Programming, Artificial Intelligence, and Reasoning
• Implementation and Application of Automata