Minimisation of acyclic deterministic automata in linear time
From MaRDI portal
Publication:1190464
DOI10.1016/0304-3975(92)90142-3zbMath0759.68066OpenAlexW2070830131WikidataQ56048077 ScholiaQ56048077MaRDI QIDQ1190464
Publication date: 26 September 1992
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(92)90142-3
Related Items
General suffix automaton construction algorithm and space bounds ⋮ ON-LINE CONSTRUCTION OF A SMALL AUTOMATON FOR A FINITE SET OF WORDS ⋮ Manipulation of regular expressions using derivatives: an overview ⋮ An automata-theoretic approach to the word problem for \(\omega\)-terms over R ⋮ Efficient computation of substring equivalence classes with suffix arrays ⋮ Building efficient and compact data structures for simplicial complexes ⋮ Optimal insertion in deterministic DAWGs ⋮ Quantum algorithm for lexicographically minimal string rotation ⋮ Average case analysis of Moore's state minimization algorithm ⋮ Polynomial time multiplication and normal forms in free bands ⋮ Sampling different kinds of acyclic automata using Markov chains ⋮ Hopcroft’s Algorithm and Cyclic Automata ⋮ Cycle-aware minimization of acyclic deterministic finite-state automata ⋮ Using multiset discrimination to solve language processing problems without hashing ⋮ Description and analysis of a bottom-up DFA minimization algorithm ⋮ Parsing with a finite dictionary ⋮ Ternary directed acyclic word graphs ⋮ Exact enumeration of acyclic deterministic automata ⋮ State complexity of finite partial languages ⋮ Continuant polynomials and worst-case behavior of Hopcroft's minimization algorithm ⋮ How to squeeze a lexicon ⋮ From tree automata to string automata minimization ⋮ Boosting over non-deterministic ZDDs ⋮ Random Generation of Deterministic Acyclic Automata Using Markov Chains ⋮ Extending greedy feature selection algorithms to multiple solutions ⋮ Circular Sturmian words and Hopcroft's algorithm ⋮ Computations by fly-automata beyond monadic second-order logic ⋮ A Challenging Family of Automata for Classical Minimization Algorithms ⋮ An Efficient Algorithm for the Construction of the Equation Tree Automaton ⋮ Satisfiability via Smooth Pictures ⋮ Fast equation automaton computation ⋮ Average complexity of Moore's and Hopcroft's algorithms ⋮ Minimisation of automata ⋮ INTEX: An FST toolbox ⋮ The design principles of a weighted finite-state transducer library ⋮ Re-describing an algorithm by Hopcroft ⋮ State complexity of finite partial languages
Cites Work
