|国家预印本平台
首页|Cyclic system for an algebraic theory of alternating parity automata

Cyclic system for an algebraic theory of alternating parity automata

Cyclic system for an algebraic theory of alternating parity automata

来源:Arxiv_logoArxiv
英文摘要

$\omega$-regular languages are a natural extension of the regular languages to the setting of infinite words. Likewise, they are recognised by a host of automata models, one of the most important being Alternating Parity Automata (APAs), a generalisation of B\"uchi automata that symmetrises both the transitions (with universal as well as existential branching) and the acceptance condition (by a parity condition). In this work we develop a cyclic proof system manipulating APAs, represented by an algebraic notation of Right Linear Lattice expressions. This syntax dualises that of previously introduced Right Linear Algebras, which comprised a notation for non-deterministic finite automata (NFAs). This dualisation induces a symmetry in the proof systems we design, with lattice operations behaving dually on each side of the sequent. Our main result is the soundness and completeness of our system for $\omega$-language inclusion, heavily exploiting game theoretic techniques from the theory of $\omega$-regular languages.

Anupam Das、Abhishek De

自动化基础理论

Anupam Das,Abhishek De.Cyclic system for an algebraic theory of alternating parity automata[EB/OL].(2025-05-13)[2025-06-05].https://arxiv.org/abs/2505.09000.点此复制

评论