Short Regular Expressions from Finite Automata: Empirical Results

DOI10.1007/978-3-642-02979-0_22MaRDI QIDQ3637356zbMATH OpenOpenAlexFDO

Authors Hermann Gruber, Markus Holzer, Michael Tautschnig

Publication date 9 July 2009

Published in Implementation and Application of Automata (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-02979-0_22

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• State elimination ordering strategies: some experimental results
• Provably Shorter Regular Expressions from Deterministic Finite Automata
• State elimination heuristics for short regular expressions
• Implementation of State Elimination Using Heuristics
• Implementation and Application of Automata

Cites work

• Complexity measures for regular expressions
• Enumeration and generation with a string automata representation
• Finite Automata, Digraph Connectivity, and Regular Expression Size
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• Implementation and Application of Automata
• Implementation and Application of Automata
• Improved Approximation Algorithms for Minimum Weight Vertex Separators
• 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
• Provably Shorter Regular Expressions from Deterministic Finite Automata
• Regular expressions: new results and open problems
• Succinctness of the complement and intersection of regular expressions
• Transition graphs and the star-height of regular events

Cited in

(13)

• Automata and rational expressions
• Descriptional complexity of regular languages
• Provably Shorter Regular Expressions from Deterministic Finite Automata
• Series-Parallel Automata and Short Regular Expressions
• Implementation of State Elimination Using Heuristics
• Extended to multi-tilde-bar regular expressions and efficient finite automata constructions
• State elimination ordering strategies: some experimental results
• scientific article; zbMATH DE number 7075888 (Why is no real title available?)
• State elimination heuristics for short regular expressions
• Implementation and Application of Automata
• Implementation and Application of Automata
• Small balanced vertex separators in NFA to regular expression conversion
• Obtaining shorter regular expressions from finite-state automata

Describes a project that uses

Uses Software

• GenRGenS

This page was built for publication: Short Regular Expressions from Finite Automata: Empirical Results

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