Obtaining shorter regular expressions from finite-state automata

DOI10.1016/J.TCS.2006.09.025MaRDI QIDQ868946zbMATH OpenOpenAlexFDO

Authors Yo-Sub Han, D. Wood

Publication date 26 February 2007

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2006.09.025

zbMATH Keywords

bridge statesfinite-state automatahorizontal choppingregular languagesstate eliminationvertical chopping

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Implementation and Application of Automata
• Provably shorter regular expressions from finite automata
• Short Regular Expressions from Finite Automata: Empirical Results
• Provably Shorter Regular Expressions from Deterministic Finite Automata
• Regular expressions into finite automata
• scientific article; zbMATH DE number 1948484
• From regular expressions to finite automata^∗
• An optimal construction of finite automata from regular expressions
• From regular expressions to smaller NFAs
• More Concise Representation of Regular Languages by Automata and Regular Expressions

Cites work

• A characterization of Thompson digraphs.
• Boolean Matrices and the Stability of Neural Nets
• Characterization of Glushkov automata
• Deterministic generalized automata
• Follow automata.
• scientific article; zbMATH DE number 3460178 (Why is no real title available?)
• scientific article; zbMATH DE number 3497806 (Why is no real title available?)
• scientific article; zbMATH DE number 2162119 (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?)
• Implementation and Application of Automata
• Introduction to algorithms
• Minimal NFA Problems are Hard
• Programming Techniques: Regular expression search algorithm
• STACS 2005
• THE ABSTRACT THEORY OF AUTOMATA
• THE GENERALIZATION OF GENERALIZED AUTOMATA: EXPRESSION AUTOMATA
• The validation of SGML content models
• Theory Is Forever

Cited in

(16)

• Acyclic automata and small expressions using multi-tilde-bar operators
• From finite automata to regular expressions and back -- a summary on descriptional complexity
• Provably Shorter Regular Expressions from Deterministic Finite Automata
• Multi-tilde Operators and Their Glushkov Automata
• Implementation of State Elimination Using Heuristics
• Short Regular Expressions from Finite Automata: Empirical Results
• Small Extended Expressions for Acyclic Automata
• On regular expression hashing to reduce FA size
• Provably shorter regular expressions from finite automata
• Counterexample generation for discrete-time Markov models: an introductory survey
• State elimination heuristics for short regular expressions
• Optimal Lower Bounds on Regular Expression Size Using Communication Complexity
• STACS 2005
• Implementation and Application of Automata
• Small balanced vertex separators in NFA to regular expression conversion
• From regular expressions to smaller NFAs

Describes a project that uses

Uses Software

• LANGAGE

This page was built for publication: Obtaining shorter regular expressions from finite-state automata

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