Obtaining shorter regular expressions from finite-state automata
From MaRDI portal
Publication:868946
DOI10.1016/J.TCS.2006.09.025zbMATH Open1118.68078OpenAlexW2142662777MaRDI QIDQ868946FDOQ868946
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
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
finite-state automataregular languagesbridge stateshorizontal choppingstate eliminationvertical chopping
Cites Work
- Introduction to algorithms
- THE ABSTRACT THEORY OF AUTOMATA
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Minimal NFA Problems are Hard
- Title not available (Why is that?)
- Follow automata.
- Title not available (Why is that?)
- A characterization of Thompson digraphs.
- Characterization of Glushkov automata
- Programming Techniques: Regular expression search algorithm
- Theory Is Forever
- STACS 2005
- Boolean Matrices and the Stability of Neural Nets
- Deterministic generalized automata
- THE GENERALIZATION OF GENERALIZED AUTOMATA: EXPRESSION AUTOMATA
- The validation of SGML content models
- Implementation and Application of Automata
Cited In (15)
- Small Extended Expressions for Acyclic Automata
- On regular expression hashing to reduce FA size
- Optimal Lower Bounds on Regular Expression Size Using Communication Complexity
- Implementation of State Elimination Using Heuristics
- STACS 2005
- Counterexample generation for discrete-time Markov models: an introductory survey
- State elimination heuristics for short regular expressions
- Acyclic automata and small expressions using multi-tilde-bar operators
- Short Regular Expressions from Finite Automata: Empirical Results
- Provably shorter regular expressions from finite automata
- From regular expressions to smaller NFAs
- From finite automata to regular expressions and back -- a summary on descriptional complexity
- Implementation and Application of Automata
- Multi-tilde Operators and Their Glushkov Automata
- Provably Shorter Regular Expressions from Deterministic Finite Automata
Uses Software
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)
