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 Coalgebras

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

Linked publications - datasets - softwares

Source : ScholeXplorer IsReferencedBy ARXIV 1104.2803 Source : ScholeXplorer IsReferencedBy DOI 10.1145/2422085.2422092 Source : ScholeXplorer IsReferencedBy DOI 10.48550/arxiv.1104.2803 Source : ScholeXplorer IsReferencedBy HANDLE 1822/35523 Source : ScholeXplorer IsReferencedBy HANDLE 1887/59681 Source : ScholeXplorer IsReferencedBy HANDLE 2066/111253 2066/111253 1887/59681 10.48550/arxiv.1104.2803 1104.2803 2066/111253 1887/59681 1822/35523 10.1145/2422085.2422092 10.1145/2422085.2422092 10.1145/2422085.2422092 Sound and complete axiomatizations of coalgebraic language equivalence Bonsangue, M.M. ; Milius, S. ; Silva, A. ;

11 Documents citing this article

Source : OpenCitations

Ballester-Bolinches, Adolfo; Cosme-Llรณpez, E.; Esteban-Romero, Ramรณn, 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.

Bonsangue, Marcello; Caltais, Georgiana; Goriac, Eugen-Ioan; Lucanu, Dorel; Rutten, Jan; Silva, Alexandra, 2011, A Decision Procedure For Bisimilarity Of Generalized Regular Expressions, Lecture Notes In Computer Science, pp. 226-241, 10.1007/978-3-642-19829-8_15.

Bonsangue, Marcello; Caltais, Georgiana; Goriac, Eugen-Ioan; Lucanu, Dorel; Rutten, Jan; Silva, Alexandra, 2013, Automatic Equivalence Proofs For Non-Deterministic Coalgebras, Science Of Computer Programming, 78, 9, pp. 1324-1345, 10.1016/j.scico.2012.07.001.

Bonsangue, Marcello; Milius, Stefan; Silva, Alexandra, 2013, Sound And Complete Axiomatizations Of Coalgebraic Language Equivalence, ACM Transactions On Computational Logic, 14, 1, pp. 1-52, 10.1145/2422085.2422092.

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

Jacobs, Bart; Silva, Alexandra, 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.

Kupke, Clemens; Pattinson, Dirk, 2011, Coalgebraic Semantics Of Modal Logics: An Overview, Theoretical Computer Science, 412, 38, pp. 5070-5094, 10.1016/j.tcs.2011.04.023.

Milius, Stefan; Pattinson, Dirk; WiĂmann, Thorsten, 2016, A New Foundation For Finitary Corecursion, Foundations Of Software Science And Computation Structures, pp. 107-125, 10.1007/978-3-662-49630-5_7.

Schmid, Todd; Rot, Jurriaan; Silva, Alexandra, 2021, On Star Expressions And Completeness Theorems, Electronic Proceedings In Theoretical Computer Science, 351, pp. 242-259, 10.4204/eptcs.351.15.

Silva, Alexandra, 2012, A Specification Language For Reo Connectors, Fundamentals Of Software Engineering, pp. 368-376, 10.1007/978-3-642-29320-7_26.

Winter, Joost; Bonsangue, Marcello; Rutten, Jan, 2011, Context-Free Languages, Coalgebraically, Algebra And Coalgebra In Computer Science, pp. 359-376, 10.1007/978-3-642-22944-2_25.

Share and export

Consultation statistics

This page has been seen 632 times.

This article's PDF has been downloaded 220 times.