Provably Shorter Regular Expressions from Deterministic Finite Automata

DOI10.1007/978-3-540-85780-8_30MaRDI QIDQ3533026zbMATH OpenOpenAlexFDO

Authors Hermann Gruber, Markus Holzer

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)

Recommendations

• Provably shorter regular expressions from finite automata
• Short Regular Expressions from Finite Automata: Empirical Results
• State elimination ordering strategies: some experimental results
• State elimination heuristics for short regular expressions
• Implementation and Application of Automata

Cites work

• A Separator Theorem for Planar Graphs
• Automata Studies. (AM-34)
• Complexity measures for regular expressions
• Derivatives of Regular Expressions
• Follow automata.
• Graph minors. II. Algorithmic aspects of tree-width
• scientific article; zbMATH DE number 2068872 (Why is no real title available?)
• scientific article; zbMATH DE number 194974 (Why is no real title available?)
• scientific article; zbMATH DE number 3251424 (Why is no real title available?)
• scientific article; zbMATH DE number 964896 (Why is no real title available?)
• scientific article; zbMATH DE number 3041944 (Why is no real title available?)
• Implementation and Application of Automata
• Implementation and Application of Automata
• Obtaining shorter regular expressions from finite-state automata
• Optimal Lower Bounds on Regular Expression Size Using Communication Complexity
• Planarization and fragmentability of some classes of graphs
• Regular expressions: new results and open problems
• Succinctness of Regular Expressions with Interleaving, Intersection and Counting
• Succinctness of the complement and intersection of regular expressions

Cited in

(14)

• An optimal construction of finite automata from regular expressions
• Finite Automata, Digraph Connectivity, and Regular Expression Size
• Simplifying regular expressions. A quantitative perspective
• Tight Bounds on the Descriptional Complexity of Regular Expressions
• Implementation of State Elimination Using Heuristics
• Short Regular Expressions from Finite Automata: Empirical Results
• State elimination ordering strategies: some experimental results
• Provably shorter regular expressions from finite automata
• Implementation and Application of Automata
• An improved spectral lower bound of treewidth
• On deterministic finite automata equipped with partial orders
• Obtaining shorter regular expressions from finite-state automata
• More concise representation of regular languages by automata and regular expressions
• Succinctness of regular expressions with interleaving, intersection and counting

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

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