From regular expressions to deterministic finite automata: 2ⁿ²+n( n)^ (1) states are necessary and sufficient
From MaRDI portal
Publication:6861674
Cites work
- A lower bound on the size of \(\varepsilon\)-free NFA corresponding to a regular expression
- Chrobak normal form revisited, with applications
- Complexity measures for regular expressions
- Computingϵ-Free NFA from Regular Expressions inO(nlog2(n)) Time
- Finite automata and unary languages
- Finite Automata, Digraph Connectivity, and Regular Expression Size
- Follow automata.
- From finite automata to regular expressions and back -- a summary on descriptional complexity
- scientific article; zbMATH DE number 3709588 (Why is no real title available?)
- scientific article; zbMATH DE number 3251424 (Why is no real title available?)
- Improved upper bounds for planarization and series-parallelization of degree-bounded graphs
- Programming Techniques: Regular expression search algorithm
- Provably shorter regular expressions from finite automata
- Regular Expressions and NFAs Without ε-Transitions
- Regular expressions: new results and open problems
- Separating Exponentially Ambiguous Finite Automata from Polynomially Ambiguous Finite Automata
- Simplifying regular expressions. A quantitative perspective
- THE ABSTRACT THEORY OF AUTOMATA
- The complexity of restricted regular expressions and the synthesis problem for finite automata
- The difference between consecutive primes. II
- Translating regular expressions into small \(\epsilon\)-free nondeterministic finite automata
This page was built for publication: From regular expressions to deterministic finite automata: \(2^{\frac{n}{2}+\sqrt{n}(\log n)^{\varTheta (1)}}\) states are necessary and sufficient
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6861674)
