Minimisation of automata
type: Item
instance of: scholarly article
title: Minimisation of automata
author: Jean Berstel
author: Luc Boasson
author: Olivier Carton
author: Isabelle Fagnot
publication date: 2022-02-04T00:00:00Z
full work available at URL: https://arxiv.org/abs/1010.5318
review text: Summary: For the entire collection see [Zbl 1470.68001].
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 7469508
MaRDI profile type: Publication
cites work: Q4091421
cites work: Building the Minimal Automaton of A * X in Linear Time, When X Is of Bounded Cardinality
cites work: Description and analysis of a bottom-up DFA minimization algorithm
cites work: Q4005202
cites work: Around Hopcroft’s Algorithm
cites work: Q5389971
cites work: Average case analysis of Moore's state minimization algorithm
cites work: Continuant polynomials and worst-case behavior of Hopcroft's minimization algorithm
cites work: Sturmian trees
cites work: Implementation and Application of Automata
cites work: The tractability frontier for NFA minimization
cites work: An O(n \text{log} n) implementation of the standard method for minimizing n-state finite automata
cites work: The smallest automaton recognizing the subwords of a text
cites work: Q5725992
cites work: Incremental Construction and Maintenance of Minimal Finite-State Automata
cites work: Hopcroft’s Algorithm and Cyclic Automata
cites work: Circular Sturmian words and Hopcroft's algorithm
cites work: Transducers and repetitions
cites work: Algorithms on Strings
cites work: Q4418623
cites work: Comments on “Incremental Construction and Maintenance of Minimal Finite-State Automata,” by Rafael C. Carrasco and Mikel L. Forcada
cites work: Incremental Construction of Minimal Acyclic Finite-State Automata
cites work: Minimization of symbolic automata
cites work: Average complexity of Moore's and Hopcroft's algorithms
cites work: Q4799353
cites work: Brzozowski Algorithm Is Generically Super-Polynomial for Deterministic Automata
cites work: Average case analysis of Brzozowski's algorithm
cites work: Minimizing nfa's and regular expressions
cites work: Describing an algorithm by Hopcroft
cites work: On Simon's string searching algorithm
cites work: Q3862379
cites work: Minimal NFA Problems are Hard
cites work: DETERMINISTIC BLOW-UPS OF MINIMAL NONDETERMINISTIC FINITE AUTOMATA OVER A FIXED ALPHABET
cites work: MAGIC NUMBERS AND TERNARY ALPHABET
cites work: On the State Minimization of Nondeterministic Finite Automata
cites work: Generic-case complexity, decision problems in group theory, and random walks.
cites work: Re-describing an algorithm by Hopcroft
cites work: Algorithms for minimization of finite acyclic automata and pattern matching in terms
cites work: Q3086930
cites work: Minimizing finite automata is computationally hard
cites work: Automata Studies. (AM-34)
cites work: On the Hopcroft's minimization technique for DFA and DFCA
cites work: Q5317419
cites work: Minimisation of acyclic deterministic automata in linear time
cites work: Optimal insertion in deterministic DAWGs
cites work: Fast brief practical DFA minimization
cites work: A new algorithm for the construction of minimal acyclic DFAs.
DOI: 10.4171/AUTOMATA-1/10
description: scientific article; zbMATH DE number 7469508