Hostname: page-component-cd9895bd7-lnqnp Total loading time: 0 Render date: 2024-12-17T19:08:03.529Z Has data issue: false hasContentIssue false
  • English
  • Français

Bisimilarity is not Borel†

Published online by Cambridge University Press:  09 December 2015

PEDRO SÁNCHEZ TERRAF
PEDRO SÁNCHEZ TERRAF*
Affiliation:
CIEM-FAMAF, Universidad Nacional de Córdoba, Medina Allende s/n (Ciudad Universitaria), X5000HUA – Córdoba, Argentina Email: [email protected] Algebraische und Logische Grundlagen der Informatik – Institut für Theoretische Informatik – Technische Universität Dresden – Fakultät Informatik – 01062 Dresden
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.

We prove that the relation of bisimilarity between countable labelled transition systems (LTS) is Σ11-complete (hence not Borel), by reducing the set of non-well orders over the natural numbers continuously to it.

This has an impact on the theory of probabilistic and non-deterministic processes over uncountable spaces, since logical characterizations of bisimilarity (as, for instance, those based on the unique structure theorem for analytic spaces) require a countable logic whose formulas have measurable semantics. Our reduction shows that such a logic does not exist in the case of image-infinite processes.

Type
Paper
Information
Mathematical Structures in Computer Science , Volume 27 , Special Issue 7: Special Issue: Coalgebraic Logic , October 2017 , pp. 1265 - 1284
Copyright
Copyright © Cambridge University Press 2015 

Footnotes

†

Partially supported by CONICET, ANPCyT project PICT 2012-1823, SeCyT-UNC project 05/B284, and EU 7FP grant agreement 295261 (MEALS). Part of this work was presented at Dagstuhl Seminar 12411 on Coalgebraic Logics.

References

Blackburn, P., Benthem, J.V. and Wolter, F. (2006). Handbook of Modal Logic, Studies in Logic and Practical Reasoning, volume 3, Elsevier Science Inc., New York, NY, USA.Google Scholar
Bolognesi, T. and Brinksma, E. (1987). Introduction to the ISO specification language LOTOS. Computer Networks 14 (1) 25–59.Google Scholar
Celayes, P. (2006). Procesos de Markov Etiquetados sobre Espacios de Borel Estándar, Master's thesis, FaMAF, Universidad Nacional de Córdoba.Google Scholar
Danos, V., Desharnais, J., Laviolette, F. and Panangaden, P. (2006). Bisimulation and cocongruence for probabilistic systems. Information and Computation 204 (4) 503–523.Google Scholar
D'Argenio, P., Wolovick, N., Sánchez Terraf, P. and Celayes, P. (2009). Nondeterministic labeled Markov processes: Bisimulations and logical characterization. In: QEST, IEEE Computer Society 11–20.Google Scholar
D'Argenio, P.R., Sánchez Terraf, P. and Wolovick, N. (2012). Bisimulations for non-deterministic labelled Markov processes. Mathematical Structures in Computer Science 22 (1) 43–68.Google Scholar
Desharnais, J. (1999). Labeled Markov Process, Ph.D. thesis, McGill University.Google Scholar
Desharnais, J., Edalat, A. and Panangaden, P. (2002). Bisimulation for labelled Markov processes. Information and Computation 179 (2) 163–193.Google Scholar
Desharnais, J., Laviolette, F. and Turgeon, A. (2011). A logical duality for underspecified probabilistic systems. Information and Computation 209 (5) 850–871.Google Scholar
Doberkat, E.E. (2005). Stochastic relations: Congruences, bisimulations and the Hennessy–Milner theorem. SIAM Journal on Computing 35 (3) 590–626.CrossRefGoogle Scholar
Doberkat, E.E. (2007a). Kleisli morphisms and randomized congruences for the Giry monad. Journal of Pure and Applied Algebra 211 (3) 638–664.Google Scholar
Doberkat, E.E. (2007b). Stochastic Relations: Foundations for Markov Transition Systems, Studies in Informatics Series, Chapman & Hall/CRC, Taylor & Francis.Google Scholar
Doberkat, E.E. (2009). Stochastic Coalgebraic Logic, Monographs in Theoretical Computer Science, Springer.Google Scholar
Edalat, A. (1999). Semi-pullbacks and bisimulation in categories of Markov processes. Mathematical Structures in Computer Science 9 (5) 523–543.CrossRefGoogle Scholar
Kechris, A.S. (1994). Classical Descriptive Set Theory, Graduate Texts in Mathematics, volume 156, Springer-Verlag.Google Scholar
Kechris, A.S. (2011). Classical descriptive set theory; corrections and updates. Available at http://www.math.caltech.edu/papers/CDST-corrections.pdf.Google Scholar
Kracht, M. (1999). Tools and Techniques in Modal Logic, Studies in Logic and the Foundations of Mathematics, Elsevier.Google Scholar
Larsen, K.G. and Skou, A. (1991). Bisimulation through probabilistic testing. Information and Computation 94 (1) 1–28.CrossRefGoogle Scholar
Moschovakis, Y.N. (2009). Descriptive Set Theory, 2nd edition, Mathematical Surveys and Monographs, American Mathematical Society.Google Scholar
Rutten, J.J.M.M. (2000). Universal coalgebra: A theory of systems. Theoretical Computer Science 249 (1) 3–80.CrossRefGoogle Scholar
Sánchez Terraf, P. (2011). Unprovability of the logical characterization of bisimulation. Information and Computation 209 (7) 1048–1056.Google Scholar
Scott, D. (1964). Invariant Borel sets. Fundamenta Mathematicae 56 (1) 117–128.Google Scholar
Srivastava, S.M., A Course on Borel Sets, Graduate Texts in Mathematics, volume 180, Springer.Google Scholar
Wolovick, N. (2012). Continuous Probability and Nondeterminism in Labeled Transition Systems, Ph.D. thesis, Universidad Nacional de Córdoba.Google Scholar