{"id":"arxiv/2604.06443","url":"https://arxiv.org/abs/2604.06443","tags":["cs.LO","math.LO"],"score":0,"title":"The complexity of bisimilarity on pointmass processes","domain":"cs.LO","source":"arxiv","authors":["Martín Santiago Moroni","Pedro Sánchez Terraf"],"reviews":0,"subject":"cs.LO","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-04-07","reactions":{}}