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; Funder: Fundação para a Ciência e a Tecnologia, I.P.; 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, Electronic Proceedings in Theoretical Computer Science, 351, pp. 242-259, 10.4204/eptcs.351.15, https://doi.org/10.4204/eptcs.351.15.

Stefan Milius;Dirk Pattinson;Thorsten Wißmann, 2016, A New Foundation for Finitary Corecursion, arXiv (Cornell University), pp. 107-125, 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, http://hdl.handle.net/10251/51041.

Bart Jacobs;Alexandra Silva, 2014, Initial Algebras of Terms with Binding and Algebraic Structure, Lecture notes in computer science, pp. 211-234, 10.1007/978-3-642-54789-8_12.

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, 2012, A Specification Language for Reo Connectors, Lecture notes in computer science, pp. 368-376, 10.1007/978-3-642-29320-7_26.

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.

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.

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, 2011, Context-Free Languages, Coalgebraically, Lecture notes in computer science, pp. 359-376, 10.1007/978-3-642-22944-2_25.

Marcello Bonsangue;Georgiana Caltais;Eugen-Ioan Goriac;Dorel Lucanu;Jan Rutten;et al., 2011, A Decision Procedure for Bisimilarity of Generalized Regular Expressions, VU Research Portal, pp. 226-241, 10.1007/978-3-642-19829-8_15, https://research.vu.nl/en/publications/c473c1f2-2ba8-4641-b5ef-c58ad2ef72b4.

Sources : OpenCitations, OpenAlex & Crossref

Share and export

Consultation statistics

This page has been seen 2881 times.

This article's PDF has been downloaded 462 times.