Capturing Bisimulation-Invariant Complexity Classes with Higher-Order Modal Fixpoint Logic

Abstract : Polyadic Higher-Order Fixpoint Logic (PHFL) is a modal fixpoint logic obtained as the merger of Higher-Order Fixpoint Logic (HFL) and the Polyadic μ-Calculus. Polyadicity enables formulas to make assertions about tuples of states rather than states only. Like HFL, PHFL has the ability to formalise properties using higher-order functions. We consider PHFL in the setting of descriptive complexity theory: its fragment using no functions of higher-order is exactly the Polyadic μ-Calculus, and it is known from Otto’s Theorem that it captures the bisimulation-invariant fragment of PTIME. We extend this and give capturing results for the bisimulation-invariant fragments of EXPTIME, PSPACE, and NLOGSPACE.
Type de document :
Communication dans un congrès
Josep Diaz; Ivan Lanese; Davide Sangiorgi. 8th IFIP International Conference on Theoretical Computer Science (TCS), Sep 2014, Rome, Italy. Springer, Lecture Notes in Computer Science, LNCS-8705, pp.90-103, 2014, Theoretical Computer Science. 〈10.1007/978-3-662-44602-7_8〉
Liste complète des métadonnées

Littérature citée [20 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01402031
Contributeur : Hal Ifip <>
Soumis le : jeudi 24 novembre 2016 - 10:48:52
Dernière modification le : jeudi 24 novembre 2016 - 11:14:11
Document(s) archivé(s) le : mardi 21 mars 2017 - 08:36:28

Fichier

978-3-662-44602-7_8_Chapter.pd...
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Martin Lange, Etienne Lozes. Capturing Bisimulation-Invariant Complexity Classes with Higher-Order Modal Fixpoint Logic. Josep Diaz; Ivan Lanese; Davide Sangiorgi. 8th IFIP International Conference on Theoretical Computer Science (TCS), Sep 2014, Rome, Italy. Springer, Lecture Notes in Computer Science, LNCS-8705, pp.90-103, 2014, Theoretical Computer Science. 〈10.1007/978-3-662-44602-7_8〉. 〈hal-01402031〉

Partager

Métriques

Consultations de la notice

12

Téléchargements de fichiers

3