ACM/IEEE Symposium on Logic in Computer Science

LICS Home - LICS Awards - LICS Newsletters - LICS Archive - LICS Organization - Logic-Related Conferences - Links

Thirteenth Annual IEEE Symposium on

Logic in Computer Science (LICS 1998)

Invited Paper: Monadic Logic and Automata: Recent Developments (at LICS 1998)

Authors: Wolfgang Thomas


This tutorial surveys selected recent results on the connection between monadic second-order logic and finite automata. As a unifying idea, the role of automata as normal forms of monadic formulas is pursued. In the first part we start from an automata-theoretic interpretation of existential monadic second-order formulas and in this framework explain the monadic quantifier alternation hierarchy over finite graphs. In the second part, infinite models, in particular ?-words, are considered. We analyze the logical significance of central constructions in ?-automata theory and sketch new proofs of decidability results in monadic second-order logic


    author = 	 {Wolfgang Thomas},
    title = 	 {Monadic Logic and Automata: Recent Developments},
    booktitle =  {Proceedings of the Thirteenth Annual IEEE Symposium on Logic in Computer Science (LICS 1998)},
    year =	 {1998},
    month =	 {June}, 
    pages =      {136--138},
    location =   {Indianapolis, IN, USA}, 
    note =       {Invited Talk},
    publisher =	 {IEEE Computer Society Press}

Last modified: 2022-10-3113:49
Sam Staton