MSc THESIS DEFENSE
11:30 am - 12 noon, Lecture hall 5
Playing with repetitions in data words
Anirban Majumdar
Chennai Mathematical Institute.
14-06-18

---

Abstract

We study two-player games which build words over infinite alphabets, and we study the problem of checking the existence of winning strategies. These games are played by two players, who take turns in choosing valuations for variables ranging over an infinite data domain, thus generating multi-attributed data words. The winner of the game is specified by formulas in the Logic of Repeating Values, which can reason about repetitions of data values in infinite data words. It is known that checking whether one of the players has a winning strategy is undecidable in general and becomes decidable under some restrictions. Existing works do not address the case where the logic of repeating values can use nested formulas. We study this scenario and determine that decidability depends on whether or not nested formulas can refer to the future.