On the finite degree of ambiguity of finite tree automata

DOI10.1007/BF00263578zbMath0683.68049OpenAlexW3022399311MaRDI QIDQ1825038

Helmut Seidl

Publication date: 1989

Published in: Acta Informatica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf00263578

zbMATH Keywords

computational complexitydecidabilitytree automatadegree of ambiguity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Related Items (11)

Finite tree automata with cost functions ⋮ Finite-image property of weighted tree automata over past-finite monotonic strong bimonoids ⋮ Equivalence of finite-valued tree transducers is decidable ⋮ On the degree of ambiguity of finite automata ⋮ Single-valuedness of tree transducers is decidable in polynomial time ⋮ Queries on XML streams with bounded delay and concurrency ⋮ On finitely generated monoids of matrices with entries in $\mathbb {N}$ ⋮ Unnamed Item ⋮ Finite sequentiality of unambiguous max-plus tree automata ⋮ On degrees of ambiguity for Büchi tree automata ⋮ On Finite and Polynomial Ambiguity of Weighted Tree Automata

This page was built for publication: On the finite degree of ambiguity of finite tree automata