Backward and forward bisimulation minimization of tree automata

DOI10.1016/j.tcs.2009.03.022zbMath1194.68139MaRDI 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

minimization; bisimulation; tree language; partition refinement; tree automaton

Mathematics Subject Classification ID

68Q45: Formal languages and automata

68Q85: Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)

Related Items

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

Uses Software

• Tiburon
• Penn Treebank

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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