Hostname: page-component-586b7cd67f-tf8b9 Total loading time: 0 Render date: 2024-11-23T22:56:58.414Z Has data issue: false hasContentIssue false
  • English
  • Français

A coalgebraic view on decorated traces

Published online by Cambridge University Press:  03 December 2014

F. BONCHI ,
M. BONSANGUE ,
G. CALTAIS ,
J. RUTTEN  and
A. SILVA
F. BONCHI
Affiliation:
ENS Lyon, Université de Lyon, LIP (UMR 5668 CNRS ENS Lyon UCBL INRIA), Lyon, France
M. BONSANGUE
Affiliation:
LIACS - Leiden University, Leiden, The Netherlands Centrum voor Wiskunde en Informatica, Amsterdam, The Netherlands
G. CALTAIS
Affiliation:
Centrum voor Wiskunde en Informatica, Amsterdam, The Netherlands School of Computer Science - Reykjavik University, Reykjavik, Iceland
J. RUTTEN
Affiliation:
Centrum voor Wiskunde en Informatica, Amsterdam, The Netherlands Radboud University, Nijmegen, The Netherlands
A. SILVA
Affiliation:
Centrum voor Wiskunde en Informatica, Amsterdam, The Netherlands Radboud University, Nijmegen, The Netherlands HASLab/INESC TEC, Universidade do Minho, Braga, Portugal
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

In the concurrency theory, various semantic equivalences on transition systems are based on traces decorated with some additional observations, generally referred to as decorated traces. Using the generalized powerset construction, recently introduced by a subset of the authors (Silva et al.2010 FSTTCS. LIPIcs8 272–283), we give a coalgebraic presentation of decorated trace semantics. The latter include ready, failure, (complete) trace, possible futures, ready trace and failure trace semantics for labelled transition systems, and ready, (maximal) failure and (maximal) trace semantics for generative probabilistic systems. This yields a uniform notion of minimal representatives for the various decorated trace equivalences, in terms of final Moore automata. As a consequence, proofs of decorated trace equivalence can be given by coinduction, using different types of (Moore-) bisimulation (up-to context).

Type
Paper
Information
Mathematical Structures in Computer Science , Volume 26 , Issue 7 , October 2016 , pp. 1234 - 1268
Copyright
Copyright © Cambridge University Press 2014 

References

Aceto, L., Fokkink, W. and Verhoef, C. (1999) Structural operational semantics. In: Handbook of Process Algebra, Elsevier 197–292.Google Scholar
Awodey, S. (2010) Category theory, Oxford Logic Guides, Oxford University Press.Google Scholar
Bartels, F. (2004) On Generalised Coinduction and Probabilistic Specification Formats, Ph.D. thesis, CWI, Amsterdam.Google Scholar
Bartels, F., Sokolova, A. and de Vink, E. P. (2004) A hierarchy of probabilistic system types. Theoretical Computer Science 327 (1–2) 3–22.Google Scholar
Bonchi, F., Bonsangue, M. M., Caltais, G., Rutten, J. J. M. M. and Silva, A. (2012) Final semantics for decorated traces. Electronic Notes in Theoretical Computer Science 286 73–86.CrossRefGoogle Scholar
Bonchi, F., Caltais, G., Pous, D. and Silva, A. (2013) Brzozowski's and up-to algorithms for must testing. In: Chieh Shan, C. (ed.) Asian Symposium on Programming Languages and Systems. Springer Lecture Notes in Computer Science 8301 1–16.Google Scholar
Bonchi, F. and Pous, D. (2013) Checking NFA equivalence with bisimulations up to congruence. In: Giacobazzi, R. and Cousot, R. (eds.) Principles of Programming Languages, ACM 457–468.Google Scholar
Boreale, M. and Gadducci, F. (2006) Processes as formal power series: A coinductive approach to denotational semantics. Theoretical Computer Science 360 (1–3) 440–458.Google Scholar
Cancila, D., Honsell, F. and Lenisa, M. (2003) Generalized coiteration schemata. Electronic Notes in Theoretical Computer Science 82 (1) 79–93.Google Scholar
Cleaveland, R. and Hennessy, M. (1993) Testing equivalence as a bisimulation equivalence. Formal Aspects of Computing 5 (1) 1–20.Google Scholar
Doberkat, E.-E. (2008) Erratum and addendum: Eilenberg–Moore algebras for stochastic relations. Information and Computation 206 (12) 1476–1484.Google Scholar
Hasuo, I., Jacobs, B. and Sokolova, A. (2007) Generic trace semantics via coinduction. Logical Methods in Computer Science 3 (4).Google Scholar
Hennessy, M. and Milner, R. (1985) Algebraic laws for nondeterminism and concurrency. Journal of the ACM 32 (1) 137–161.CrossRefGoogle Scholar
Jou, C.-C. and Smolka, S. (1990) Equivalences, congruences, and complete axiomatizations for probabilistic processes. In: Baeten, J. and Klop, J. (eds.) International conference on concurrency theory Theories of Concurrency: Unification and Extension. Springer Lecture Notes in Computer Science 458, 367–383.CrossRefGoogle Scholar
Lenisa, M. (1999) From set-theoretic coinduction to coalgebraic coinduction: Some results, some problems. Electronic Notes in Theoretical Computer Science 19 2–22.Google Scholar
Lenisa, M., Power, J. and Watanabe, H. (2000) Distributivity for endofunctors, pointed and co-pointed endofunctors, monads and comonads. Electronic Notes in Theoretical Computer Science 33 230–260.Google Scholar
Milner, R. (1989) Communication and Concurrency, Prentice Hall.Google Scholar
Monteiro, L. (2008) A coalgebraic characterization of behaviours in the linear time – branching time spectrum. In: Corradini, A. and Montanari, U. (eds.) Workshop on Algebraic Development Techniques. Springer Lecture Notes in Computer Science 5486 251–265.Google Scholar
Park, D. M. R. (1981) Concurrency and automata on infinite sequences. In: Deussen, P. (ed.) Theoretical Computer Science. Springer Lecture Notes in Computer Science 104 167–183.Google Scholar
Rot, J., Bonsangue, M. M. and Rutten, J. J. M. M. (2013) Coalgebraic bisimulation-up-to. In: van Emde Boas, P., Groen, F. C. A., Italiano, G. F., Nawrocki, J. R. and Sack, H. (eds.) SOFtware SEMinar. Springer Lecture Notes in Computer Science 7741 369–381.Google Scholar
Rosu, G. and Lucanu, D. (2009) Circular coinduction: A proof theoretical foundation. In: Conference on Algebra and Coalgebra in Computer Science, 127–144.Google Scholar
Rutten, J. J. M. M. (2000) Universal coalgebra: A theory of systems. Theoretical Computer Science 249 (1) 3–80.Google Scholar
Sangiorgi, D. and Rutten, J. (2011) Advanced Topics in Bisimulation and Coinduction, Cambridge Tracts in Theoretical Computer Science, Cambridge University Press.CrossRefGoogle Scholar
Silva, A., Bonchi, F., Bonsangue, M. M. and Rutten, J. J. M. M. (2010) Generalizing the powerset construction, coalgebraically. In: Lodaya, K. and Mahajan, M. (eds.), Conference of Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics 8 272–283.Google Scholar
Silva, A., Bonchi, F., Bonsangue, M. M. and Rutten, J. J. M. M. (2013) Generalizing determinization from automata to coalgebras. Logical Methods in Computer Science 9 (1).Google Scholar
van Glabbeek, R. (2001) The linear time – branching time spectrum I. The semantics of concrete, sequential processes. In: Bergstra, J., Ponse, A. and Smolka, S. (eds.) Handbook of Process Algebra, Elsevier 3–99.Google Scholar