Provably Shorter Regular Expressions from Deterministic Finite Automata

DOI10.1007/978-3-540-85780-8_30zbMath1161.68533OpenAlexW1533814670MaRDI QIDQ3533026

Markus Holzer, Hermann Gruber

Publication date: 30 October 2008

Published in: Developments in Language Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-85780-8_30

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (max. 100)

More concise representation of regular languages by automata and regular expressions ⋮ Succinctness of regular expressions with interleaving, intersection and counting ⋮ Tight Bounds on the Descriptional Complexity of Regular Expressions ⋮ Implementation of State Elimination Using Heuristics ⋮ Short Regular Expressions from Finite Automata: Empirical Results

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Obtaining shorter regular expressions from finite-state automata
• Complexity measures for regular expressions
• Follow automata.
• Planarization and fragmentability of some classes of graphs
• Automata Studies. (AM-34)
• Succinctness of Regular Expressions with Interleaving, Intersection and Counting
• Graph minors. II. Algorithmic aspects of tree-width
• A Separator Theorem for Planar Graphs
• Optimal Lower Bounds on Regular Expression Size Using Communication Complexity
• Implementation and Application of Automata
• Derivatives of Regular Expressions
• Implementation and Application of Automata

This page was built for publication: Provably Shorter Regular Expressions from Deterministic Finite Automata