2026-07-20T11:46:00Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:2870 2024-03-06T10:33:39Z ddc:004 open_access

Generalizing the powerset construction, coalgebraically Silva, Alexandra Bonchi, Filippo Bonsangue, Marcello M. Rutten, Jan J. M. M. coalgebra language equivalence bisimilarity powerset construction 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Alexandra Silva and Filippo Bonchi and Marcello M. Bonsangue and Jan J. M. M. Rutten 2010 Is Part Of LIPIcs, Volume 8, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2010.272 urn:nbn:de:0030-drops-28706 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2010.272 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode