The \(\exists\forall^2\) fragment of the first-order theory of atomic set constraints is \(\Pi_1^0\)-hard

DOI10.1016/S0020-0190(00)00030-2zbMath1014.68041OpenAlexW2021680514MaRDI QIDQ1607043

Jean-Marc Talbot

Publication date: 25 July 2002

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0020-0190(00)00030-2

zbMATH Keywords

set constraints

Mathematics Subject Classification ID

Undecidability and degrees of sets of sentences (03D35) Logic programming (68N17)

Cites Work

• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• An undecidable fragment of the theory of set constraints
• Decidability of systems of set constraints with negative constraints
• Computability of Recursive Functions
• Grid structures and undecidable constraint theories
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The \(\exists\forall^2\) fragment of the first-order theory of atomic set constraints is \(\Pi_1^0\)-hard