Decidability of definability
From MaRDI portal
Abstract: For a fixed countably infinite structure Gamma with finite relational signature au, we study the following computational problem: input are quantifier-free au-formulas phi_0,phi_1,...,phi_n that define relations R_0,R_1,...,R_n over Gamma. The question is whether the relation R_0 is primitive positive definable from R_1,...,R_n, i.e., definable by a first-order formula that uses only relation symbols for R_1,..., R_n, equality, conjunctions, and existential quantification (disjunction, negation, and universal quantification are forbidden). We show decidability of this problem for all structures Gamma that have a first-order definition in an ordered homogeneous structure Delta with a finite relational signature whose age is a Ramsey class and determined by finitely many forbidden substructures. Examples of structures Gamma 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.
Recommendations
Cited in
(58)- scientific article; zbMATH DE number 777294 (Why is no real title available?)
- Ticket Entailment is decidable
- Topological dynamics of unordered Ramsey structures
- Deciding quantifier-free definability in finite algebraic structures
- PROJECTIVE CLONE HOMOMORPHISMS
- On the expression complexity of equivalence and isomorphism of primitive positive formulas
- Complexity of inverse constraint problems and a dichotomy for the inverse satisfiability problem
- Constraint satisfaction and semilinear expansions of addition over the rationals and the reals
- Permutation groups containing infinite symplectic linear groups and reducts of linear spaces over the two element field
- CORES OVER RAMSEY STRUCTURES
- When Is Reachability Intrinsically Decidable?
- Infinitely many reducts of homogeneous structures
- Topological dynamics of kaleidoscopic groups
- Universal minimal flows of generalized Ważewski dendrites
- Smooth approximations: an algebraic approach to CSPs over finitely bounded homogeneous structures
- The lattice of definability: origins, recent developments, and further directions
- Fixed points in compactifications and combinatorial counterparts
- Constants and finite unary relations in qualitative constraint reasoning
- Homogeneous structures: model theory meets universal algebra. Abstracts from the workshop held January 3--9, 2021 (online meeting)
- scientific article; zbMATH DE number 1302671 (Why is no real title available?)
- The 42 reducts of the random ordered graph
- scientific article; zbMATH DE number 2151710 (Why is no real title available?)
- Decidability and definability with circumscription
- Primitive positive formulas preventing a finite basis of quasi-equations
- Decidability of general extensional mereology
- Gowers' Ramsey theorem with multiple operations and dynamics of the homeomorphism group of the Lelek fan
- A complexity dichotomy in spatial reasoning via Ramsey theory
- scientific article; zbMATH DE number 4085609 (Why is no real title available?)
- A dichotomy for first-order reducts of unary structures
- Topological dynamics of Polish group extensions
- \(2^{\aleph_{0}}\) pairwise nonisomorphic maximal-closed subgroups of \(\mathrm{Sym}(\mathbb N)\) via the classification of the reducts of the Henson digraphs
- Permutation groups with small orbit growth
- Reducts of the random partial order
- Decidability in elementary analysis. I
- A dichotomy theorem for the inverse satisfiability problem
- Generalized completion problems with forbidden tournaments
- Smooth approximations and relational width collapses
- An algebraic proof of the dichotomy for graph orientation problems with forbidden tournaments
- Generating primitive positive clones
- Complexity classification transfer for CSPs via algebraic products
- From Ramsey degrees to Ramsey expansions via weak amalgamation
- Promise and infinite-domain constraint satisfaction
- Decidability in Intuitionistic Type Theory is Functionally Decidable
- Reducts of the generic digraph
- Deciding open definability via subisomorphisms
- scientific article; zbMATH DE number 7406819 (Why is no real title available?)
- Smooth approximations and CSPs over finitely bounded homogeneous structures
- Ramsey properties of products and pullbacks of categories and the Grothendieck construction
- Definability by turing machines
- Decidable and Undecidable Problems for First-Order Definability and Modal Definability
- Reducts of Ramsey structures
- Permutations on the random permutation
- The wonderland of reflections
- Collapsing the bounded width hierarchy for infinite-domain constraint satisfaction problems: when symmetries are enough
- A logic-based framework for characterizing nexus of similarity within knowledge bases
- The language of stratified sets is confluent and strongly normalising
- Constraint satisfaction problems for reducts of homogeneous graphs
- Reducts of the Henson graphs with a constant
This page was built for publication: Decidability of definability
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5407040)
