Tight Bounds on the Descriptional Complexity of Regular Expressions

DOI10.1007/978-3-642-02737-6_22MaRDI QIDQ3637232zbMATH OpenOpenAlexFDO

Authors Hermann Gruber, Markus Holzer

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)

Recommendations

• The complexity of regular(-like) expressions
• The complexity of regular(-like) expressions
• Descriptional complexity of regular languages
• Optimal Lower Bounds on Regular Expression Size Using Communication Complexity
• Provably shorter regular expressions from finite automata

Cites work

• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• Algorithms for determining relative star height and star height
• Complexity measures for regular expressions
• Directed tree-width
• Finite Automata, Digraph Connectivity, and Regular Expression Size
• Homomorphisms that preserve star height
• Language operations with regular expressions of polynomial size
• On the complexity of iterated shuffle
• Optimal Lower Bounds on Regular Expression Size Using Communication Complexity
• Provably Shorter Regular Expressions from Deterministic Finite Automata
• Regular expressions: new results and open problems
• Star height of certain families of regular events
• Succinctness of Regular Expressions with Interleaving, Intersection and Counting
• Succinctness of the complement and intersection of regular expressions
• The loop complexity of pure-group events
• The treewidth and pathwidth of hypercubes
• Transition graphs and the star-height of regular events

Cited in

(22)

• Succinctness of Regular Expressions with Interleaving, Intersection and Counting
• Succinctness of the complement and intersection of regular expressions
• Unshuffling a square is NP-hard
• Analysis of an efficient reduction algorithm for random regular expressions based on universality detection
• The complexity of regular(-like) expressions
• State complexity of the concatenation of regular tree languages
• Semi-linear Parikh Images of Regular Expressions via Reduction
• State complexity of Kleene-star operations on trees
• Succinctness of regular expressions with interleaving, intersection and counting
• Games for succinctness of regular expressions
• Implementation and Application of Automata
• Optimal Lower Bounds on Regular Expression Size Using Communication Complexity
• Regular expression length via arithmetic formula complexity
• The complexity of regular(-like) expressions
• Finite Automata, Digraph Connectivity, and Regular Expression Size
• Descriptional complexity of regular languages
• String shuffle: circuits and graphs
• The tractability frontier for NFA minimization
• Closure properties and descriptional complexity of deterministic regular expressions
• From finite automata to regular expressions and back -- a summary on descriptional complexity
• From finite automata to regular expressions and back -- a summary on descriptional complexity
• On pumping preserving homomorphisms and the complexity of the pumping problem (extended abstract)

This page was built for publication: Tight Bounds on the Descriptional Complexity of Regular Expressions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3637232)