Bisimilarity is not Borel
| Title | Bisimilarity is not Borel |
| Publication Type | Journal Article |
| Year of Publication | In Press |
| Authors | Sánchez Terraf, P |
| Journal | Mathematical Structures in Computer Science |
| Abstract | We prove that the relation of bisimilarity between countable labelled transition systems is Σ11-complete (hence not Borel), by reducing the set of non-wellorders over the natural numbers continuously to it. This has an impact on the theory of probabilistic and nondeterministic 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. |
Work Package:
WP1
