|
Informatics Report Series
|
|
|
|
|
|
|
|
|
| Title:The complexity of independence-friendly fixpoint logic |
| Authors:
Julian Bradfield
; Stephan Kreutzer
|
| Date: 2005 |
| Publication Title:19th International Workshop, CSL 2005, 14th Annual Conference of the EACSL, Oxford, UK, August 22-25, 2005. Proceedings |
| Publisher:Springer |
|
Publication Type:Conference Paper
Publication Status:Published
|
|
Volume No:3634
Page Nos:355-368
|
|
DOI:10.1007/11538363
ISBN/ISSN:0302-9743
|
- Abstract:
-
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).
- Links To Paper
- Preprint of the to-be-published version
- Bibtex format
- @InProceedings{EDI-INF-RR-0555,
- author = {
Julian Bradfield
and Stephan Kreutzer
},
- title = {The complexity of independence-friendly fixpoint logic},
- book title = {19th International Workshop, CSL 2005, 14th Annual Conference of the EACSL, Oxford, UK, August 22-25, 2005. Proceedings},
- publisher = {Springer},
- year = 2005,
- volume = {3634},
- pages = {355-368},
- doi = {10.1007/11538363},
- url = {http://www.inf.ed.ac.uk/~jcb/Research/iflfpcomplex.ps.gz},
- }
|
