Rational Operational Models

Milius S, Bonsangue M, Myers R, Rot J (2013)

Publication Type: Conference contribution

Publication year: 2013

Journal

Electronic Notes in Theoretical Computer Science Elsevier BV

Publisher: Elsevier BV

Edited Volumes: Electronic Notes in Theoretical Computer Science

Series: Electronic Notes in Theoretical Computer Science

City/Town: Berlin München

Book Volume: 298

Pages Range: 257-282

Conference Proceedings Title: Proc. of the Twenty-ninth Conference on the Mathematical Foundations of Programming Semantics, MFPS XXIX

URI: https://www8.cs.fau.de/~milius/publications/papers.html

DOI: 10.1016/j.entcs.2013.09.017

Abstract

GSOS is a specification format for well-behaved operations on transition systems. Aceto introduced a restriction of this format, called simple GSOS, which guarantees that the associated transition system is locally finite, i.e. every state has only finitely many different descendent states (i.e. states reachable by a sequence of transitions). The theory of coalgebras provides a framework for the uniform study of systems, including labelled transition systems but also, e.g. weighted transition systems and (non-)deterministic automata. In this context GSOS can be studied at the general level of distributive laws of syntax over behaviour. In the present paper we generalize Aceto's result to the setting of coalgebras by restricting abstract GSOS to bipointed specifications. We show that the operational model of a bipointed specification is locally finite, even for specifications with infinitely many operations which have finite dependency. As an example, we derive a concrete format for operations on regular languages and obtain for free that regular expressions have finitely many derivatives modulo the equations of join semilattices. © 2013 Elsevier B.V.

Authors with CRIS profile

Stefan Milius Lehrstuhl für Informatik 8 (Theoretische Informatik)

Involved external institutions

Technische Universität Braunschweig DE Germany (DE) Leiden University NL Netherlands (NL)

How to cite

APA:

Milius, S., Bonsangue, M., Myers, R., & Rot, J. (2013). Rational Operational Models. In Proc. of the Twenty-ninth Conference on the Mathematical Foundations of Programming Semantics, MFPS XXIX (pp. 257-282). Berlin München: Elsevier BV.

MLA:

Milius, Stefan, et al. "Rational Operational Models." Proceedings of the Proc. of the Twenty-ninth Conference on the Mathematical Foundations of Programming Semantics, MFPS XXIX Berlin München: Elsevier BV, 2013. 257-282.

BibTeX: Download