Tight Bounds on the Descriptional Complexity of Regular Expressions

DOI10.1007/978-3-642-02737-6_22zbMath1247.68141OpenAlexW1600628136MaRDI QIDQ3637232

Markus Holzer, Hermann Gruber

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/

Mathematics Subject Classification ID

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

Related Items

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