Alladi Ramakrishnan Hall

Languages over countable linear orderings

A V Sreejith

University of Warsaw

We look at words which are mappings from a linear ordering to a finite alphabet. Finite words, Omega words etc satisfy the above condition. There are also other interesting words.

We study the languages (of words) definable by different logics. We consider first-order logic, weak monadic second-order (WMSO) logic, two-variable fragments and a host of other logics. We are interested in the relationship between these logics. Are these logics expressively different? 

We will show that the above logics can be characterized by algebra. This is then used to answer interesting questions.