Backward and forward bisimulation minimization of tree automata

DOI10.1016/j.tcs.2009.03.022zbMath1194.68139OpenAlexW2089409100MaRDI QIDQ840778

Johanna Högberg, Jonathan May, Andreas Maletti

Publication date: 14 September 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.03.022

zbMATH Keywords

minimizationbisimulationtree languagepartition refinementtree automaton

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Related Items (22)

Weak bisimulations for fuzzy automata ⋮ Decidability of the minimization of fuzzy tree automata with membership values in complete lattices ⋮ Similarity-based minimization of fuzzy tree automata ⋮ Unnamed Item ⋮ On the greatest solutions to weakly linear systems of fuzzy relation inequalities and equations ⋮ An automated quantitative information flow analysis for concurrent programs ⋮ Unnamed Item ⋮ Bisimulations for fuzzy automata ⋮ Nondeterministic automata: equivalence, bisimulations, and uniform relations ⋮ Approximate bisimulations and state reduction of fuzzy automata under fuzzy similarity measures ⋮ From generic partition refinement to weighted tree automata minimization ⋮ HYPER-MINIMIZATION FOR DETERMINISTIC TREE AUTOMATA ⋮ Computation of the greatest simulations and bisimulations between fuzzy automata ⋮ Minimization of Finite State Automata Through Partition Aggregation ⋮ Fuzzy relation equations and reduction of fuzzy automata ⋮ From tree automata to string automata minimization ⋮ Aggregation-based minimization of finite state automata ⋮ Approximate bisimulation relations for fuzzy automata ⋮ MINIMIZATION OF PLANAR DIRECTED ACYCLIC GRAPH ALGEBRAS ⋮ The Bottom-Up Position Tree Automaton and the Father Automaton ⋮ Hyper-optimization for deterministic tree automata ⋮ A Congruence-Based Perspective on Finite Tree Automata

Uses Software

• Tiburon
• Penn Treebank

Cites Work

• Bisimulation relations for weighted automata
• Minimizing nfa's and regular expressions
• BISIMULATION MINIMIZATION OF TREE AUTOMATA
• Backward and Forward Bisimulation Minimisation of Tree Automata
• Composed Bisimulation for Tree Automata
• Three Partition Refinement Algorithms
• Inapproximability of Nondeterministic State and Transition Complexity Assuming P ≠ NP
• STACS 2005
• Bisimulation Minimization of Tree Automata
• Tiburon: A Weighted Tree Automata Toolkit
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Backward and forward bisimulation minimization of tree automata