A decidable two-sorted quantified fragment of set theory with ordered pairs and some undecidable extensions

DOI10.1016/j.tcs.2014.03.021zbMath1329.03045OpenAlexW2011350458MaRDI QIDQ477206

Cristiano Longo, Domenico Cantone

Publication date: 2 December 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2014.03.021

zbMATH Keywords

undecidabilityset theorydecision procedure

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Axiomatics of classical set theory and its fragments (03E30)

Related Items (3)

Web ontology representation and reasoning via fragments of set theory ⋮ Automated reasoning with restricted intensional sets ⋮ Solving quantifier-free first-order constraints over finite sets and binary relations

Uses Software

• AEtnaNova
• Referee
• Datalog
• SETL

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Decision procedures for elementary sublanguages of set theory: XI. Multilevel syllogistic extended by some elementary map constructs
• Decision procedures for elementary sublanguages of set theory. XV: Multilevel syllogistic extended by the predicate Finite and the operators singleton and \(pred_ <\)
• Decision procedures for elementary sublanguages of set theory. V. Multilevel syllogistic extended by the general union operator
• A Decidable Quantified Fragment of Set Theory Involving Ordered Pairs with Applications to Description Logics.
• The Bernays-Schönfinkel-Ramsey class for set theory: decidability
• The Bernays-Schönfinkel-Ramsey class for set theory: semidecidability
• Decision procedures for elementary sublanguages of set theory. VI. Multi-level syllogistic extended by the powerset operator
• Decision procedures for elementary sublanguages of set theory. I. Multi-level syllogistic and some extensions
• Decision procedures for elementary sublanguages of set theory. II. Formulas involving restricted quantifiers, together with ordinal, integer, map, and domain notions
• Computational Logic and Set Theory
• Verification: Theory and Practice
• The Description Logic Handbook
• On the Properties of Metamodeling in OWL
• The undecidability of the domino problem

This page was built for publication: A decidable two-sorted quantified fragment of set theory with ordered pairs and some undecidable extensions