Bisimulational Categoricity

Speaker(s)

Jędrzej Kołodziejski

Affiliation

Uniwersytet Warszawski

Date

Jan. 23, 2019, 2:15 p.m.

Room

room 5050

Seminar

Seminar Automata Theory

---

The notion of bisimulation – which can be thought of as behavioral equivalence – is ubiquitous and in many contexts it appears more appropriate than isomorphism. Therefore, it is natural to introduce a notion of bisimulational categoricity – the property of having a unique model up to bisimulation, which is analogous to the well-studied notion of categoricity – the property of having a unique model up to isomorphism.

In the talk I will present a wide class of modal logics along with corresponding bisimilarity relations for which a nice characterization can be given: a complete modal theory t has a unique model up to bisimulation iff all models of t are finitely branching up to bisimulation.

Some corollaries of the theorem are:
A complete theory in the (standard) modal logic has a unique model up to (standard) bisimulation iff it has a finitely branching model.
A complete theory of the logic EF has a unique model up to EF-bisimulation iff it has a finite model.

 

---