Optimal Lower Bounds on Regular Expression Size Using Communication Complexity
From MaRDI portal
Publication:5458365
DOI10.1007/978-3-540-78499-9_20zbMath1139.68033OpenAlexW2112175063MaRDI QIDQ5458365
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
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