Non-Deterministic Kleene Coalgebras

Alexandra Silva; Marcello Bonsangue; Jan Rutten

doi:10.2168/LMCS-6(3:23)2010

Alexandra Silva ; Marcello Bonsangue ; Jan Rutten - Non-Deterministic Kleene Coalgebras

lmcs:695 - Logical Methods in Computer Science, September 9, 2010, Volume 6, Issue 3 - https://doi.org/10.2168/LMCS-6(3:23)2010

Non-Deterministic Kleene CoalgebrasArticle

Authors: Alexandra Silva ; Marcello Bonsangue ; Jan Rutten

In this paper, we present a systematic way of deriving (1) languages of (generalised) regular expressions, and (2) sound and complete axiomatizations thereof, for a wide variety of systems. This generalizes both the results of Kleene (on regular languages and deterministic finite automata) and Milner (on regular behaviours and finite labelled transition systems), and includes many other systems such as Mealy and Moore machines.

https://doi.org/10.2168/LMCS-6(3:23)2010

Source: arXiv.org:1007.3769

Volume: Volume 6, Issue 3

Published on: September 9, 2010

Imported on: January 3, 2010

Keywords: Computer Science - Logic in Computer Science,F.3.1, F.3.2, F.4.1

Licence: arXiv.org - Non-exclusive license to distribute

Funding:

Source : OpenAIRE Graph

SERVICE-ORIENTED COMPUTING: FOUNDATIONS AND CALCULI; Code: SFRH/BD/27482/2006

Classifications

Mathematics Subject Classification 2020¹

68Q45 - Formal languages and automata

Sources:

[1] zbMATH Open.

Bibliographic References

11 Documents citing this article

Todd Schmid;Jurriaan Rot;Alexandra Silva, 2021, On Star Expressions and Completeness Theorems, arXiv (Cornell University), 351, pp. 242-259, 10.4204/eptcs.351.15.

Stefan Milius;Dirk Pattinson;Thorsten Wißmann, arXiv (Cornell University), A New Foundation for Finitary Corecursion, pp. 107-125, 2016, 10.1007/978-3-662-49630-5_7, http://arxiv.org/abs/1601.01532.

A. Ballester-Bolinches;E. Cosme-Llópez;R. Esteban-Romero, 2014, A description based on languages of the final non-deterministic automaton, Theoretical Computer Science, 536, pp. 1-20, 10.1016/j.tcs.2014.01.018, https://doi.org/10.1016/j.tcs.2014.01.018.

Bart Jacobs;Alexandra Silva, CiteSeer X (The Pennsylvania State University), Initial Algebras of Terms with Binding and Algebraic Structure, pp. 211-234, 2014, 10.1007/978-3-642-54789-8_12, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.822.8321.

Marcello M. Bonsangue;Stefan Milius;Alexandra Silva, 2013, Sound and Complete Axiomatizations of Coalgebraic Language Equivalence, arXiv (Cornell University), 14, 1, pp. 1-52, 10.1145/2422085.2422092, http://arxiv.org/abs/1104.2803.

Alexandra Silva, CWI's Institutional Repository (Centrum Wiskunde & Informatica), A Specification Language for Reo Connectors, pp. 368-376, 2012, 10.1007/978-3-642-29320-7_26, https://ir.cwi.nl/pub/18033.

Marcello Bonsangue;Georgiana Caltais;Eugen-Ioan Goriac;Dorel Lucanu;Jan Rutten;et al., 2012, Automatic equivalence proofs for non-deterministic coalgebras, Science of Computer Programming, 78, 9, pp. 1324-1345, 10.1016/j.scico.2012.07.001, https://doi.org/10.1016/j.scico.2012.07.001.

Clemens Kupke;Dirk Pattinson, 2011, Coalgebraic semantics of modal logics: An overview, Theoretical Computer Science, 412, 38, pp. 5070-5094, 10.1016/j.tcs.2011.04.023, https://doi.org/10.1016/j.tcs.2011.04.023.

Fritz Henglein;Lasse Nielsen, 2011, Regular expression containment, ACM SIGPLAN Notices, 46, 1, pp. 385-398, 10.1145/1925844.1926429.

Joost Winter;Marcello M. Bonsangue;Jan Rutten, CWI's Institutional Repository (Centrum Wiskunde & Informatica), Context-Free Languages, Coalgebraically, pp. 359-376, 2011, 10.1007/978-3-642-22944-2_25, https://ir.cwi.nl/pub/18032.

Marcello Bonsangue;Georgiana Caltais;Eugen-Ioan Goriac;Dorel Lucanu;Jan Rutten;et al., KOPS (University of Konstanz), A Decision Procedure for Bisimilarity of Generalized Regular Expressions, pp. 226-241, 2011, 10.1007/978-3-642-19829-8_15, http://nbn-resolving.de/urn:nbn:de:bsz:352-2-yi8hayl9n9430.

Sources : OpenCitations, OpenAlex & Crossref

Share and export

Consultation statistics

This page has been seen 2109 times.

This article's PDF has been downloaded 378 times.