Hostname: page-component-586b7cd67f-g8jcs Total loading time: 0 Render date: 2024-11-28T13:49:08.334Z Has data issue: false hasContentIssue false
  • English
  • Français

Relational structures constructible by quantifier free definable operations

Published online by Cambridge University Press:  12 March 2014

Saharon Shelah  and
Mor Doron
Saharon Shelah
Affiliation:
The Hebrew University of Jerusalem, Einstein Institute of Mathematics, Edmond Safra Campus, Givat Ram, Jerusalem 91904, Israel. E-mail: [email protected]
Mor Doron
Affiliation:
The Hebrew University of Jerusalem, Einstein Institute of Mathematics, Edmond Safra Campus, Givat Ram, Jerusalem 91904, Israel. E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We consider the notion of bounded m-ary patch-width defined in [9], and its very close relative m-constructibility defined below. We show that the notions of m-constructibility all coincide for m ≥ 3, while 1-constructibility is a weaker notion. The same holds for bounded m-ary patch-width. The case m = 2 is left open.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 72 , Issue 4 , December 2007 , pp. 1283 - 1298
Copyright
Copyright © Association for Symbolic Logic 2007

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äsentantenproblem 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]Blumensath, A., Axiomatising tree-interpretable structures, Theory of Computing Systems, vol. 237 (2004), no. 1, pp. 3–27.CrossRefGoogle Scholar
[3]Blumensath, A. and Courcelle, B., Recognizability, hypergraph operations, and logical types, Information and Computation, vol. 204 (2006), no. 6, pp. 853–919.CrossRefGoogle Scholar
[4]Courcelle, B., The monadic second order logic of graphs. VII. Graphs as relational structures. Theoretical Computer Science, vol. 101 (1992), no. 1, pp. 3–33.CrossRefGoogle Scholar
[5]Courcelle, B., Monadic second-order definable graph transductions: a survey, Theoretical Computer Science, vol. 126 (1994), no. 1, pp. 53–75.CrossRefGoogle Scholar
[6]Courcelle, B., Structural properties of context-free sets of graphs generated by vertex replacement, Information and Computation, vol. 116 (1995), no. 2, pp. 275–293.CrossRefGoogle Scholar
[7]Durand, A., Fagin, R., and Loescher, B., Spectra with only unary function symbols. Computer science logic (Aarhus, 1997), Lecture Notes in Computer Science, vol. 1414, Springer, Berlin, 1998, pp. 189–202.CrossRefGoogle Scholar
[8]Ebbinghaus, H. D. and Flum, J., Finite model theory, second ed., Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1999.Google Scholar
[9]Fischer, E. and Makowsky, J. A., On spectra of sentences of monadic second order logic with counting, this Journal, vol. 69 (2004), no. 3, pp. 617–640.Google Scholar
[10]Gurevich, Y. and Shelah, S., Spectra of monadic second-order formulas with one nary function, LICS '03, IEEE Computer Society, 2003, pp. 291–300.Google Scholar
[11]Shelah, S., Spectra of monadic second order sentences, Scientiae Mathematicae Japonicae, vol. 59 (2004), no. 2, pp. 351–355, Special issue on set theory and algebraic model theory.Google Scholar