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

DOI10.1016/0020-0190(95)00199-9MaRDI QIDQ672727zbMATH OpenOpenAlexWikidataFDO

Authors 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)

Recommendations

• An nlogn Algorithm for Hyper-minimizing States in a (Minimized) Deterministic Automaton
• An n n algorithm for hyper-minimizing a (minimized) deterministic automaton
• scientific article; zbMATH DE number 1309169
• The minimization of a kind of non-deterministic finite automata
• scientific article; zbMATH DE number 3316051
• scientific article; zbMATH DE number 1962773
• scientific article; zbMATH DE number 4166871
• scientific article; zbMATH DE number 4108165
• Efficient minimization of deterministic weak -automata
• Implementation and Application of Automata

Cites work

• A taxonomy of sublinear multiple keyword pattern matching algorithms
• scientific article; zbMATH DE number 3124495 (Why is no real title available?)
• scientific article; zbMATH DE number 3856413 (Why is no real title available?)
• scientific article; zbMATH DE number 3460178 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 194974 (Why is no real title available?)
• scientific article; zbMATH DE number 3266653 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• Optimization of LR(k) parsers

Cited in

(22)

• Sorting and doubling techniques for set partitioning and automata minimization problems
• Re-describing an algorithm by Hopcroft
• Minimisation of automata
• Continuant polynomials and worst-case behavior of Hopcroft's minimization algorithm
• Average case analysis of Moore's state minimization algorithm
• Efficient deterministic finite automata split-minimization derived from Brzozowski's algorithm
• Hopcroft's algorithm and tree-like automata
• scientific article; zbMATH DE number 3883625 (Why is no real title available?)
• Forward bisimulations for nondeterministic symbolic finite automata
• scientific article; zbMATH DE number 4166871 (Why is no real title available?)
• An Implementation of Deterministic Tree Automata Minimization
• Hopcroft’s Algorithm and Cyclic Automata
• Edmonds-Karp
• Flow Networks
• Gabow SCC
• scientific article; zbMATH DE number 1309169 (Why is no real title available?)
• Fast brief practical DFA minimization
• A note on mc-DFA and its minimization
• Prpu_Maxflow
• Minimization of finite state automata through partition aggregation
• Incremental dead state detection in logarithmic time
• A split-based incremental deterministic automata minimization algorithm

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q672727)