Course Information

CS 713: Selected Topics in Automata and Logics

The course aims at giving an introduction to the theory of automata working on infinite words and infinite trees and connections thereof to logics. These automata and related logics are of fundamental importance in the areas of formal specification and verification of reactive systems. If time permits, we will also discuss some basic results in finite model theory. Below is a list of topics, which will be discussed in this course. Automata on finite words - equivalence of MSO and automata; Automata on infinite words – different acceptance conditions; Closure properties and equivalence of different acceptance conditions and related translations Determinization and complementation results; Equivalence of automata and MSO and decidability of MSO; Automata on infinite trees - different acceptance conditions; Closure properties and comparision of expressive power of different acceptance conditions and related translations Complementation result for tree automata via parity games; Equivalence of MSO and tree automata; Decidability of MSO over tress; Parity games and determinacy; Ehrenfeucht-Frasse games in logics and applications

Wolfgang Thomas: Automata on infinite objects, Handbook of theoretical computer science (vol B): formal methods and semantics, Elsevier.Wolfgang Thomas: Languages, automata, and logic, Handbook of formal languages, vol. 3: beyond words, Springer-Verlag.Dominique Perrin, Jean-Eric Pin: Infinite words, Elsevier.Erich Gradel, Wolfgang Thomas, Thomas Wilke: Automata, logics, and infinite games: a guide to current research. LNCS, Springer-Verlag.Leonid Libkin: Elements of finite model theory, Springer-Verlag.
Home Page

Not Available

Other Details

Duration : Full Semester Total Credit : 6
Type : Theory
Autumn Semester 2019-20

Status : Offered Instructor : Prof. Bharat Adsul
Spring Semester 2019-20

Status : Not Offered Instructor : ---

Last Modified Date: 15-Jul-2013


Faculty CSE IT
Forgot Password
    [+] Sitemap     Feedback