Hostname: page-component-cd9895bd7-q99xh Total loading time: 0 Render date: 2024-12-23T13:04:29.837Z Has data issue: false hasContentIssue false
  • English
  • Français

Decidability of Definability

Published online by Cambridge University Press:  12 March 2014

Manuel Bodirsky ,
Michael Pinsker  and
Todor Tsankov
Manuel Bodirsky
Affiliation:
Laboratoire d'Informatique (LIX), CNRS UMR 7161, École Polytechnique, 91128 Palaiseau, France, E-mail: [email protected], URL: http://www.lix.polytechnique.fr/~bodirsky/
Michael Pinsker
Affiliation:
Équipe de Logique Mathématique, Université Diderot, —Paris 7, UFR de Mathématiques, 75205 Paris Cedex 13, France, E-mail: [email protected], URL: http://dmg.tuwien.ac.at/pinsker/
Todor Tsankov
Affiliation:
Équipe de Logique Mathématique, Université Diderot, —Paris 7, UFR de Mathématiques, 75205 Paris Cedex 13, France, E-mail: [email protected], URL: http://people.math.jussieu.fr/~todor/
Get access Rights & Permissions [Opens in a new window]

Abstract

For a fixed countably infinite structure Γ with finite relational signature τ, we study the following computational problem: input are quantifier-free τ-formulas ϕ0, ϕ1, …, ϕn that define relations R0, R1, …, Rn over Γ. The question is whether the relation R0 is primitive positive definable from R1, …, Rn, i.e., definable by a first-order formula that uses only relation symbols for R1, …, Rn, equality, conjunctions, and existential quantification (disjunction, negation, and universal quantification are forbidden).

We show decidability of this problem for all structures Γ that have a first-order definition in an ordered homogeneous structure Δ with a finite relational signature whose age is a Ramsey class and determined by finitely many forbidden substructures. Examples of structures Γ with this property are the order of the rationals, the random graph, the homogeneous universal poset, the random tournament, all homogeneous universal C-relations, and many more. We also obtain decidability of the problem when we replace primitive positive definability by existential positive, or existential definability. Our proof makes use of universal algebraic and model theoretic concepts, Ramsey theory, and a recent characterization of Ramsey classes in topological dynamics.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 78 , Issue 4 , December 2013 , pp. 1036 - 1054
Copyright
Copyright © Association for Symbolic Logic 2013

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] Adeleke, Samson Adepoju and Neumann, Peter M., Relations related to betweenness: their structure and automorphisms, vol. 131, Memoirs of the American Mathematical Society, no. 623, 1998.Google Scholar
[2] Allen, James F., Maintaining knowledge about temporal intervals, Communications of the ACM, vol. 26 (1983), no. 11, pp. 832–843.CrossRefGoogle Scholar
[3] Bodirsky, Manuel, Chen, Hubie, and Pinsker, Michael, The reducts of equality up to primitive positive interdefinability, this Journal, vol. 75 (2010), no. 4, pp. 1249–1292.Google Scholar
[4] Bodirsky, Manuel and Dalmau, Víctor, Datalog and constraint satisfaction with infinite templates, Journal on Computer and System Sciences, vol. 79 (2013), pp. 79–100, A preliminary version appeared in the Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS'05) .CrossRefGoogle Scholar
[5] Bodirsky, Manuel and Kára, Jan, The complexity of temporal constraint satisfaction problems, Journal of the ACM, vol. 57 (2009), no. 2, pp. 1–41, an extended abstract appeared in the Proceedings of the Symposium on Theory of Computing (STOC'08) .CrossRefGoogle Scholar
[6] Bodirsky, Manuel and Nešetřil, Jaroslav, Constraint satisfaction with countable homogeneous templates, Journal of Logic and Computation, vol. 16 (2006), no. 3, pp. 359–373.CrossRefGoogle Scholar
[7] Bodirsky, Manuel and Piguet, Diana, Finite trees are Ramsey with respect to topological embeddings, preprint, arXiv: 1002.1557, 2010.Google Scholar
[8] Bodirsky, Manuel and Pinsker, Michael, Reducts of Ramsey structures, Model theoretic methods in finite combinatorics, Contemporary Mathematics, vol. 558, AMS, 2011, pp. 489–519.CrossRefGoogle Scholar
[9] Bodirsky, Manuel and Pinsker, Michael, Minimal functions on therandom graph, Israel Journal of Mathematics , to appear, preprint arXiv.org/abs/1003.4030.Google Scholar
[10] Duentsch, Ivo, Relation algebras and their application in temporal and spatial reasoning, Artificial Intelligence Review, vol. 23 (2005), pp. 315–357.CrossRefGoogle Scholar
[11] Goldstern, Martin and Pinsker, Michael, A survey of clones on infinite sets, Algebra Universalis, vol. 59 (2008), pp. 365–403.CrossRefGoogle Scholar
[12] Graham, Ron L., Rothschild, Bruce L., and Spencer, Joel H., Ramsey theory, second ed., Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., New York, 1990.Google Scholar
[13] Henson, C. Ward, Countable homogeneous relational systems and categorical theories, this Journal, vol. 37 (1972), pp. 494–500.Google Scholar
[14] Hirsch, R., Expressive power and complexity in algebraic logic, Journal of Logic and Computation, vol. 7 (1997), no. 3, pp. 309–351.CrossRefGoogle Scholar
[15] Hodges, Wilfrid, A shorter model theory, Cambridge University Press, New York, USA, 1997.Google Scholar
[16] Kechris, Alexander, Pestov, Vladimir, and Todorcevic, Stevo, Fraissé limits, Ramsey theory, and topological dynamics of automorphism groups, Geometric and Functional Analysis, vol. 15 (2005), no. 1, pp. 106–189.CrossRefGoogle Scholar
[17] Macpherson, Dugald, A survey of homogeneous structures, Discrete Mathematics, vol. 311 (2011), no. 15, pp. 1599–1634.CrossRefGoogle Scholar
[18] Milliken, Keith R., A Ramsey theorem for trees, Journal of Combinatorial Theory, Series A, vol. 26 (1979), no. 3, pp. 215–237.CrossRefGoogle Scholar
[19] Nešetřil, Jaroslav, Ramsey classes and homogeneous structures, Combinatorics, Probability & Computing, vol. 14 (2005), no. 1–2, pp. 171–189.CrossRefGoogle Scholar
[20] Nešetřil, Jaroslav and Rödl, Vojtěch, The partite construction and Ramsey set systems, Discrete Mathematics, vol. 75 (1989), no. 1–3, pp. 327–334.CrossRefGoogle Scholar
[21] Pinsker, Michael, More sublattices of the lattice of local clones, Order, vol. 27 (2010), no. 3, pp. 353–364.CrossRefGoogle Scholar
[22] Thomas, Simon, Reducts of the random graph, this Journal, vol. 56 (1991), no. 1, pp. 176–181.Google Scholar
[23] Willard, Ross, Testing expressibility is hard, Principles and practice of constraint programming - CP 2010 (Cohen, David, editor), Lecture Notes in Computer Science, vol. 6308, Springer, 2010, pp. 9–23.CrossRefGoogle Scholar