Hall 123

Block products for algebras over countable words

A V Sreejith

IIT Goa

We look at words which are mappings from a countable linear ordering to a finite alphabet. Finite words, Omega words etc satisfy the above condition. In this talk, we study the languages (of words) definable by different logics. We consider monadic second order logic, first order logic, linear temporal logic etc.

These logics can be characterized by an algebra called o-algebra and its subclasses. We first present a block product principle. Building on this, we generalize the well-known algebraic characterizations of first-order logic (resp. first-order logic with two variables) in terms of strongly (resp. weakly) iterated block products. We also explicate the role of block products for linear temporal logic by formulating a novel algebraic characterization of a natural fragment.


(**** Please note the unusual venue: Room 123 ****)