Obtaining shorter regular expressions from finite-state automata

DOI10.1016/j.tcs.2006.09.025zbMath1118.68078OpenAlexW2142662777MaRDI QIDQ868946

Yo-Sub Han, Derick 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

regular languagesfinite-state automatabridge stateshorizontal choppingstate eliminationvertical chopping

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

Acyclic automata and small expressions using multi-tilde-bar operators, Provably Shorter Regular Expressions from Deterministic Finite Automata, PROVABLY SHORTER REGULAR EXPRESSIONS FROM FINITE AUTOMATA, Counterexample Generation for Discrete-Time Markov Models: An Introductory Survey, From Finite Automata to Regular Expressions and Back — A Summary on Descriptional Complexity, Multi-tilde Operators and Their Glushkov Automata, Optimal Lower Bounds on Regular Expression Size Using Communication Complexity, Implementation of State Elimination Using Heuristics, Short Regular Expressions from Finite Automata: Empirical Results, Small Extended Expressions for Acyclic Automata

Uses Software

• LANGAGE

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Deterministic generalized automata
• The validation of SGML content models
• A characterization of Thompson digraphs.
• Follow automata.
• Characterization of Glushkov automata
• THE ABSTRACT THEORY OF AUTOMATA
• Minimal NFA Problems are Hard
• THE GENERALIZATION OF GENERALIZED AUTOMATA: EXPRESSION AUTOMATA
• Implementation and Application of Automata
• Programming Techniques: Regular expression search algorithm
• STACS 2005
• Boolean Matrices and the Stability of Neural Nets
• Theory Is Forever