@inproceedings{baez_operads_2015,
title = {Operads and {Phylogenetic} {Trees}},
abstract = {We construct an operad \${\textbackslash}mathrm\{Phyl\}\$ whose operations are the edge-labelled trees used in phylogenetics. This operad is the coproduct of \${\textbackslash}mathrm\{Com\}\$, the operad for commutative semigroups, and \$[0,{\textbackslash}infty)\$, the operad with unary operations corresponding to nonnegative real numbers, where composition is addition. We show that there is a homeomorphism between the space of \$n\$-ary operations of \${\textbackslash}mathrm\{Phyl\}\$ and \${\textbackslash}mathcal\{T\}\_n{\textbackslash}times [0,{\textbackslash}infty){\textasciicircum}\{n+1\}\$, where \${\textbackslash}mathcal\{T\}\_n\$ is the space of metric \$n\$-trees introduced by Billera, Holmes and Vogtmann. Furthermore, we show that the Markov models used to reconstruct phylogenetic trees from genome data give coalgebras of \${\textbackslash}mathrm\{Phyl\}\$. These always extend to coalgebras of the larger operad \${\textbackslash}mathrm\{Com\} + [0,{\textbackslash}infty]\$, since Markov processes on finite sets converge to an equilibrium as time approaches infinity. We show that for any operad \$O\$, its coproduct with \$[0,{\textbackslash}infty]\$ contains the operad \$W(O)\$ constucted by Boardman and Vogt. To prove these results, we explicitly describe the coproduct of operads in terms of labelled trees.},
author = {Baez, John C. and Otter, Nina},
year = {2015},
note = {ZSCC: NoCitationData[s1]
arXiv: 1512.03337},
keywords = {Biology, Coalgebras}
}
@article{sokolova_probabilistic_2011,
title = {Probabilistic systems coalgebraically: {A} survey},
volume = {412},
issn = {0304-3975},
shorttitle = {Probabilistic systems coalgebraically},
url = {https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3185909/},
doi = {10/frbx24},
abstract = {We survey the work on both discrete and continuous-space probabilistic systems as coalgebras, starting with how probabilistic systems are modeled as coalgebras and followed by a discussion of their bisimilarity and behavioral equivalence, mentioning results that follow from the coalgebraic treatment of probabilistic systems. It is interesting to note that, for different reasons, for both discrete and continuous probabilistic systems it may be more convenient to work with behavioral equivalence than with bisimilarity.},
number = {38},
urldate = {2019-11-26},
journal = {Theoretical Computer Science},
author = {Sokolova, Ana},
month = sep,
year = {2011},
pmid = {21998490},
pmcid = {PMC3185909},
note = {ZSCC: 0000057 },
keywords = {Coalgebras, Probabilistic transition systems, Transition systems},
pages = {5095--5110}
}
@article{van_breugel_domain_2005,
series = {Foundations of {Software} {Science} and {Computation} {Structures}},
title = {Domain theory, testing and simulation for labelled {Markov} processes},
volume = {333},
issn = {0304-3975},
url = {http://www.sciencedirect.com/science/article/pii/S030439750400711X},
doi = {10/ft9vc5},
abstract = {This paper presents a fundamental study of similarity and bisimilarity for labelled Markov processes (LMPs). The main results characterize similarity as a testing preorder and bisimilarity as a testing equivalence. In general, LMPs are not required to satisfy a finite-branching condition—indeed the state space may be a continuum, with the transitions given by arbitrary probability measures. Nevertheless we show that to characterize bisimilarity it suffices to use finitely-branching labelled trees as tests. Our results involve an interaction between domain theory and measure theory. One of the main technical contributions is to show that a final object in a suitable category of LMPs can be constructed by solving a domain equation D≅V(D)Act, where V is the probabilistic powerdomain. Given an LMP whose state space is an analytic space, bisimilarity arises as the kernel of the unique map to the final LMP. We also show that the metric for approximate bisimilarity introduced by Desharnais, Gupta, Jagadeesan and Panangaden generates the Lawson topology on the domain D.},
language = {en},
number = {1},
urldate = {2019-11-26},
journal = {Theoretical Computer Science},
author = {van Breugel, Franck and Mislove, Michael and Ouaknine, Joël and Worrell, James},
month = mar,
year = {2005},
note = {ZSCC: 0000058},
keywords = {Coalgebras, Denotational semantics, Probabilistic transition systems, Transition systems},
pages = {171--197}
}
@incollection{goos_probabilistic_2004,
address = {Berlin, Heidelberg},
title = {Probabilistic {Automata}: {System} {Types}, {Parallel} {Composition} and {Comparison}},
volume = {2925},
isbn = {978-3-540-22265-1 978-3-540-24611-4},
shorttitle = {Probabilistic {Automata}},
url = {http://link.springer.com/10.1007/978-3-540-24611-4_1},
abstract = {We survey various notions of probabilistic automata and probabilistic bisimulation, accumulating in an expressiveness hierarchy of probabilistic system types. The aim of this paper is twofold: On the one hand it provides an overview of existing types of probabilistic systems and, on the other hand, it explains the relationship between these models. We overview probabilistic systems with discrete probabilities only. The expressiveness order used to built the hierarchy is deﬁned via the existence of mappings between the corresponding system types that preserve and reﬂect bisimilarity. Additionally, we discuss parallel composition for the presented types of systems, augmenting the map of probabilistic automata with closedness under this compositional operator.},
language = {en},
urldate = {2019-11-28},
booktitle = {Validation of {Stochastic} {Systems}},
publisher = {Springer Berlin Heidelberg},
author = {Sokolova, Ana and de Vink, Erik P.},
editor = {Goos, Gerhard and Hartmanis, Juris and van Leeuwen, Jan and Baier, Christel and Haverkort, Boudewijn R. and Hermanns, Holger and Katoen, Joost-Pieter and Siegle, Markus},
year = {2004},
doi = {10.1007/978-3-540-24611-4_1},
note = {ZSCC: NoCitationData[s1] },
keywords = {Coalgebras, Probabilistic transition systems, Transition systems},
pages = {1--43}
}
@article{bartels_hierarchy_2003,
series = {{CMCS}'03, {Coalgebraic} {Methods} in {Computer} {Science} ({Satellite} {Event} for {ETAPS} 2003)},
title = {A hierarchy of probabilistic system types},
volume = {82},
issn = {1571-0661},
url = {http://www.sciencedirect.com/science/article/pii/S1571066104806327},
doi = {10/d7kq38},
abstract = {We arrange various types of probabilistic transition systems studied in the literature in an expressiveness hierarchy. The expressiveness criterion is the existence of an embedding of systems of the one class into those of the other. An embedding here is a system transformation which preserves and reflects bisimilarity. To facilitate the task, we define the classes of systems and the corresponding notion of bisimilarity coalgebraically and use the new technical result that an embedding arises from a natural transformation with injective components between the two coalgebra functors under consideration. Moreover, we argue that coalgebraic bisimilarity, on which we base our results, coincides with the concrete notions proposed in the literature for the different system classes, exemplified by a detailed proof for the case of general Segala-type systems.},
language = {en},
number = {1},
urldate = {2019-11-26},
journal = {Electronic Notes in Theoretical Computer Science},
author = {Bartels, Falk and Sokolova, Ana and de Vink, Erik},
month = jul,
year = {2003},
note = {ZSCC: 0000049},
keywords = {Coalgebras, Probabilistic transition systems, Transition systems},
pages = {57--75}
}
@article{desharnais_bisimulation_2002,
title = {Bisimulation for {Labelled} {Markov} {Processes}},
volume = {179},
issn = {0890-5401},
url = {http://www.sciencedirect.com/science/article/pii/S0890540101929621},
doi = {10/fmp9vd},
abstract = {In this paper we introduce a new class of labelled transition systems—labelled Markov processes— and define bisimulation for them. Labelled Markov processes are probabilistic labelled transition systems where the state space is not necessarily discrete. We assume that the state space is a certain type of common metric space called an analytic space. We show that our definition of probabilistic bisimulation generalizes the Larsen–Skou definition given for discrete systems. The formalism and mathematics is substantially different from the usual treatment of probabilistic process algebra. The main technical contribution of the paper is a logical characterization of probabilistic bisimulation. This study revealed some unexpected results, even for discrete probabilistic systems. •Bisimulation can be characterized by a very weak modal logic. The most striking feature is that one has no negation or any kind of negative proposition.•We do not need any finite branching assumption, yet there is no need of infinitary conjunction. We also show how to construct the maximal autobisimulation on a system. In the finite state case, this is just a state minimization construction. The proofs that we give are of an entirely different character than the typical proofs of these results. They use quite subtle facts about analytic spaces and appear, at first sight, to be entirely nonconstructive. Yet one can give an algorithm for deciding bisimilarity of finite state systems which constructs a formula that witnesses the failure of bisimulation.},
language = {en},
number = {2},
urldate = {2019-11-26},
journal = {Information and Computation},
author = {Desharnais, Josée and Edalat, Abbas and Panangaden, Prakash},
month = dec,
year = {2002},
note = {ZSCC: 0000297},
keywords = {Coalgebras, Denotational semantics, Probabilistic transition systems, Symbolic logic, Transition systems},
pages = {163--193}
}
@article{rutten_universal_2000,
series = {Modern {Algebra}},
title = {Universal coalgebra: a theory of systems},
volume = {249},
issn = {0304-3975},
shorttitle = {Universal coalgebra},
url = {http://www.sciencedirect.com/science/article/pii/S0304397500000566},
doi = {10/fqrjpn},
abstract = {In the semantics of programming, finite data types such as finite lists, have traditionally been modelled by initial algebras. Later final coalgebras were used in order to deal with infinite data types. Coalgebras, which are the dual of algebras, turned out to be suited, moreover, as models for certain types of automata and more generally, for (transition and dynamical) systems. An important property of initial algebras is that they satisfy the familiar principle of induction. Such a principle was missing for coalgebras until the work of Aczel (Non-Well-Founded sets, CSLI Leethre Notes, Vol. 14, center for the study of Languages and information, Stanford, 1988) on a theory of non-wellfounded sets, in which he introduced a proof principle nowadays called coinduction. It was formulated in terms of bisimulation, a notion originally stemming from the world of concurrent programming languages. Using the notion of coalgebra homomorphism, the definition of bisimulation on coalgebras can be shown to be formally dual to that of congruence on algebras. Thus, the three basic notions of universal algebra: algebra, homomorphism of algebras, and congruence, turn out to correspond to coalgebra, homomorphism of coalgebras, and bisimulation, respectively. In this paper, the latter are taken as the basic ingredients of a theory called universal coalgebra. Some standard results from universal algebra are reformulated (using the aforementioned correspondence) and proved for a large class of coalgebras, leading to a series of results on, e.g., the lattices of subcoalgebras and bisimulations, simple coalgebras and coinduction, and a covariety theorem for coalgebras similar to Birkhoff's variety theorem.},
language = {en},
number = {1},
urldate = {2019-11-26},
journal = {Theoretical Computer Science},
author = {Rutten, J. J. M. M.},
month = oct,
year = {2000},
note = {ZSCC: 0001448},
keywords = {Coalgebras, Transition systems},
pages = {3--80}
}
@inproceedings{de_vink_bisimulation_1997,
address = {Berlin, Heidelberg},
series = {Lecture {Notes} in {Computer} {Science}},
title = {Bisimulation for probabilistic transition systems: {A} coalgebraic approach},
isbn = {978-3-540-69194-5},
shorttitle = {Bisimulation for probabilistic transition systems},
doi = {10/fcqzmk},
abstract = {The notion of bisimulation as proposed by Larsen and Skou for discrete probabilistic transition systems is shown to coincide with a coalgebraic definition in the sense of Aczel and Mendier in terms of a set functor. This coalgebraic formulation makes it possible to generalize the concepts to a continuous setting involving Borel probability measures. Under reasonable conditions, generalized probabilistic bisimilarity can be characterized categorically. Application of the final coalgebra paradigm then yields an internally fully abstract semantical domain with respect to probabilistic bisimulation.},
language = {en},
booktitle = {Automata, {Languages} and {Programming}},
publisher = {Springer},
author = {de Vink, E. P. and Rutten, J. J. M. M.},
editor = {Degano, Pierpaolo and Gorrieri, Roberto and Marchetti-Spaccamela, Alberto},
year = {1997},
note = {ZSCC: NoCitationData[s1]},
keywords = {Categorical probability theory, Coalgebras, Denotational semantics, Probabilistic transition systems, Transition systems},
pages = {460--470}
}