A Nivat Theorem for Weighted Alternating Automata over Commutative Semirings

DOI10.46298/LMCS-19(4:27)2023arXiv2203.07370OpenAlexW4390232466MaRDI QIDQ6137852FDOQ6137852

Authors:

Publication date: 16 January 2024

Published in: Logical Methods in Computer Science (Search for Journal in Brave)

Abstract: This paper connects the classes of weighted alternating finite automata (WAFA), weighted finite tree automata (WFTA), and polynomial automata (PA). First, we investigate the use of trees in the run semantics for weighted alternating automata and prove that the behavior of a weighted alternating automaton can be characterized as the composition of the behavior of a weighted finite tree automaton and a specific tree homomorphism, if weights are taken from a commutative semiring. Based on this, we give a Nivat-like characterization for weighted alternating automata. Moreover, we show that the class of series recognized by weighted alternating automata is closed under inverses of homomorphisms, but not under homomorphisms. Additionally, we give a logical characterization of weighted alternating automata, which uses weighted MSO logic for trees. Finally, we investigate the strong connection between weighted alternating automata and polynomial automata. We prove: A weighted language is recognized by a weighted alternating automaton iff its reversal in recognized by a polynomial automaton. Using the corresponding result for polynomial automata, we are able to prove that the ZERONESS problem for weighted alternating automata with weights taken from the rational numbers decidable.

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

zbMATH Keywords

automata theorytree automataweighted automataalternating automataweighted logics

Mathematics Subject Classification ID

Logic in computer science (03B70) Computer science (68-XX)

Cites Work

• Handbook of weighted automata
• Alternation
• On the definition of a family of automata
• Alternating automata on infinite trees
• Alternating Weighted Automata
• Quantitative Languages
• Weighted Tree Automata and Tree Transducers
• On equations for regular languages, finite automata, and sequential networks
• Weighted automata and weighted logics
• Weighted Automata and Weighted Logics
• Weighted logics for unranked tree automata
• Weighted tree automata and weighted logics
• Transductions des langages de Chomsky
• Max and sum semantics for alternating weighted automata
• Weighted automata and logics on graphs
• Alternating weighted automata over commutative semirings
• Regular Functions and Cost Register Automata
• A Nivat Theorem for Quantitative Automata on Unranked Trees
• Sequences of Level 1, 2, 3,..., k,...

This page was built for publication: A Nivat Theorem for Weighted Alternating Automata over Commutative Semirings

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