Obtaining shorter regular expressions from finite-state automata
From MaRDI portal
Publication:868946
DOI10.1016/j.tcs.2006.09.025zbMath1118.68078MaRDI QIDQ868946
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
regular languages; finite-state automata; bridge states; horizontal chopping; state elimination; vertical chopping
68Q45: Formal languages and automata
Related Items
PROVABLY SHORTER REGULAR EXPRESSIONS FROM FINITE AUTOMATA, Counterexample Generation for Discrete-Time Markov Models: An Introductory Survey, Optimal Lower Bounds on Regular Expression Size Using Communication Complexity, 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
Uses Software
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