Session details: Automata column
Mikołaj Bojańczyk · ACM SIGLOG News · 2015
The foundational result of automata and logic is that regular languages of finite words are exactly those which can be defined in monadic second-order logic. For example, the language of words of even length is defined by a formula which says there exists a set X of positions that contains the first position but not the last one, and furthermore for each position x , the set X contains either x or its successor, but not both.