Deciding Equivalence of Finite Tree Automata

DOI10.1137/0219027zbMath0699.68075OpenAlexW2019789808MaRDI QIDQ3477969

Helmut Seidl

Publication date: 1990

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0219027

zbMATH Keywords

complexityequivalenceambiguitysemiringsfinite tree automata

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70) Semigroups in automata theory, linguistics, etc. (20M35)

Related Items (43)

Synchronized tree automata ⋮ Deciding twig-definability of node selecting tree automata ⋮ The mu-calculus and Model Checking ⋮ Definable transductions and weighted logics for texts ⋮ Complexity of Equivalence and Learning for Multiplicity Tree Automata ⋮ Weighted tree automata and weighted logics ⋮ Generating, sampling and counting subclasses of regular tree languages ⋮ Automata for XML -- a survey ⋮ Choice functions and well-orderings over the infinite binary tree ⋮ On the minimization of XML schemas and tree automata for unranked trees ⋮ Simplifying XML schema: single-type approximations of regular tree languages ⋮ Regular matching and inclusion on compressed tree patterns with constrained context variables ⋮ Complexity of EOL structural equivalence ⋮ Conjunctive Visibly-Pushdown Path Queries ⋮ Minimisation of Multiplicity Tree Automata ⋮ A gap property of deterministic tree languages. ⋮ Efficient inclusion testing for simple classes of unambiguous \(\omega \)-automata ⋮ Minimizing Deterministic Weighted Tree Automata ⋮ Distributed XML design ⋮ Validating XML document adaptations via hedge automata transformations ⋮ Complexity of E0L structural equivalence ⋮ On the degree of ambiguity of finite automata ⋮ Decidability of equivalence for deterministic synchronized tree automata ⋮ On the equivalence of recursive and nonrecursive Datalog programs ⋮ A Fragment of ML Decidable by Visibly Pushdown Automata ⋮ Third-order Idealized Algol with iteration is decidable ⋮ Single-valuedness of tree transducers is decidable in polynomial time ⋮ Another variation on the common subexpression problem ⋮ Deciding low levels of tree-automata hierarchy ⋮ A Büchi-like theorem for weighted tree automata over multioperator monoids ⋮ Analysis of dynamic policies ⋮ On the complexity of typechecking top-down XML transformations ⋮ Attribute grammars for unranked trees as a query language for structured documents ⋮ Deciding inclusion of set constants over infinite non-strict data structures ⋮ Characterizing EF and EX tree logics ⋮ Weak Inclusion for XML Types ⋮ Automata on infinite trees ⋮ Efficient inclusion checking for deterministic tree automata and XML schemas ⋮ Minimizing deterministic weighted tree automata ⋮ Unambiguity in Automata Theory ⋮ Genetic algorithms in logic tree decision modeling ⋮ Relating word and tree automata ⋮ Sequentiality, monadic second-order logic and tree automata.

This page was built for publication: Deciding Equivalence of Finite Tree Automata