License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2010.272
URN: urn:nbn:de:0030-drops-28706
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2010/2870/
Go to the corresponding LIPIcs Volume Portal

Silva, Alexandra ; Bonchi, Filippo ; Bonsangue, Marcello M. ; Rutten, Jan J. M. M.

Generalizing the powerset construction, coalgebraically

pdf-format:
24.pdf (0.5 MB)

Abstract

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 behavioral
equivalence ($\sim_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. The powerset construction is a standard method for converting a nondeterministic automaton into an equivalent deterministic one as far as language is concerned. In this paper, we lift the powerset construction on automata to the more general framework of coalgebras with structured state spaces. Examples of applications include partial Mealy machines, (structured) Moore automata, and Rabin probabilistic automata.

BibTeX - Entry

@InProceedings{silva_et_al:LIPIcs:2010:2870,
  author =	{Alexandra Silva and Filippo Bonchi and Marcello M. Bonsangue and Jan J. M. M. Rutten},
  title =	{{Generalizing the powerset construction, coalgebraically}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)},
  pages =	{272--283},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-23-1},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{8},
  editor =	{Kamal Lodaya and Meena Mahajan},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2010/2870},
  URN =		{urn:nbn:de:0030-drops-28706},
  doi =		{10.4230/LIPIcs.FSTTCS.2010.272},
  annote =	{Keywords: coalgebra, language equivalence, bisimilarity, powerset construction}
}

Keywords: coalgebra, language equivalence, bisimilarity, powerset construction
Collection: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)
Issue Date: 2010
Date of publication: 14.12.2010

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI