2026-07-20T14:45:26Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24146 2025-11-12T13:33:38Z ddc:004 open_access

Right-Linear Lattices: An Algebraic Theory of ω-Regular Languages, with Fixed Points Das, Anupam De, Abhishek omega-languages regular languages fixed points Kleene algebras right-linear grammars Alternating parity automata (APAs) provide a robust formalism for modelling infinite behaviours and play a central role in formal verification. Despite their widespread use, the algebraic theory underlying APAs has remained largely unexplored. In recent work [Anupam Das and Abhishek De, 2024], a notation for non-deterministic finite automata (NFAs) was introduced, along with a sound and complete axiomatisation of their equational theory via right-linear algebras. In this paper, we extend that line of work to the setting of infinite words. In particular, we present a dualised syntax, yielding a notation for APAs based on right-linear lattice expressions, and provide a natural axiomatisation of their equational theory with respect to the standard language model of ω-regular languages. The design of this axiomatisation is guided by the theory of fixed point logics; in fact, the completeness factors cleanly through the completeness of the linear-time μ-calculus. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Anupam Das and Abhishek De 2025 Is Part Of LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2025.39 urn:nbn:de:0030-drops-241461 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.39 eng https://creativecommons.org/licenses/by/4.0/legalcode