From tree automata to string automata minimization
type: Item
instance of: scholarly article
title: From tree automata to string automata minimization
zbMATH Open document ID: 1400.68103
author: Younes Guellouma
author: Hadda Cherroun
author: Djelloul Ziadi
author: B. W. Watson
published in: Theory of Computing Systems
publication date: 2018-07-23T00:00:00Z
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.
reviewed by: Magnus Steinby
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68W05
zbMATH DE Number: 6909388
zbMATH Keywords: tree automaton
zbMATH Keywords: recognizable tree language
zbMATH Keywords: minimization algorithm
zbMATH Keywords: finite automaton
describes a project that uses: OpenFst
describes a project that uses: FSA
MaRDI profile type: Publication
full work available at URL: s00224-017-9815-4
OpenAlex ID: W2757434222
cites work: Q4447237
cites work: The minimalization of tree automata
cites work: Algebra automata I: Parallel programming as a prolegomena to the categorical approach
cites work: Q3862379
cites work: Fast brief practical DFA minimization
cites work: Q4179852
cites work: Q4848749
cites work: Parametric random generation of deterministic tree automata
cites work: Incremental DFA Minimisation
cites work: A split-based incremental deterministic automata minimization algorithm
cites work: Incremental construction of minimal tree automata
cites work: Incremental Construction and Maintenance of Minimal Finite-State Automata
cites work: An Implementation of Deterministic Tree Automata Minimization
cites work: COMPOSED BISIMULATION FOR TREE AUTOMATA
cites work: Backward and forward bisimulation minimization of tree automata
cites work: Three Partition Refinement Algorithms
cites work: XML compression via directed acyclic graphs
cites work: A new algorithm for the construction of minimal acyclic DFAs.
cites work: Minimisation of acyclic deterministic automata in linear time
cites work: Incremental Construction of Minimal Acyclic Finite-State Automata
cites work: Pushing for Weighted Tree Automata
cites work: Cycle-aware minimization of acyclic deterministic finite-state automata
DOI: 10.1007/S00224-017-9815-4
description: scientific article; zbMATH DE number 6909388