Tight Bounds on the Descriptional Complexity of Regular Expressions

DOI10.1007/978-3-642-02737-6_22zbMATH Open1247.68141OpenAlexW1600628136MaRDI QIDQ3637232FDOQ3637232

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/

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (19)

• Succinctness of Regular Expressions with Interleaving, Intersection and Counting
• The complexity of regular(-like) expressions
• Closure properties and descriptional complexity of deterministic regular expressions
• Optimal Lower Bounds on Regular Expression Size Using Communication Complexity
• Analysis of an efficient reduction algorithm for random regular expressions based on universality detection
• State complexity of the concatenation of regular tree languages
• Regular expression length via arithmetic formula complexity
• String shuffle: circuits and graphs
• Succinctness of regular expressions with interleaving, intersection and counting
• The tractability frontier for NFA minimization
• The complexity of regular(-like) expressions
• Unshuffling a square is NP-hard
• Semi-linear Parikh Images of Regular Expressions via Reduction
• Games for succinctness of regular expressions
• State Complexity of Kleene-Star Operations on Trees
• Finite Automata, Digraph Connectivity, and Regular Expression Size
• Descriptional complexity of regular languages
• Implementation and Application of Automata
• 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)