Cycle-aware minimization of acyclic deterministic finite-state automata

DOI10.1016/J.DAM.2013.08.003MaRDI QIDQ496535zbMATH OpenOpenAlexFDO

Authors Johannes Bubenzer

Publication date 22 September 2015

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2013.08.003

zbMATH Keywords

minimizationalgorithmicdeterministic finite state automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Minimisation of acyclic deterministic automata in linear time
• Description and analysis of a bottom-up DFA minimization algorithm
• A fast and simple algorithm for constructing minimal acyclic deterministic finite automata
• Fast brief practical DFA minimization
• Incremental DFA minimisation

Cites work

• scientific article; zbMATH DE number 3460178 (Why is no real title available?)
• scientific article; zbMATH DE number 1033260 (Why is no real title available?)
• scientific article; zbMATH DE number 1962788 (Why is no real title available?)
• scientific article; zbMATH DE number 798342 (Why is no real title available?)
• scientific article; zbMATH DE number 3266653 (Why is no real title available?)
• scientific article; zbMATH DE number 3189697 (Why is no real title available?)
• Describing an algorithm by Hopcroft
• Incremental Construction of Minimal Acyclic Finite-State Automata
• Linear Automaton Transformations
• Minimisation of acyclic deterministic automata in linear time
• Re-describing an algorithm by Hopcroft
• \(fsm2\) --- A scripting language for creating weighted finite-state morphologies

Cited in

(4)

• From tree automata to string automata minimization
• Branching measures and nearly acyclic NFAs
• A fast and simple algorithm for constructing minimal acyclic deterministic finite automata
• Minimisation of acyclic deterministic automata in linear time

Describes a project that uses

Uses Software

• fsm2

This page was built for publication: Cycle-aware minimization of acyclic deterministic finite-state automata

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