Crisp-determinization of weighted tree automata over strong bimonoids

DOI10.46298/dmtcs.5943zbMath1496.68208arXiv1912.02660OpenAlexW3173756144MaRDI QIDQ5038197

Dávid Kószó, Heiko Vogler, Zoltán Fülöp

Publication date: 30 September 2022

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

Full work available at URL: https://arxiv.org/abs/1912.02660

zbMATH Keywords

undecidabilitysemiringdeterminizationstrong bimonoidweighted tree automaton

Mathematics Subject Classification ID

Algebraic theory of languages and automata (68Q70) Semigroups in automata theory, linguistics, etc. (20M35)

Related Items

Finite-image property of weighted tree automata over past-finite monotonic strong bimonoids ⋮ Unnamed Item ⋮ A Comparison of Sets of Recognizable Weighted Tree Languages Over Specific Sets of Bounded Lattices ⋮ Weighted Automata over Vector Spaces ⋮ Determinisability of unary weighted automata over the rational numbers

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Handbook of weighted automata
• Weighted finite automata over strong bimonoids
• Weighted tree automata and weighted logics
• Determinization of weighted finite automata over strong bimonoids
• Weighted grammars and Kleene's theorem
• Recognizable formal power series on trees
• Finite tree automata with cost functions
• Squaring transducers: An efficient procedure for deciding functionality and sequentiality.
• Weighted automata and weighted MSO logics for average and long-time behaviors
• Weighted automata and weighted logics
• WEIGHTED AUTOMATA AND REGULAR EXPRESSIONS OVER VALUATION MONOIDS
• On the definition of a family of automata
• Bottom-up and top-down tree transformations— a comparison
• Initial Algebra Semantics and Continuous Algebras
• On the Determinization of Weighted Finite Automata
• Weighted Tree Automata and Tree Transducers
• Fuzzy Languages
• THE FINITENESS PROBLEM FOR AUTOMATON SEMIGROUPS IS UNDECIDABLE
• Generalized finite automata theory with an application to a decision problem of second-order logic
• Automata, Languages and Programming