Pure and applied fixed point logics [Elektronische Ressource] / vorgelegt von Stephan Kreutzer

Pure and AppliedFixed-Point LogicsVon der Fakult at fur Mathematik, Informatik undNaturwissenschaften der Rheinisch-Westf alischen TechnischenHochschule Aachen zur Erlangung des akademischen Grades einesDoktors der Naturwissenschaften genehmigte Dissertationvorgelegt vonDiplom-InformatikerStephan Kreutzeraus Aachen, DeutschlandBerichter: Universit atsprofessor Dr. Erich Gr adelUniversit Dr. Wolfgang ThomasTag der mundlic hen Prufung: 17.12.2002Diese Dissertation ist auf den Internetseiten der Hochschulbibliothek online verfugbar.23AbstractFixed-point logics are logics with an explicit operator for forming xed pointsof de nable mappings. They are particularly well suited for modelling recur-sion in logical languages and consequently they have found applications invarious areas of theoretical computer science such as database theory, nitemodel theory, and computer-aided veri cation.The topic of this thesis is the study of xed-p oint logics with respect totheir expressive power. Of particular interest are logics based on in ationary xed points and their comparison to least xed-p oint logics.The rst part focuses on xed-p oint extensions of rst-order logic. Inthe main result we show that in ationary and least xe d-point logic { theextensions of rst-order logic by least and in ationary xed points { havethe same expressive power on all structures, i.e. LFP = IFP.In the second part of this thesis, we study xed-p oint extensions of modallogic.