Decidability of ∀*∀‐Sentences in Membership Theories

DOI10.1002/MALQ.19960420105MaRDI QIDQ4868240zbMATH OpenOpenAlexFDO

Authors Alberto Policriti, Eugenio Omodeo, Franco Parlamento

Publication date 2 May 1996

Published in Mathematical Logic Quarterly (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/malq.19960420105

zbMATH Keywords

fragment of set theoryNP-completenessNP-hardnesssatisfiability of prenex formulas involving a single universal quantifier

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15) Axiomatics of classical set theory and its fragments (03E30)

Recommendations

• Publication:4893143
• Decidability of ^*-sentences in HF
• Decidability and completeness for open formulas of membership theories
• Truth In V for ∃*∀∀-Sentences is Decidable
• The decidability of the ^* class and the axiom of foundation
• Axiomatizability by \({\forall \exists!}\)-sentences
• Provability and Decidability of Arithmetical Universal-Existential Sentences
• Publication:3489978
• The theory of Peano _1 sentences
• scientific article; zbMATH DE number 2020228

Cites work

• scientific article; zbMATH DE number 3657754 (Why is no real title available?)
• scientific article; zbMATH DE number 3715502 (Why is no real title available?)
• Witnessing differences without redundancies

Cited in

(15)

• A derived algorithm for evaluating -expressions over abstract sets
• The decidability of the ^* class and the axiom of foundation
• Decidability and completeness for open formulas of membership theories
• The \(\forall \exists \)-theory of the effectively closed Medvedev degrees is decidable
• Set-syllogistics meet combinatorics
• scientific article; zbMATH DE number 3865269 (Why is no real title available?)
• Truth In V for ∃*∀∀-Sentences is Decidable
• The Bernays-Schönfinkel-Ramsey class for set theory: semidecidability
• Deciding the Inductive Validity of ∀ ∃ * Queries
• Provability and Decidability of Arithmetical Universal-Existential Sentences
• Foundation versus induction in Kripke-Platek set theory
• Solvable set/hyperset contexts: I. Some decision procedures for the pure, finite case
• scientific article; zbMATH DE number 922623 (Why is no real title available?)
• A practical decision procedure for quantifier-free, decidable languages extended with restricted quantifiers
• Satisfiability of formulae with one \(\forall\) is decidable in exponential time

This page was built for publication: Decidability of ∀*∀‐Sentences in Membership Theories

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4868240)