MSc Thesis Defence
10.00 am, Lecture Hall 2
A logic for synchronous relations
Varun Ramanathan
Chennai Mathematical Institute.
16-05-18

---

Abstract

Synchronous relations are relations on words defined by multi-tape automata that run synchronously. It is known that these relations can be characterized logically by first order formulae on words with prefix, equal length and last letter predicates. We will prove that the logic collapses to its $\Sigma_3$ fragment, and we will characterize binary relations definable in the $\Sigma_1$ fragment. We will also prove that the membership problem for $\Sigma_1$-definable relations is decidable. If time permits, then we will talk about the characterization of relations definable in the $B\Sigma_1$ fragment.