Alexandra Silva ; Filippo Bonchi ; Marcello Bonsangue ; Jan Rutten - Generalizing determinization from automata to coalgebras

lmcs:1087 - Logical Methods in Computer Science, March 4, 2013, Volume 9, Issue 1 - https://doi.org/10.2168/LMCS-9(1:9)2013
Generalizing determinization from automata to coalgebrasArticle

Authors: Alexandra Silva ; Filippo Bonchi ; Marcello Bonsangue ; Jan Rutten

    The powerset construction is a standard method for converting a nondeterministic automaton into a deterministic one recognizing the same language. In this paper, we lift the powerset construction from automata to the more general framework of coalgebras with structured state spaces. Coalgebra is an abstract framework for the uniform study of different kinds of dynamical systems. An endofunctor F determines both the type of systems (F-coalgebras) and a notion of behavioural equivalence (~_F) amongst them. Many types of transition systems and their equivalences can be captured by a functor F. For example, for deterministic automata the derived equivalence is language equivalence, while for non-deterministic automata it is ordinary bisimilarity. We give several examples of applications of our generalized determinization construction, including partial Mealy machines, (structured) Moore automata, Rabin probabilistic automata, and, somewhat surprisingly, even pushdown automata. To further witness the generality of the approach we show how to characterize coalgebraically several equivalences which have been object of interest in the concurrency community, such as failure or ready semantics.


    Volume: Volume 9, Issue 1
    Published on: March 4, 2013
    Imported on: October 25, 2011
    Keywords: Computer Science - Logic in Computer Science,F.3.2
    Funding:
      Source : OpenAIRE Graph
    • COINDUCTIVE CALCULI OF REGULAR BEHAVIOURS; Code: SFRH/BPD/71956/2010
    • CoRE: Coinductive Calculi of Regular Expressions; Funder: Netherlands Organisation for Scientific Research (NWO); Code: 612.063.920
    • Qais: Quantitative analysis of interacting systems: foundations and algorithms; Funder: Netherlands Organisation for Scientific Research (NWO); Code: PTDC/EIA-CCO/122240/2010

    35 Documents citing this article

    Consultation statistics

    This page has been seen 1378 times.
    This article's PDF has been downloaded 535 times.