The complexity of bisimilarity on pointmass processes
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866915921894834176 |
|---|---|
| author | Moroni, Martín Santiago Terraf, Pedro Sánchez |
| author_facet | Moroni, Martín Santiago Terraf, Pedro Sánchez |
| contents | We assess the descriptive complexity of *bisimilarity* or "equality of behavior" on a family of Markov decision processes over uncountable standard Borel spaces, namely *nondeterministic labelled Markov processes* (NLMP).
We show that bisimilarity is analytic for processes with a uniform assignment of finitely-supported measures to each state and label. More finely, we obtain that bisimilarity on the space of countable Kripke frames (or labelled transition systems) is classifiable by countable structures.
We show that bisimilarity of well-founded ("terminating") processes is Borel. We also provide a lower complexity bound by reducing the relation of eventual equality of binary sequences $E_0$ to the former. As a consequence, there is no countable fragment of basic modal logic with denumerable conjunctions that characterizes bisimilarity for processes of small rank.
We finally apply the previous Borel definability to study the well-founded part of discrete uniform processes over uncountable spaces. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_06443 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | The complexity of bisimilarity on pointmass processes Moroni, Martín Santiago Terraf, Pedro Sánchez Logic in Computer Science Logic 68Q85 (Primary) 03E15, 60Jxx, 28A05 (Secondary) F.4.1 We assess the descriptive complexity of *bisimilarity* or "equality of behavior" on a family of Markov decision processes over uncountable standard Borel spaces, namely *nondeterministic labelled Markov processes* (NLMP). We show that bisimilarity is analytic for processes with a uniform assignment of finitely-supported measures to each state and label. More finely, we obtain that bisimilarity on the space of countable Kripke frames (or labelled transition systems) is classifiable by countable structures. We show that bisimilarity of well-founded ("terminating") processes is Borel. We also provide a lower complexity bound by reducing the relation of eventual equality of binary sequences $E_0$ to the former. As a consequence, there is no countable fragment of basic modal logic with denumerable conjunctions that characterizes bisimilarity for processes of small rank. We finally apply the previous Borel definability to study the well-founded part of discrete uniform processes over uncountable spaces. |
| title | The complexity of bisimilarity on pointmass processes |
| topic | Logic in Computer Science Logic 68Q85 (Primary) 03E15, 60Jxx, 28A05 (Secondary) F.4.1 |
| url | https://arxiv.org/abs/2604.06443 |