Hostname: page-component-78c5997874-s2hrs Total loading time: 0 Render date: 2024-11-09T15:15:38.709Z Has data issue: false hasContentIssue false
  • English
  • Français

On spectra of sentences of monadic second order logic with counting

Published online by Cambridge University Press:  12 March 2014

E. Fischer  and
J. A. Makowsky
E. Fischer
Affiliation:
Department of Computer Science, Technion-Israel Institute of Technology, Haifa, Israel, E-mail: [email protected]
J. A. Makowsky
Affiliation:
Department of Computer Science, Technion-Israel Institute of Technology, Haifa, Israel, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract.

We show that the spectrum of a sentence ϕ in Counting Monadic Second Order Logic (CMSOL) using one binary relation symbol and finitely many unary relation symbols, is ultimately periodic, provided all the models of ϕ are of clique width at most k, for some fixed k. We prove a similar statement for arbitrary finite relational vocabularies τ and a variant of clique width for τ-structures. This includes the cases where the models of ϕ are of tree width at most k. For the case of bounded tree-width, the ultimate periodicity is even proved for Guarded Second Order Logic GSOL. We also generalize this result to many-sorted spectra, which can be viewed as an analogue of Parikh's Theorem on context-free languages, and its analogues for context-free graph grammars due to Habel and Courcelle.

Our work was inspired by Gurevich and Shelah (2003), who showed ultimate periodicity of the spectrum for sentences of Monadic Second Order Logic where only finitely many unary predicates and one unary function are allowed. This restriction implies that the models are all of tree width at most 2, and hence it follows from our result.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 69 , Issue 3 , September 2004 , pp. 617 - 640
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

[1]Asser, G., Das Repräsentationsproblem im Prädikatenkalkül der ersten Stufe mit Identität, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 1 (1955), pp. 252–263.CrossRefGoogle Scholar
[2]Beth, E. W., Observations métamathématiques sur les structures simplement ordonneés, Applications scientifiques de la logique mathématique, Collection de Logique Mathématique, Serie A, vol. 5, Paris and Louvain, 1954, pp. 29–35.Google Scholar
[3]Blatter, C. and Specker, E., First order spectra with one variable, Computation theory and logic, Lecture Notes in Computer Science, vol. 270, Springer-Verlag, 1987, pp. 166–180.Google Scholar
[4]Bodlaender, H., A tourist guide through tree width, Acta Cybernetica, vol. 11 (1993), pp. 1–23.Google Scholar
[5]Bodlaender, H., Treewidth: Algorithmic techniques and results, Proceedings of the 22th International Symposium on the Mathematical Foundation of Computer Science, MFCS ’97 (Privara, I. and Ruzicka, P., editors), Lecture Notes in Computer Science, vol. 1295, Springer-Verlag, 1997, pp. 29–36.Google Scholar
[6]Bodlaender, H., A partial k-arboretum of graphs with bounded treewidth, Theoretical Computer Science, vol. 209 (1998), pp. 1–45.CrossRefGoogle Scholar
[7]Brandstädt, A., Le, V. B., and Spinrad, J., Graph classes: A survey, SIAM Monographs on Discrete Mathematics and Applications, SIAM, 1999.CrossRefGoogle Scholar
[8]Christen, C. A., Spektralproblem und Komplexitätstherie, Komplexität von Entscheidungsproblemen (Specker, E. and Strassen, V., editors), Lecture Notes in Computer Science, vol. 43, Springer-Verlag, 1976, pp. 102–126.CrossRefGoogle Scholar
[9]Corneil, D. G., Habib, M., Lanlignel, J.-M., Reed, B., and Rotics, U., Polynomial time recognition of clique-width ≤ 3 graphs, Proceedings of LATIN 2000, Lecture Notes in Computer Science, vol. 1776, Springer-Verlag, 2000, pp. 126–134.Google Scholar
[10]Courcelle, B., The monadic second-order logic of graphs I: Recognizable sets of finite graphs, Information and Computation, vol. 85 (1990), pp. 12–75.CrossRefGoogle Scholar
[11]Courcelle, B., Monadic second-order logic of graphs VII: Graphs as relational structures, Theoretical Computer Science, vol. 101 (1992), pp. 3–33.CrossRefGoogle Scholar
[12]Courcelle, B., The monadic second-order logic of graphs VI: On several representations of graphs by relational structures, Discrete Applied Mathematics, vol. 54 (1994), pp. 117–149.CrossRefGoogle Scholar
[13]Courcelle, B., Structural properties of context-free sets of graphs generated by vertex replacement, Information and Computation, vol. 116 (1995), pp. 275–293.CrossRefGoogle Scholar
[14]Courcelle, B., The expression of graph properties and graph transformations in monadic second-order logic, Handbook of graph grammars and computing by graph transformations (Rozenberg, G., editor), vol. 1: Foundations, World Scientific, 1997, pp. 313–400.CrossRefGoogle Scholar
[15]Courcelle, B. and Engelfriet, J., A logical characterization of the sets of hypergraphs defined by hyperedge replacement grammars, Mathematical Systems Theory, vol. 28 (1995), pp. 515–552.CrossRefGoogle Scholar
[16]Courcelle, B., Engelfriet, J., and Rozenberg, G., Handle-rewriting hypergraph grammars, Journal of Computer and System Sciences, vol. 46 (1993), pp. 218–270.CrossRefGoogle Scholar
[17]Courcelle, B. and Makowsky, J. A., Fusion on relational structures and the verification of monadic second order properties, Mathematical Structures in Computer Science, vol. 12 (2002), no. 2, pp. 203–235.CrossRefGoogle Scholar
[18]Courcelle, B., Makowsky, J. A., and Rotics, U., On the fixed parameter complexity of graph enumeration problems definable in monadic second order logic, Discrete Applied Mathematics, vol. 108 (2001), no. 1–2, pp. 23–52.CrossRefGoogle Scholar
[19]Courcelle, B. and Olariu, S., Upper bounds to the clique-width of graphs, Discrete Applied Mathematics, vol. 101 (2000), pp. 77–114.CrossRefGoogle Scholar
[20]Diestel, R., Graph theory, Graduate Texts in Mathematics, Springer-Verlag, 1996.Google Scholar
[21]Downey, R. G. and Fellows, M. F., Parametrized complexity, Springer-Verlag, 1999.CrossRefGoogle Scholar
[22]Durand, A., Fagin, R., and Loescher, B., Spectra with only unary function symbols, CSL ’97 (Nielsen, M. and Thomas, W., editors), Lecture Notes in Computer Science, vol. 1414, Springer-Verlag, 1997, pp. 189–202.Google Scholar
[23]Durand, A. and Ranaivoson, S., First order spectra with one binary predicate, Theoretical Computer Science, vol. 160 (1996), pp. 305–320.CrossRefGoogle Scholar
[24]Ebbinghaus, H. D. and Flum, J., Finite model theory, Perspectives in Mathematical Logic, Springer-Verlag, 1995.Google Scholar
[25]Ebbinghaus, H. D., Flum, J., and Thomas, W., Mathematical logic, Undergraduate Texts in Mathematics, Springer-Verlag, 1980.Google Scholar
[26]Engelfriet, J. and van Oostrom, V., Logical description of context-free graph-languages, Journal of Computer and System Sciences, vol. 55 (1997), pp. 489–503.CrossRefGoogle Scholar
[27]Fagin, R., Generalized first-order spectra and polynomial time recognizable sets, Complexity of computation (Karp, R., editor), American Mathematical Society Proceedings, vol. 7, Society for Industrial and Applied Mathematics, 1974, pp. 27–41.Google Scholar
[28]Fagin, R., Monadic generalized spectra, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 21 (1975), pp. 89–96.CrossRefGoogle Scholar
[29]Feferman, S. and Vaught, R., The first order properties of algebraic systems, Fundamenta Mathematicae, vol. 47 (1959), pp. 57–103.CrossRefGoogle Scholar
[30]Fischer, E., The Specker-Blatter theorem does not hold for quaternary relations, Journal of Combinatorial Theory, Series A, vol. 103 (2003), pp. 121–136.CrossRefGoogle Scholar
[31]Fischer, E. and Makowsky, J. A., The Specker-Blatter theorem revisited, Cocoon '03, Lecture Notes in Computer Science, vol. 2697, Springer-Verlag, 2003, pp. 90–101.Google Scholar
[32]Fischer, E. and Makowsky, J. A., Patch-width, a generalization of clique-width for relational structures, in preparation, 2004.Google Scholar
[33]Gécseg, F. and Steinby, M., Tree languages, Handbook of formal languages (Rozenberg, G. and Salomaa, A., editors), vol. 3: Beyond words, Springer-Verlag, Berlin, 1997, pp. 1–68.Google Scholar
[34]Ginsburg, S. and Spanier, E. H., Bounded Algol-like languages, Transactions of the American Mathematical Society, vol. 113 (1966), pp. 333–368.Google Scholar
[35]Glikson, A. and Makowsky, J. A., NCE graph grammars and clique-width, Graph-theoretic concepts in computer science (Bodlaender, H., editor), Lecture Notes in Computer Science, vol. 2880, Springer-Verlag, 2003, pp. 237–248.CrossRefGoogle Scholar
[36]Golumbic, M. C. and Rotics, U., On the clique-width of some perfect graph classes, International Journal of Foundations of Computer Science, vol. 11 (2000), pp. 423–443.CrossRefGoogle Scholar
[37]Grädel, T., Hirsch, C., and Otto, M., Back and forth between guarded and modal logics, LiCS 2000, IEEE, 2000, pp. 217–228.Google Scholar
[38]Grandjean, É., First order spectra with one variable, Journal of Computer and System Sciences, vol. 40 (1990), no. 2, pp. 136–153.CrossRefGoogle Scholar
[39]Gurevich, Y., Modest theory of short chains, I, this Journal, vol. 44 (1979), pp. 481–490.Google Scholar
[40]Gurevich, Y. and Shelah, S., Spectra of monadic second-order formulas with one unary function, LiCS '03, IEEE, 2003, pp. 291–300.Google Scholar
[41]Habel, Annegret, Hyperedge replacement: Grammars and languages, Lecture Notes in Computer Science, vol. 643, Springer-Verlag, Berlin, 1992.Google Scholar
[42]Immerman, N., Descriptive complexity, Graduate Texts in Computer Science, Springer-Verlag, 1999.CrossRefGoogle Scholar
[43]Johnson, T., Robertson, N., Seymour, P., and Thomas, R., Directed tree-width, Journal of Combinatorial Theory, Serie B, vol. 81 (2001), no. 1, pp. 138–154.CrossRefGoogle Scholar
[44]Jones, N. G. and Selman, A. L., Turing machines and spectra of first order formulas, this Journal, vol. 39 (1972), pp. 139–150.Google Scholar
[45]Kim, C., A hierarchy of eNCE families of graph languages, Theoretical Computer Science, vol. 186 (1997), pp. 157–169.CrossRefGoogle Scholar
[46]Lovász, L. and Gácz, P., Some remarks on generalized spectra, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 23 (1977), pp. 547–554.CrossRefGoogle Scholar
[47]Lynch, J. F., Complexity classes and theories of finite models, Mathematical Systems Theory, vol. 15 (1982), pp. 127–144.CrossRefGoogle Scholar
[48]Makowsky, J. A., Logical methods in graph algorithms, lecture notes of a course given at ESSLLI '99 in Utrecht, , 08, 1999.Google Scholar
[49]Makowsky, J. A., Algorithmic uses of the Feferman-Vaught theorem, Annals of Pure and Applied Logic, (2004), in press.Google Scholar
[50]Makowsky, J. A. and Mariño, J. P., Tree-width and the monadic quantifier hierarchy, Theoretical Computer Science, vol. 303 (2003), pp. 157–170.CrossRefGoogle Scholar
[51]Makowsky, J. A. and Pnueli, Y., Arity vs. alternation in second order logic, Annals of Pure and Applied Logic, vol. 78 (1996), no. 2, pp. 189–202.CrossRefGoogle Scholar
[52]Makowsky, J. A. and Rotics, U., On the cliquewidth of graphs with few P4's, International Journal on Foundations of Computer Science, vol. 10 (1999), pp. 329–348.CrossRefGoogle Scholar
[53]Mo, S. K., Solutions to the Scholz problem, Chinese Annals of Mathematics, Series A, vol. 12 (1991), pp. 89–97.Google Scholar
[54]More, M., Investigations of binary spectra by explicit polynomial transformations of graphs, Theoretical Computer Science, vol. 124 (1994), no. 2, pp. 221–272.CrossRefGoogle Scholar
[55]Parikh, R., On context-free languages, Journal of the Association for Computing Machinery, vol. 13 (1966), pp. 570–581.CrossRefGoogle Scholar
[56]Robertson, N. and Seymour, P., Graph minors. IV. Tree-width and well-quasi-ordering, Journal of Combinatorial Theory, Serie B, vol. 48 (1990), pp. 227–254.CrossRefGoogle Scholar
[57]Rotics, U., Efficient algorithms for generally intractable graph problems restricted to specific classes of graphs, Ph. D. thesis, Technion-Israel Institute of Technology, 1998.Google Scholar
[58]Scholz, H., Problem #1: Ein ungelöstes Problem in der symbolischen Logik, this Journal, vol. 17 (1952), p. 160.Google Scholar
[59]Shelah, S., The monadic theory of order, Annals of Mathematics, vol. 102 (1975), pp. 379–419.CrossRefGoogle Scholar
[60]Shelah, S., Classification theory and the number of non-isomorphic models, 2nd ed., Studies in Logic and the Foundations of Mathematics, vol. 92, North-Holland, 1990.Google Scholar
[61]Shelah, S., Spectra of monadic second order sentences, to appear in the Japanese Journal of Mathematics, 2004, paper no. 817 at http://shelah.logic.at.Google Scholar
[62]Specker, E., Application of logic and combinatorics to enumeration problems, Trends in theoretical computer science (Börger, E., editor), Computer Science Press, 1988, pp. 141–169, reprinted in Ernst Specker, Selecta, Birkhäuser, 1990, pp. 324–350.Google Scholar
[63]Straubing, H., Finite automata, formal logic, and circuit complexity, Progress in Theoretical Computer Science, Birkhäuser, 1994.CrossRefGoogle Scholar