1 Search Results for "Bonsangue, Marcello M."


Document
Generalizing the powerset construction, coalgebraically

Authors: Alexandra Silva, Filippo Bonchi, Marcello M. Bonsangue, and Jan J. M. M. Rutten

Published in: LIPIcs, Volume 8, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)


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.

Cite as

Alexandra Silva, Filippo Bonchi, Marcello M. Bonsangue, and Jan J. M. M. Rutten. Generalizing the powerset construction, coalgebraically. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). Leibniz International Proceedings in Informatics (LIPIcs), Volume 8, pp. 272-283, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)


Copy BibTex To Clipboard

@InProceedings{silva_et_al:LIPIcs.FSTTCS.2010.272,
  author =	{Silva, Alexandra and Bonchi, Filippo and Bonsangue, Marcello M. and Rutten, Jan J. M. M.},
  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 =	{Lodaya, Kamal and Mahajan, Meena},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2010.272},
  URN =		{urn:nbn:de:0030-drops-28706},
  doi =		{10.4230/LIPIcs.FSTTCS.2010.272},
  annote =	{Keywords: coalgebra, language equivalence, bisimilarity, powerset construction}
}
  • Refine by Author
  • 1 Bonchi, Filippo
  • 1 Bonsangue, Marcello M.
  • 1 Rutten, Jan J. M. M.
  • 1 Silva, Alexandra

  • Refine by Classification

  • Refine by Keyword
  • 1 bisimilarity
  • 1 coalgebra
  • 1 language equivalence
  • 1 powerset construction

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2010

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail