- Fragments of fixpoint logics: Automata and expressiveness
- Award date
- 11 December 2015
- Number of pages
- Document type
- PhD thesis
- Interfacultary Research Institutes
- Institute for Logic, Language and Computation (ILLC)
This dissertation studies the relative expressive power and properties of several fixpoint and second-order logics. We use the term fixpoint logic in a broad sense, referring to any logic which can encode some type of recursion, iteration or repetition.
Our main objective is to systematically identify several important logics as precise fragments of other well-known logics. In order to accomplish this task, we develop automata-theoretic tools to analyze these fragments. The results of this dissertation provide new insight on the relationship of fixpoint and second-order logic and provides further evidence of the successful logic-automata connection.
- Research conducted at: Universiteit van Amsterdam
Series: ILLC dissertation series DS-2015-05