Crisp-determinization of weighted tree automata over strong bimonoids

DOI10.46298/DMTCS.5943MaRDI QIDQ5038197zbMATH OpenOpenAlexFDO

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

Publication date 30 September 2022

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

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1912.02660, https://dmtcs.episciences.org/7580

zbMATH Keywords

determinizationsemiringstrong bimonoidundecidabilityweighted tree automaton

Mathematics Subject Classification ID

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

Abstract: We consider weighted tree automata (wta) over strong bimonoids and their initial algebra semantics and their run semantics. There are wta for which these semantics are different; however, for bottom-up deterministic wta and for wta over semirings, the difference vanishes. A wta is crisp-deterministic if it is bottom-up deterministic and each transition is weighted by one of the unit elements of the strong bimonoid. We prove that the class of weighted tree languages recognized by crisp-deterministic wta is the same as the class of recognizable step mappings. Moreover, we investigate the following two crisp-determinization problems: for a given wta $calA$, (a) does there exist a crisp-deterministic wta which computes the initial algebra semantics of $calA$ and (b) does there exist a crisp-deterministic wta which computes the run semantics of $calA$? We show that the finiteness of the Nerode algebra $calN(calA)$ of $calA$ implies a positive answer for (a), and that the finite order property of $calA$ implies a positive answer for (b). We show a sufficient condition which guarantees the finiteness of $calN(calA)$ and a sufficient condition which guarantees the finite order property of $calA$. Also, we provide an algorithm for the construction of the crisp-deterministic wta according to (a) if $calN(calA)$ is finite, and similarly for (b) if $calA$ has finite order property. We prove that it is undecidable whether an arbitrary wta $calA$ is crisp-determinizable. We also prove that both, the finiteness of $calN(calA)$ and the finite order property of $calA$ are undecidable.

Recommendations

• Crisp-determinization of weighted tree automata over additively locally finite and past-finite monotonic strong bimonoids is decidable
• Determinization of weighted finite automata over strong bimonoids
• scientific article; zbMATH DE number 6124028
• On the Determinization of Weighted Finite Automata
• An improved algorithm for determinization of weighted and fuzzy automata

Cites work

• Automata, Languages and Programming
• Bottom-up and top-down tree transformations— a comparison
• Determinization of weighted finite automata over strong bimonoids
• Determinization of weighted tree automata using factorizations
• Elements of automata theory. Translated from the French by Reuben Thomas
• Finite tree automata with cost functions
• Fuzzy languages
• Generalized finite automata theory with an application to a decision problem of second-order logic
• Handbook of weighted automata
• scientific article; zbMATH DE number 3854429 (Why is no real title available?)
• scientific article; zbMATH DE number 5141500 (Why is no real title available?)
• scientific article; zbMATH DE number 3932372 (Why is no real title available?)
• scientific article; zbMATH DE number 1183717 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3751028 (Why is no real title available?)
• scientific article; zbMATH DE number 41838 (Why is no real title available?)
• scientific article; zbMATH DE number 3497806 (Why is no real title available?)
• scientific article; zbMATH DE number 3588051 (Why is no real title available?)
• scientific article; zbMATH DE number 2040319 (Why is no real title available?)
• scientific article; zbMATH DE number 2040322 (Why is no real title available?)
• scientific article; zbMATH DE number 1542833 (Why is no real title available?)
• scientific article; zbMATH DE number 6124028 (Why is no real title available?)
• scientific article; zbMATH DE number 3290336 (Why is no real title available?)
• Initial Algebra Semantics and Continuous Algebras
• On the definition of a family of automata
• On the Determinization of Weighted Finite Automata
• Recognizable formal power series on trees
• Squaring transducers: An efficient procedure for deciding functionality and sequentiality.
• The finiteness problem for automaton semigroups is undecidable.
• Weighted automata and regular expressions over valuation monoids
• Weighted automata and weighted logics
• Weighted automata and weighted MSO logics for average and long-time behaviors
• Weighted finite automata over strong bimonoids
• Weighted grammars and Kleene's theorem
• Weighted tree automata and tree transducers
• Weighted tree automata and weighted logics

Cited in

(11)

• Crisp-determinization of weighted tree automata over additively locally finite and past-finite monotonic strong bimonoids is decidable
• Determinisability of unary weighted automata over the rational numbers
• Finite-image property of weighted tree automata over past-finite monotonic strong bimonoids
• The supports of weighted unranked tree automata
• On the Determinization of Weighted Finite Automata
• scientific article; zbMATH DE number 6124028 (Why is no real title available?)
• An improved algorithm for determinization of weighted and fuzzy automata
• Weighted tree generating regular systems over strong bimonoids with reduction semantics
• A Comparison of Sets of Recognizable Weighted Tree Languages Over Specific Sets of Bounded Lattices
• Weighted Automata over Vector Spaces
• Determinization of weighted finite automata over strong bimonoids

This page was built for publication: Crisp-determinization of weighted tree automata over strong bimonoids

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5038197)