Graded Semantics and Graded Logics for Eilenberg-Moore Coalgebras

Forster J, Schröder L, Wild P, Beohar H, Gurke S, Messing K (2024)

Publication Type: Conference contribution

Publication year: 2024

Journal

Lecture Notes in Computer Science Springer Verlag

Publisher: Springer Science and Business Media Deutschland GmbH

Book Volume: 14617 LNCS

Pages Range: 114-134

Conference Proceedings Title: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Event location: Luxembourg City LU

ISBN: 9783031664373

DOI: 10.1007/978-3-031-66438-0_6

Abstract

Coalgebra, as the abstract study of state-based systems, comes naturally equipped with a notion of behavioural equivalence that identifies states exhibiting the same behaviour. In many cases, however, this equivalence is finer than the intended semantics. Particularly in automata theory, behavioural equivalence of nondeterministic automata is essentially bisimilarity, and thus does not coincide with language equivalence. Language equivalence can be captured as behavioural equivalence on the determinization, which is obtained via the standard powerset construction. This construction can be lifted to coalgebraic generality, assuming a so-called Eilenberg-Moore distributive law between the functor determining the type of accepted structure (e.g. word languages) and a monad capturing the branching type (e.g. nondeterministic, weighted, probabilistic). Eilenberg-Moore-style coalgebraic semantics in this sense has been shown to be essentially subsumed by the more general framework of graded semantics, which is centrally based on graded monads. Graded semantics comes with a range of generic results, in particular regarding invariance and, under suitable conditions, expressiveness of dedicated modal logics for a given semantics; notably, these logics are evaluated on the original state space. We show that the instantiation of such graded logics to the case of Eilenberg-Moore-style semantics works extremely smoothly, and yields expressive modal logics in essentially all cases of interest. We additionally parametrize the framework over a quantale of truth values, thus in particular covering both the two-valued notions of equivalence and quantitative ones, i.e. behavioural distances.

Authors with CRIS profile

Jonas Forster Lehrstuhl für Informatik 8 (Theoretische Informatik) Lutz Schröder Lehrstuhl für Informatik 8 (Theoretische Informatik) Paul Wild Lehrstuhl für Informatik 8 (Theoretische Informatik)

Involved external institutions

University of Sheffield GB United Kingdom (GB) Universität Duisburg-Essen (UDE) DE Germany (DE)

How to cite

APA:

Forster, J., Schröder, L., Wild, P., Beohar, H., Gurke, S., & Messing, K. (2024). Graded Semantics and Graded Logics for Eilenberg-Moore Coalgebras. In Barbara König, Henning Urbat (Eds.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp. 114-134). Luxembourg City, LU: Springer Science and Business Media Deutschland GmbH.

MLA:

Forster, Jonas, et al. "Graded Semantics and Graded Logics for Eilenberg-Moore Coalgebras." Proceedings of the 17th International Workshop on Coalgebraic Methods in Computer Science, CMCS 2024, Luxembourg City Ed. Barbara König, Henning Urbat, Springer Science and Business Media Deutschland GmbH, 2024. 114-134.

BibTeX: Download