From tree automata to string automata minimization

DOI10.1007/S00224-017-9815-4MaRDI QIDQ722214zbMATH OpenOpenAlexFDO

Authors Younes Guellouma, Hadda Cherroun, Djelloul Ziadi, B. W. Watson

Publication date 23 July 2018

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00224-017-9815-4

zbMATH Keywords

finite automatonminimization algorithmrecognizable tree languagetree automaton

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Nonnumerical algorithms (68W05)

Review text

The authors associate with any given deterministic finite bottom-up tree automaton (DFTA) a deterministic finite string automaton (DFA) that can be used for minimizing the tree automaton. By this reduction the existing efficient minimization algorithms designed for string automata become applicable to tree automata. Thus, using a standard minimization method for DFAs, a DFTA can be minimized in time \(\mathcal{O}(rm + m \log n)\), where \(r\) is the maximal rank in the ranked alphabet, \(m\) is the size of the DFTA and \(n\) is the number of its states. The reduction yields also efficient methods for minimizing acyclic DFTAs, as well as for incremental minimization and incremental construction of DFTAs.

Recommendations

• An Implementation of Deterministic Tree Automata Minimization
• Minimization of deterministic fuzzy tree automata
• Hyper-minimization for deterministic tree automata
• Minimizing Deterministic Weighted Tree Automata
• Minimization of deterministic top-down tree automata

Cites work

• A new algorithm for the construction of minimal acyclic DFAs.
• A split-based incremental deterministic automata minimization algorithm
• Algebra automata I: Parallel programming as a prolegomena to the categorical approach
• An Implementation of Deterministic Tree Automata Minimization
• Backward and forward bisimulation minimization of tree automata
• COMPOSED BISIMULATION FOR TREE AUTOMATA
• Cycle-aware minimization of acyclic deterministic finite-state automata
• Fast brief practical DFA minimization
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3615891 (Why is no real title available?)
• scientific article; zbMATH DE number 2043533 (Why is no real title available?)
• scientific article; zbMATH DE number 798342 (Why is no real title available?)
• Incremental Construction and Maintenance of Minimal Finite-State Automata
• Incremental Construction of Minimal Acyclic Finite-State Automata
• Incremental construction of minimal tree automata
• Incremental DFA minimisation
• Minimisation of acyclic deterministic automata in linear time
• Parametric random generation of deterministic tree automata
• The minimalization of tree automata
• Three Partition Refinement Algorithms
• XML compression via directed acyclic graphs

Cited in

(10)

• Separating strings with small automata
• The suffix tree of a tree and minimizing sequential transducers
• Incremental construction of minimal tree automata
• Minimization of deterministic fuzzy tree automata
• An Implementation of Deterministic Tree Automata Minimization
• scientific article; zbMATH DE number 139615 (Why is no real title available?)
• scientific article; zbMATH DE number 2087487 (Why is no real title available?)
• A congruence-based perspective on finite tree automata
• Minimization of deterministic top-down tree automata
• Independent minimum length programs to translate between given strings

Describes a project that uses

Uses Software

• OpenFst
• FSA

This page was built for publication: From tree automata to string automata minimization

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