KWIM & Logic Colloquium: The Interplay of Languages, Automata and Monadic Second-Order Logic

Time
Monday, 19. December 2022
15:15 - 16:30

Location
F426

Organizer
Prof. Dr. Salma Kuhlmann, Jun. Prof. Carolin Antos

Speaker:
Laura Wirth

A basic tool from Theoretical Computer Science for the specification of formal languages are finite automata. Research on the logical aspects of the theory of finite automata began in the early 1960s with the work of Buchi, Elgot and Trakhtenbrot on monadic second-order logic in the context of words. The basic idea of their approach is to use formulas of monadic second-order logic over a suitable signature to describe properties of words. Thus, monadic second-order logic provides another tool for the specification of languages. Buchi, Elgot and Trakhtenbrot independently derived that the two concepts – finite automata and monadic second-order logic – are even expressively equivalent. Hence, their equivalence result, referred to as Buchi-Elgot-Trakhtenbrot Theorem, establishes an early connection between Automata Theory and Mathematical Logic. In this talk, we provide an introduction to the above-mentioned concepts. Moreover, we present an extension of the Buchi-Elgot Trakhtenbrot Theorem to formulas, involving free variables, whereas the original statement addresses only sentences. If time permits, we will further outline quantitative extensions of the above-mentioned concepts and results.

Remark: before the talk at 14:45 there will be a KWIM coffee round. Everyone is kindly invited to attend!