Cyclic system for an algebraic theory of alternating parity automata
By: Anupam Das, Abhishek De
Potential Business Impact:
Proves if computer programs run forever.
$\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.
Similar Papers
An algebraic theory of ω-regular languages, via μν-expressions
Logic
Makes computer checks for infinite loops work.
Rerailing Automata
Formal Languages and Automata Theory
Makes computer programs check themselves faster.
Cyclic Proofs in Hoare Logic and its Reverse
Logic in Computer Science
Proves computer programs work correctly, even with loops.