{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,13]],"date-time":"2026-10-13T13:00:50Z","timestamp":1791896450132,"version":"4.3.4"},"reference-count":31,"publisher":"Wiley","issue":"1","license":[{"start":{"date-parts":[[2006,11,13]],"date-time":"2006-11-13T00:00:00Z","timestamp":1163376000000},"content-version":"vor","delay-in-days":3969,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematical Logic Qtrly"],"published-print":{"date-parts":[[1996,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The problem is addressed of establishing the satisfiability of prenex formulas involving a single universal quantifier, in diversified axiomatic set theories. A rather general decision method for solving this problem is illustrated through the treatment of membership theories of increasing strength, ending with a subtheory of Zermelo\u2010Fraenkel which is already complete with respect to the \u2200*\u2200 class of sentences. NP\u2010hardness and NP\u2010completeness results concerning the problems under study are achieved and a technique for restricting the universal quantifier is presented.<\/jats:p><jats:p><jats:bold>Mathematics Subject Classification:<\/jats:bold> 03B25, 03E30.<\/jats:p>","DOI":"10.1002\/malq.19960420105","type":"journal-article","created":{"date-parts":[[2007,5,26]],"date-time":"2007-05-26T17:52:49Z","timestamp":1180201969000},"page":"41-58","source":"Crossref","is-referenced-by-count":22,"title":["Decidability of \u2200*\u2200\u2010Sentences in Membership Theories"],"prefix":"10.1002","volume":"42","author":[{"given":"Eugenio G.","family":"Omodeo","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Franco","family":"Parlamento","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alberto","family":"Policriti","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"311","published-online":{"date-parts":[[2006,11,13]]},"reference":[{"key":"e_1_2_1_2_2","series-title":"CSLI Lecture Notes 14","volume-title":"Non\u2010Well\u2010Founded Sets","author":"Aczel P.","year":"1988"},{"key":"e_1_2_1_3_2","unstructured":"Bell\u00e9 D. andF.Parlamento Decidability and completeness of open formulae in membership theories. Technical Report 25\/93 Universit\u00e0 di Udine 1993."},{"key":"e_1_2_1_4_2","unstructured":"Bell\u00e9 D. andF.Parlamento Undecidability of weak membership theories. In: Proceedings of the International Conference on Logic and Algebra Siena April1994."},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.3160340203"},{"key":"e_1_2_1_6_2","first-page":"303","article-title":"Decidability results for classes of purely universal formulas and quantifiers elimination in set theory","volume":"43","author":"Cantone D.","year":"1988","journal-title":"Le Matematiche"},{"key":"e_1_2_1_7_2","volume-title":"Computable Set Theory","author":"Cantone D.","year":"1989"},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00245817"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1305\/ndjfl\/1093894080"},{"key":"e_1_2_1_10_2","series-title":"Lecture Notes in AI 660","first-page":"150","volume-title":"Extensions of Logic Programming","author":"Dovier A.","year":"1992"},{"key":"e_1_2_1_11_2","unstructured":"Dovier A. E. G.Omodeo E.Pontelli andG.\u2010F.Rossi {log}: a language for programming in logic with finite sets. Technical Report Rap. 04. 93 Universit\u00e0 di Roma La Sapienza 1993."},{"key":"e_1_2_1_12_2","first-page":"111","volume-title":"Logic Programming","author":"Dovier A.","year":"1991"},{"key":"e_1_2_1_13_2","volume-title":"The Decision Problem. Solvable Classes of Quantificational Formulas","author":"Dreben B.","year":"1979"},{"key":"e_1_2_1_14_2","volume-title":"Computers and Intractability. A Guide to the Theory of NP\u2010Completeness","author":"Garey M. R.","year":"1979"},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19780241902"},{"key":"e_1_2_1_16_2","unstructured":"Hibti M. NP\u2010compl\u00e9tude du langage MLS. Technical report Universit\u00e9 de Franche\u2010Comt\u00e9 UFR des sciences et techniques 1991."},{"key":"e_1_2_1_17_2","unstructured":"Legros E. Tests de satisfiabilit\u00e9 dans un langage de programmation en logique avec contraintes ensemblistes. PhD thesis Universit\u00e9 de Franche\u2010Comt\u00e9 1993."},{"key":"e_1_2_1_18_2","volume-title":"Unsolvable Classes of Quantificational Formulas","author":"Lewis H. R.","year":"1979"},{"key":"e_1_2_1_19_2","doi-asserted-by":"publisher","DOI":"10.1305\/ndjfl\/1094061860"},{"key":"e_1_2_1_20_2","unstructured":"Omodeo E. G. F.Parlamento andA.Policriti Truth tables for a combinatorial kernel of set theories. In: Proceedings of ECAI \u203290."},{"key":"e_1_2_1_21_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(06)80009-X"},{"key":"e_1_2_1_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0013178"},{"key":"e_1_2_1_23_2","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.3160410206"},{"key":"e_1_2_1_24_2","unstructured":"Parlamento F. andA.Policriti The satisfiability problem for the class \u2211*\u221e in a set\u2010theoretic setting. Technical Report 13\/92 Universit\u00e0 di Udine October1992."},{"key":"e_1_2_1_25_2","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.3160460104"},{"key":"e_1_2_1_26_2","unstructured":"Parlamento F. A.Policriti andK. P. S. B.Rao Witnessing differences without redundancies. Technical Report 23\/93 Universit\u00e0 di Udine 1993."},{"key":"e_1_2_1_27_2","first-page":"49","article-title":"Completeness and decidability of the deducibility problem for some class of formulas of set theory","volume":"42","author":"Policriti A.","year":"1987","journal-title":"Le Matematiche"},{"key":"e_1_2_1_28_2","first-page":"724","volume-title":"Mutual interpretability of some essentially undecidable theories","author":"Szmielew W.","year":"1950"},{"key":"e_1_2_1_29_2","volume-title":"Undecidable Theories","author":"Tarski A.","year":"1953"},{"key":"e_1_2_1_30_2","first-page":"245","article-title":"Complexity of the solution of the validity problem for an elementary sublanguage of quantifier\u2010free set theory","volume":"126","author":"Tetruashvili M. R.","year":"1987","journal-title":"Soobsh. Akad. Nauk. Gruzin. SSR"},{"key":"e_1_2_1_31_2","first-page":"465","article-title":"Decision complexity of the theory MLSC. Soobsh","volume":"132","author":"Tetruashvili M. R.","year":"1988","journal-title":"Akad. Nauk. Gruzin. SSR"},{"key":"e_1_2_1_32_2","first-page":"14","volume-title":"Methodology and Philosophy of Science","author":"Vaught R. L.","year":"1962"}],"container-title":["Mathematical Logic Quarterly"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fmalq.19960420105","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/malq.19960420105","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,26]],"date-time":"2023-10-26T22:12:25Z","timestamp":1698358345000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/malq.19960420105"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,1]]},"references-count":31,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1996,1]]}},"alternative-id":["10.1002\/malq.19960420105"],"URL":"https:\/\/doi.org\/10.1002\/malq.19960420105","archive":["Portico"],"relation":{},"ISSN":["0942-5616","1521-3870"],"issn-type":[{"value":"0942-5616","type":"print"},{"value":"1521-3870","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996,1]]}}}