Tight Bounds on the Descriptional Complexity of Regular Expressions
From MaRDI portal
Publication:3637232
DOI10.1007/978-3-642-02737-6_22zbMath1247.68141OpenAlexW1600628136MaRDI QIDQ3637232
Publication date: 7 July 2009
Published in: Developments in Language Theory (Search for Journal in Brave)
Full work available at URL: http://geb.uni-giessen.de/geb/volltexte/2012/9080/
Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (9)
Closure properties and descriptional complexity of deterministic regular expressions ⋮ State Complexity of Kleene-Star Operations on Trees ⋮ Unshuffling a square is NP-hard ⋮ The tractability frontier for NFA minimization ⋮ State complexity of the concatenation of regular tree languages ⋮ String shuffle: circuits and graphs ⋮ Succinctness of regular expressions with interleaving, intersection and counting ⋮ Regular expression length via arithmetic formula complexity ⋮ Descriptional complexity of regular languages
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the complexity of iterated shuffle
- The treewidth and pathwidth of hypercubes
- Algorithms for determining relative star height and star height
- Complexity measures for regular expressions
- Directed tree-width
- Language operations with regular expressions of polynomial size
- Transition graphs and the star-height of regular events
- Star height of certain families of regular events
- Finite Automata, Digraph Connectivity, and Regular Expression Size
- Provably Shorter Regular Expressions from Deterministic Finite Automata
- Succinctness of Regular Expressions with Interleaving, Intersection and Counting
- Homomorphisms that preserve star height
- Optimal Lower Bounds on Regular Expression Size Using Communication Complexity
- The loop complexity of pure-group events
This page was built for publication: Tight Bounds on the Descriptional Complexity of Regular Expressions
