Communication Dans Un Congrès
Année : 2015
Résumé
We construct a single Lindström quantifier Q such that FO(Q), the extension of first-order logic with Q has the same expressive power as monadic second-order logic on the class of binary trees (with distinct left and right successors) and also on unranked trees with a sibling order. This resolves a conjecture by ten Cate and Segoufin. The quantifier Q is a variation of a quantifier expressing the Boolean satisfiability problem.
Domaines
Informatique et langage [cs.CL]Origine | Fichiers produits par l'(les) auteur(s) |
---|
Loading...
Luc Segoufin : Connectez-vous pour contacter le contributeur
https://inria.hal.science/hal-01223378
Soumis le : lundi 2 novembre 2015-15:30:18
Dernière modification le : mercredi 4 septembre 2024-13:17:40
Archivage à long terme le : mercredi 3 février 2016-10:52:56
Citer
Anuj Dawar, Luc Segoufin. Capturing MSO with One Quantifier. Fields of Logic and Computation II - Essays Dedicated to Yuri Gurevich on the Occasion of His 75th Birthday., 2015, Berlin, Germany. ⟨10.1007/978-3-319-23534-9_8⟩. ⟨hal-01223378⟩
75
Consultations
134
Téléchargements