DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2010 · 58 citations · 16 references
ComputingComputer ScienceAlgorithmsDynamical SystemsFormal MethodsAutomata TheoryFinite AutomataFinite State Machine ModelingFinite-state MachinesType SystemsAutomata EquivalenceBehavioral EquivalenceEquivalence Of Transition SystemsLanguage EquivalenceMealy MachinesMoore MachinesProbabilistic AutomataTransition Systems
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.
16
Communicating sequential processes
C. A. R. Hoare · Communications of the ACM · 1983 · 3.8K citations · Full text
Notions of computation and monads
Eugenio Moggi · Information and Computation · 1991 · 1.7K citations
A Theory of Communicating Sequential Processes
Stephen Brookes, C. A. R. Hoare, A. W. Roscoe · Journal of the ACM · 1984 · 1.2K citations · Full text
Universal coalgebra: a theory of systems
J.J.M.M. Rutten · Theoretical Computer Science · 2000 · 1.2K citations
On the definition of a family of automata
M. P. Schützenberger · Information and Control · 1961 · 645 citations