Minimisation of automata
From MaRDI portal
Publication:2074212
DOI10.4171/Automata-1/10MaRDI QIDQ2074212
Luc Boasson, Jean Berstel, Olivier Carton, Isabelle Fagnot
Publication date: 4 February 2022
Full work available at URL: https://arxiv.org/abs/1010.5318
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The tractability frontier for NFA minimization
- Fast brief practical DFA minimization
- An O(n \text{log} n) implementation of the standard method for minimizing n-state finite automata
- On Simon's string searching algorithm
- Minimizing finite automata is computationally hard
- Circular Sturmian words and Hopcroft's algorithm
- Average complexity of Moore's and Hopcroft's algorithms
- Description and analysis of a bottom-up DFA minimization algorithm
- Sturmian trees
- On the Hopcroft's minimization technique for DFA and DFCA
- The smallest automaton recognizing the subwords of a text
- Minimisation of acyclic deterministic automata in linear time
- Generic-case complexity, decision problems in group theory, and random walks.
- Optimal insertion in deterministic DAWGs
- A new algorithm for the construction of minimal acyclic DFAs.
- Re-describing an algorithm by Hopcroft
- Transducers and repetitions
- Continuant polynomials and worst-case behavior of Hopcroft's minimization algorithm
- Average case analysis of Moore's state minimization algorithm
- Describing an algorithm by Hopcroft
- Minimizing nfa's and regular expressions
- Average Case Analysis of Brzozowski's Algorithm
- MAGIC NUMBERS AND TERNARY ALPHABET
- Comments on “Incremental Construction and Maintenance of Minimal Finite-State Automata,” by Rafael C. Carrasco and Mikel L. Forcada
- Automata Studies. (AM-34)
- DETERMINISTIC BLOW-UPS OF MINIMAL NONDETERMINISTIC FINITE AUTOMATA OVER A FIXED ALPHABET
- Hopcroft’s Algorithm and Cyclic Automata
- Building the Minimal Automaton of A * X in Linear Time, When X Is of Bounded Cardinality
- Algorithms for minimization of finite acyclic automata and pattern matching in terms
- Minimal NFA Problems are Hard
- Incremental Construction and Maintenance of Minimal Finite-State Automata
- Incremental Construction of Minimal Acyclic Finite-State Automata
- Brzozowski Algorithm Is Generically Super-Polynomial for Deterministic Automata
- Minimization of symbolic automata
- Algorithms on Strings
- Implementation and Application of Automata
- On the State Minimization of Nondeterministic Finite Automata
- Around Hopcroft’s Algorithm
This page was built for publication: Minimisation of automata
