Hostname: page-component-cd9895bd7-gbm5v Total loading time: 0 Render date: 2024-12-22T20:53:32.178Z Has data issue: false hasContentIssue false
  • English
  • Français

First order quantifiers in monadic second order logic

Published online by Cambridge University Press:  12 March 2014

H. Jerome Keisler  and
Wafik Boulos Lotfallah
H. Jerome Keisler
Affiliation:
Department of Mathematics, University of Wisconsin, 480 Lincoln Drive, Madison WI 53706, USA, E-mail: [email protected]
Wafik Boulos Lotfallah
Affiliation:
Dept. of Eng. Math. and Phys., Cairo University, Cairo, 11451, Egypt, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

This paper studies the expressive power that an extra first order quantifier adds to a fragment of monadic second order logic, extending the toolkit of Janin and Marcinkowski [JM01].

We introduce an operation existsn (S) on properties S that says “there are n components having S”. We use this operation to show that under natural strictness conditions, adding a first order quantifier word u to the beginning of a prefix class V increases the expressive power monotonically in u. As a corollary, if the first order quantifiers are not already absorbed in V, then both the quantifier alternation hierarchy and the existential quantifier hierarchy in the positive first order closure of V are strict.

We generalize and simplify methods from Marcinkowski [Mar99] to uncover limitations of the expressive power of an additional first order quantifier, and show that for a wide class of properties S, S cannot belong to the positive first order closure of a monadic prefix class W unless it already belongs to W.

We introduce another operation alt(S) on properties which has the same relationship with the Circuit Value Problem as reach(S) (defined in [JM01]) has with the Directed Reachability Problem. We use alt(S) to show that Πn ⊈ FO(Σn), Σn ⊈ FO(∆n). and ∆n+1 ⊈ FOB(Σn), solving some open problems raised in [Mat98].

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 69 , Issue 1 , March 2004 , pp. 118 - 136
Copyright
Copyright © Association for Symbolic Logic 2004

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

[AF90]Ajtai, M. and Fagin, R.. Reachability is harder for directed than for undirected finite graphs, this Journal, vol. 55 (1990). pp. 113–150.Google Scholar
[AFS98]Ajtai, M., Fagin, R.. and Stockmeyer, L.. The closure of monadic NP, Journal of Computer and System Sciences, (1998), pp. 309–318. (extended abstract of [AFS00]).Google Scholar
[AFS00]Ajtai, M., The closure of monadic NP. Proceedings of 13th STOC, vol. 60 (2000), pp. 660–716.Google Scholar
[EF99]Ebbinghaus, H-D. and Flum, J.. Finite model theory. 2 ed., Springer, 1999.Google Scholar
[Ehr61]Ehrenfeucht, A.. An application of games to the completeness problem for formalized theories, Fundamenta Mathematicae. vol. 49 (1961), pp. 129–141.CrossRefGoogle Scholar
[Fag74]Fagin, R.. Generalized first-order spectra and polynomial-time recognizable sets. Complexity of computation (Karp, R.M., editor), SIAM-AMS Proceedings, vol. 7. 1974, pp. 43–73.Google Scholar
[Fag75]Fagin, R., Monadic generalized spectra. Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 21 (1975), pp. 89–96.CrossRefGoogle Scholar
[Imm99]Immerman, N., Descriptive complexity, Springer Verlag. New York, 1999.CrossRefGoogle Scholar
[JM01]Janin, D. and Marcinkowski, J., Toolkit for first order extensions of monadic games, Proceedings of STACS, LNCS, Springer, 2001.Google Scholar
[KW73]Keisler, H. J. and Walkoe, W., The diversity of quantifier prefixes, this Journal, vol. 38 (1973), pp. 79–85.Google Scholar
[Mar99]Marcinkowski, J.. Directed reachability: From Ajtai-Fagin to Ehrenfeucht-Fraïssé games. Proceedings of the Annual Conference of the European Association of Computer Science Logic, (CSL 99). LNCS, vol. 1683. Springer, pp. 338–349.Google Scholar
[Mat98]Matz, O., First-order closure and the monadic second-order alternation hierarchy. Technical Report 9807, Institut für Informatik und Praktische Mathematik. Christian-Albrechts-Universität. Kiel, 05 1998.Google Scholar
[MT97]Matz, O. and Thomas, W., The monadic quantifier alternation hierarchy over Graphs is infinite. Proceedings of 12th IEEE Symposium on Logic in Computer Science, 1997, pp, 236–244,Google Scholar
[Sto77]Stockmeyer, L., The polynomial time hierarchy, Theoretical Computer Science, vol. 3 (1977), pp. 1–22.CrossRefGoogle Scholar