Hostname: page-component-78c5997874-dh8gc Total loading time: 0 Render date: 2024-11-12T22:28:14.015Z Has data issue: false hasContentIssue false
  • English
  • Français

DICHOTOMY RESULT FOR INDEPENDENCE-FRIENDLY PREFIXES OF GENERALIZED QUANTIFIERS

Published online by Cambridge University Press:  12 December 2014

MERLIJN SEVENSTER
MERLIJN SEVENSTER*
Affiliation:
PHILIPS RESEARCH NORTH AMERICA 345 SCARBOROUGH ROAD, BRIARCLIFF MANOR NY 10510, USAE-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We study the expressive power of independence-friendly quantifier prefixes composed of universal $\left( {\forall x/X} \right)$, existential $\left( {\exists x/X} \right)$, and majority quantifiers $\left( {Mx/X} \right)$. We provide four quantifier prefixes that can express NP hard properties and show that all quantifier prefixes capable of expressing NP-hard properties embed at least one of these four quantifier prefixes. As for the quantifier prefixes that do not embed any of these four quantifier prefixes, we show that they are equivalent to a first-order quantifier prefix composed of $\forall x$, $\exists x$, and Mx. In unison, our results imply a dichotomy result: every independence-friendly quantifier prefix is either decidable in LOGSPACE or NP hard.

Keywords

DichotomyBranching quantifiersHenkin quantifiersIndependence-friendly logicDescriptive complexityNP
Type
Articles
Information
The Journal of Symbolic Logic , Volume 79 , Issue 4 , December 2014 , pp. 1224 - 1246
Copyright
Copyright © The Association for Symbolic Logic 2014 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

Barbero, F., On existential declarations of independence in IF logic. The Review of Symbolic Logic, vol. 6 (2013), pp. 254–280.Google Scholar
Barwise, J., On branching quantifiers in English. Journal of Philosophical Logic, vol. 8 (1979), pp. 47–80.Google Scholar
Blass, A. and Gurevich, Y., Henkin quantifiers and complete problems. Annals of Pure and Applied Logic, vol. 32 (1986), pp. 1–16.CrossRefGoogle Scholar
Caicedo, X., Dechesne, F., and Janssen, T. M. V., Equivalence and quantifier rules for logic with imperfect information. Logic Journal of the IGPL, vol. 17 (2009), pp. 91–129.Google Scholar
Caicedo, X. and Krynicki, M., Quantifiers for reasoning with imperfect information and ${\rm{\Sigma }}_1^1 $-logic, Advances in contemporary logic and computer science: Proceedings of the eleventh Brazilian conference on mathematical Logic, May 6–10, 1996 (Walter A. Carnielli and Itala M. L. Ottaviano, editors), Contemporary Mathematics, vol. 235, American Mathematical Society, 1999, pp. 17–31.CrossRefGoogle Scholar
Enderton, H. B., Finite partially ordered quantifiers. Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 16 (1970) pp. 393–397.Google Scholar
Engström, Fredrik, Generalized quantifiers in dependence logic. Journal of Logic, Language and Information, vol. 21 (2012), no. 3, pp. 299–324.CrossRefGoogle Scholar
Fagin, R., Generalized first-order spectra and polynomial-time recognizable sets, SIAM-AMS proceedings, complexity of computation (R. M. Karp, editor), vol. 7, 1974, pp. 43–73.Google Scholar
Garey, M. R. and Johnson, D. S., Computers and intractability: A guide to the theory of NP-completeness, W. H. Freeman and Company, San Francisco, CA, 1979.Google Scholar
Gottlob, G., Kolaitis, P. G., and Schwentick, T., Existential second-order logic over graphs: Charting the tractability frontier. The Journal of the ACM, vol. 51 (2004), no. 2, pp. 312–362.Google Scholar
Henkin, L., Some remarks on infinitely long formulas, Infinitistic methods: Proceedings of the symposium on foundations of mathematics, Warsaw, 2–9 September 1959 (P. Bernays, editor), Pergamon Press, Oxford, 1961, pp. 167–183.Google Scholar
Hintikka, J. and Sandu, G., Game-theoretical semantics, Handbook of logic and language (J. F. A. K. van Benthem and A. ter Meulen, editors), North Holland, Amsterdam, 1997, pp. 361–481.Google Scholar
Hodges, W., Compositional semantics for a language of imperfect information. Logic Journal of the IGPL, vol. 5 (1997), pp. 539–563.Google Scholar
Immerman, N., Descriptive complexity, Graduate Texts in Computer Science. Springer-Verlag, New York, 1999.Google Scholar
Ladner, R. E., On the structure of polynomial time reducibility. The Journal of the ACM, vol. 22 (1975), pp. 155–171.Google Scholar
Mann, A. L., Sandu, G., and Sevenster, M., Independence-friendly logic: A game-theoretic approach, Cambridge University Press, Cambridge, 2011.CrossRefGoogle Scholar
Osborne, M. J. and Rubinstein, A., A Course in game theory, MIT Press, Cambridge, MA, 1994.Google Scholar
Sandu, G., On the logic of informational independence and its applications. Journal of Philosophical Logic, vol. 22 (1993), pp. 29–60.CrossRefGoogle Scholar
Sevenster, M., Branches of imperfect information: Logic, games, and computation, Ph.D. thesis, University of Amsterdam, Amsterdam, 2006.Google Scholar
Walkoe, W., Finite partially-ordered quantification, this JOURNAL, vol. 35 (1940), pp. 535–555.Google Scholar