An O(n \text{log} n) implementation of the standard method for minimizing n-state finite automata

DOI10.1016/0020-0190(95)00199-9zbMath0875.68649OpenAlexW2113689473WikidataQ126839033 ScholiaQ126839033MaRDI QIDQ672727

Norbert Blum

Publication date: 28 February 1997

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(95)00199-9

zbMATH Keywords

AlgorithmsFinite automataMinimization

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Parallel algorithms in computer science (68W10)

Related Items (9)

EFFICIENT DETERMINISTIC FINITE AUTOMATA SPLIT-MINIMIZATION DERIVED FROM BRZOZOWSKI'S ALGORITHM ⋮ An Implementation of Deterministic Tree Automata Minimization ⋮ Average case analysis of Moore's state minimization algorithm ⋮ A split-based incremental deterministic automata minimization algorithm ⋮ Forward Bisimulations for Nondeterministic Symbolic Finite Automata ⋮ Continuant polynomials and worst-case behavior of Hopcroft's minimization algorithm ⋮ A note on mc-DFA and its minimization ⋮ Minimisation of automata ⋮ Re-describing an algorithm by Hopcroft

Cites Work

• A taxonomy of sublinear multiple keyword pattern matching algorithms
• Optimization of LR(k) parsers
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: An O(n \text{log} n) implementation of the standard method for minimizing n-state finite automata