Optimal Lower Bounds on Regular Expression Size Using Communication Complexity

DOI10.1007/978-3-540-78499-9_20zbMath1139.68033OpenAlexW2112175063MaRDI QIDQ5458365

Jan Johannsen, Hermann Gruber

Publication date: 11 April 2008

Published in: Foundations of Software Science and Computational Structures (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-78499-9_20

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (11)

Closure properties and descriptional complexity of deterministic regular expressions ⋮ Series parallel digraphs with loops ⋮ Finite Automata, Digraph Connectivity, and Regular Expression Size ⋮ Provably Shorter Regular Expressions from Deterministic Finite Automata ⋮ Language operations with regular expressions of polynomial size ⋮ Succinctness of regular expressions with interleaving, intersection and counting ⋮ Multi-tilde-bar expressions and their automata ⋮ Regular expression length via arithmetic formula complexity ⋮ Tight Bounds on the Descriptional Complexity of Regular Expressions ⋮ Short Regular Expressions from Finite Automata: Empirical Results ⋮ Descriptional complexity of regular languages

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Obtaining shorter regular expressions from finite-state automata
• Complexity measures for regular expressions
• Monotone separation of logarithmic space from logarithmic depth
• Method of determining lower bounds for the complexity of \(\Pi\)-circuits
• Automata Studies. (AM-34)
• Monotone Circuits for Connectivity Require Super-Logarithmic Depth
• Finite Automata, Digraph Connectivity, and Regular Expression Size
• A New Rank Technique for Formula Size Lower Bounds
• Communication Complexity
• Regular Expressions and NFAs Without ε-Transitions
• Implementation and Application of Automata
• Two Complete Axiom Systems for the Algebra of Regular Events
• Implementation and Application of Automata
• Implementation and Application of Automata

This page was built for publication: Optimal Lower Bounds on Regular Expression Size Using Communication Complexity