Minimisation of acyclic deterministic automata in linear time
From MaRDI portal
A deterministic automaton is acyclic if the underlying graph is acyclic. Two automata are said to be equivalent if and only if they recognise the same language. If \(A\) is an automaton there exists an unique automaton \(M\) minimal by the number of states, recognizing the same language. An automaton with no pair of equivalent states is minimal. The minimal automaton for a given language \(L\) is the unique automaton with the smallest number of states among those recognizing \(L\). The author presents a linear algorithm for the minimization of acyclic automata. This algorithm can be used, in particular, on automaton representing lexicons.
Recommendations
- Cycle-aware minimization of acyclic deterministic finite-state automata
- A fast and simple algorithm for constructing minimal acyclic deterministic finite automata
- Exact enumeration of acyclic deterministic automata
- Direct construction of minimal acyclic finite states automata
- A new algorithm for the construction of minimal acyclic DFAs.
Cites work
- Graph-Based Algorithms for Boolean Function Manipulation
- scientific article; zbMATH DE number 3124495 (Why is no real title available?)
- scientific article; zbMATH DE number 3511563 (Why is no real title available?)
- scientific article; zbMATH DE number 3254905 (Why is no real title available?)
- scientific article; zbMATH DE number 3266653 (Why is no real title available?)
- scientific article; zbMATH DE number 3310089 (Why is no real title available?)
- On the computational power of pushdown automata
- Partitioning a graph in \(O(|A|\log_ 2|V|)\)
- Three Partition Refinement Algorithms
Cited in
(47)- Fast equation automaton computation
- Optimal insertion in deterministic DAWGs
- INTEX: An FST toolbox
- The design principles of a weighted finite-state transducer library
- Re-describing an algorithm by Hopcroft
- Extending greedy feature selection algorithms to multiple solutions
- Minimisation of automata
- State complexity of finite partial languages
- Manipulation of regular expressions using derivatives: an overview
- Continuant polynomials and worst-case behavior of Hopcroft's minimization algorithm
- Efficient computation of substring equivalence classes with suffix arrays
- Building efficient and compact data structures for simplicial complexes
- Average case analysis of Moore's state minimization algorithm
- Parsing with a finite dictionary
- Exact enumeration of acyclic deterministic automata
- Polynomial time multiplication and normal forms in free bands
- How to squeeze a lexicon
- Enumeration of minimal acyclic automata via generalized parking functions
- Satisfiability via smooth pictures
- On-line construction of a small automaton for a finite set of words
- A challenging family of automata for classical minimization algorithms
- EXACT GENERATION OF MINIMAL ACYCLIC DETERMINISTIC FINITE AUTOMATA
- Hopcroft’s Algorithm and Cyclic Automata
- Running Time Complexity of Printing an Acyclic Automaton
- Sampling different kinds of acyclic automata using Markov chains
- An efficient algorithm for the construction of the equation tree automaton
- Cycle-aware minimization of acyclic deterministic finite-state automata
- Random generation of deterministic acyclic automata using Markov chains
- Epichristoffel Words and Minimization of Moore Automata
- Boosting over non-deterministic ZDDs
- Computations by fly-automata beyond monadic second-order logic
- State complexity of finite partial languages
- Quantum algorithm for lexicographically minimal string rotation
- Block languages and their bitmap representations
- Using multiset discrimination to solve language processing problems without hashing
- McDag: indexing maximal common subsequences in practice
- Operational state complexity of block languages
- Acyclic networks maximizing the printing complexity
- Ternary directed acyclic word graphs
- From tree automata to string automata minimization
- Circular Sturmian words and Hopcroft's algorithm
- Average complexity of Moore's and Hopcroft's algorithms
- General suffix automaton construction algorithm and space bounds
- Construction of Aho Corasick automaton in linear time for integer alphabets
- An automata-theoretic approach to the word problem for \(\omega\)-terms over R
- A split-based incremental deterministic automata minimization algorithm
- Description and analysis of a bottom-up DFA minimization algorithm
This page was built for publication: Minimisation of acyclic deterministic automata in linear time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1190464)
