Re-describing an algorithm by Hopcroft
From MaRDI portal
Publication:1589443
DOI10.1016/S0304-3975(99)00150-4zbMath0952.68077WikidataQ56750561 ScholiaQ56750561MaRDI QIDQ1589443
Publication date: 12 December 2000
Published in: Theoretical Computer Science (Search for Journal in Brave)
Related Items
Quasilinear-time Computation of Generic Modal Witnesses for Behavioural Inequivalence, Unnamed Item, An automata-theoretic approach to the word problem for \(\omega\)-terms over R, EFFICIENT DETERMINISTIC FINITE AUTOMATA SPLIT-MINIMIZATION DERIVED FROM BRZOZOWSKI'S ALGORITHM, Subsequential transducers: a coalgebraic perspective, Probabilistic Arithmetic Automata and Their Application to Pattern Matching Statistics, Construction of minimal deterministic finite automata from biological motifs, A graph theoretic approach to automata minimality, Average case analysis of Moore's state minimization algorithm, A split-based incremental deterministic automata minimization algorithm, Fast brief practical DFA minimization, On extremal cases of Hopcroft's algorithm, Hopcroft’s Algorithm and Cyclic Automata, An algorithm to compute the character access count distribution for pattern matching algorithms, Cycle-aware minimization of acyclic deterministic finite-state automata, Hopcroft's algorithm and tree-like automata, From generic partition refinement to weighted tree automata minimization, Description and analysis of a bottom-up DFA minimization algorithm, A search algorithm for subshift attractors of cellular automata, Continuant polynomials and worst-case behavior of Hopcroft's minimization algorithm, Hopcroft’s Minimization Technique: Queues or Stacks?, Linear kernels and linear-time algorithms for finding large cuts, Circular Sturmian words and Hopcroft's algorithm, On the Hopcroft's minimization technique for DFA and DFCA, Bisimilarity Minimization in O(m logn) Time, On Extremal Cases of Hopcroft’s Algorithm, Average complexity of Moore's and Hopcroft's algorithms, Minimisation of automata, Efficient Coalgebraic Partition Refinement, A reduction technique for weighted grouping problems
Uses Software
Cites Work
- An O(n \text{log} n) implementation of the standard method for minimizing n-state finite automata
- A linear time solution to the single function coarsest partition problem
- Partitioning a graph in \(O(|A|\log_ 2|V|)\)
- AUTOMATE, a computing package for automata and finite semigroups
- Algebraic and structural automata theory. Transl. of algebraiczna i structuralna teoria automatów (PWN, Warsaw, 1985)
- Minimisation of acyclic deterministic automata in linear time
- \textit{Grail}: A C++ library for automata and expressions
- Describing an algorithm by Hopcroft
- Three Partition Refinement Algorithms
- Implementing Quicksort programs
- Quicksort
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
