Finite Automata, Digraph Connectivity, and Regular Expression Size

DOI10.1007/978-3-540-70583-3_4zbMath1155.68418WikidataQ56060439 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

68Q45: Formal languages and automata

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C20: Directed graphs (digraphs), tournaments

05C40: Connectivity

Related Items

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

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