A Nivat Theorem for Weighted Alternating Automata over Commutative Semirings

DOI10.46298/LMCS-19(4:27)2023MaRDI QIDQ6137852zbMATH OpenOpenAlexFDO

Authors

Publication date 16 January 2024

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

Copyright license Creative Commons Attribution 4.0 International

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)

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.

Recommendations

• A Nivat theorem for weighted alternating automata over commutative semirings
• Alternating weighted automata over commutative semirings
• Alternating Weighted Automata
• A Nivat theorem for quantitative automata on unranked trees
• Weighted tree automata and weighted logics

Cites work

• A Nivat theorem for quantitative automata on unranked trees
• Alternating Weighted Automata
• Alternating automata on infinite trees
• Alternating weighted automata over commutative semirings
• Alternation
• Handbook of weighted automata
• Max and sum semantics for alternating weighted automata
• On equations for regular languages, finite automata, and sequential networks
• On the definition of a family of automata
• Quantitative Languages
• Regular functions and cost register automata (invited paper)
• Sequences of Level 1, 2, 3,..., k,...
• Transductions des langages de Chomsky
• Weighted automata and logics on graphs
• Weighted automata and weighted logics
• Weighted automata and weighted logics
• Weighted logics for unranked tree automata
• Weighted tree automata and tree transducers
• Weighted tree automata and weighted logics

Cited in

(1)

• A Nivat theorem for weighted alternating automata over commutative semirings

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)