INVESTIGADORES
SANCHEZ TERRAF Pedro Octavio
artículos
Título:
Bisimilarity is not Borel
Autor/es:
PEDRO SÁNCHEZ TERRAF
Revista:
MATHEMATICAL STRUCTURES IN COMPUTER SCIENCE
Editorial:
CAMBRIDGE UNIV PRESS
Referencias:
Lugar: Cambridge; Año: 2017 vol. 27 p. 1265 - 1284
ISSN:
0960-1295
Resumen:
We prove that the relation of bisimilarity between countable labelled transitionsystems is Sigma^1_1-complete (hence not Borel), by reducing the set of non-wellordersover the natural numbers continuously to it.This has an impact on the theory of probabilistic and nondeterministic processesover uncountable spaces, since the proofs of logical characterizations of bisimilaritybased on the unique structure theorem for analytic spaces require a countable logicwhose formulas have measurable semantics. Our reduction shows that such a logicdoes not exist in the case of image-infinite processes.
