The complexity of independence-friendly fixpoint logic

Julian Bradfield, Stephan Kreutzer

Research output: Chapter in Book/Report/Conference proceedingChapter (peer-reviewed)


We study the complexity of model-checking for the fixpoint extension of Hintikka and Sandu's independence-friendly logic. We show that this logic captures EXPTIME; and by embedding PFP, we show that its combined complexity is EXPSPACE-hard, and moreover the logic includes second order logic (on finite structures).
Original languageEnglish
Title of host publicationFoundations of the Formal Sciences V, Infinite Games
EditorsStefan Bold, Benedikt Löwe, Thoralf Räsch, Johan van Benthem
Place of PublicationLondon
PublisherCollege Publications
ISBN (Print)978-1904987758
Publication statusPublished - 2007

Publication series

NameStudies in Logic


Dive into the research topics of 'The complexity of independence-friendly fixpoint logic'. Together they form a unique fingerprint.

Cite this