{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,12,23]],"date-time":"2022-12-23T15:54:27Z","timestamp":1671810867568},"reference-count":24,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":6401,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[1996,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We give a decision procedure for the \u2200\u2203-theory of the weak truth-table (<jats:italic>wtt<\/jats:italic>) degrees of the recursively enumerable sets. The key to this decision procedure is a characterization of the finite lattices which can be embedded into the r.e.<jats:italic>wtt<\/jats:italic>-degrees by a map which preserves the least and greatest elements: a finite lattice has such an embedding if and only if it is distributive and the ideal generated by its cappable elements and the filter generated by its cuppable elements are disjoint.<\/jats:p><jats:p>We formulate general criteria that allow one to conclude that a distributive upper semi-lattice has a decidable two-quantifier theory. These criteria are applied not only to the weak truth-table degrees of the recursively enumerable sets but also to various substructures of the polynomial many-one (<jats:italic>pm<\/jats:italic>) degrees of the recursive sets. These applications to the<jats:italic>pm<\/jats:italic>degrees require no new complexity-theoretic results. The fact that the<jats:italic>pm<\/jats:italic>-degrees of the recursive sets have a decidable two-quantifier theory answers a question raised by Shore and Slaman in [21].<\/jats:p>","DOI":"10.2307\/2275790","type":"journal-article","created":{"date-parts":[[2006,5,6]],"date-time":"2006-05-06T22:59:03Z","timestamp":1146956343000},"page":"880-905","source":"Crossref","is-referenced-by-count":7,"title":["Decidability of the two-quantifier theory of the recursively enumerable weak truth-table degrees and other distributive upper semi-lattices"],"prefix":"10.1017","volume":"61","author":[{"given":"Klaus","family":"Ambos-Spies","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter A.","family":"Fejer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Steffen","family":"Lempp","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Manuel","family":"Lerman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200017175_ref019","volume-title":"Classical recursion theory","volume":"125","author":"Odifreddi","year":"1989"},{"key":"S0022481200017175_ref001","doi-asserted-by":"publisher","DOI":"10.1007\/BF02007561"},{"key":"S0022481200017175_ref009","doi-asserted-by":"publisher","DOI":"10.1007\/BF01673953"},{"key":"S0022481200017175_ref017","unstructured":"Lempp Steffen and Nies Andr\u00e9 , The undecidability of the \u03a04-theory for the r.e. wtt- and Turing degrees, to appear, this Journal."},{"key":"S0022481200017175_ref004","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90234-8"},{"key":"S0022481200017175_ref011","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1982-0664035-X"},{"key":"S0022481200017175_ref010","first-page":"368","article-title":"The uppersemilattice of numerations of a finite set","volume":"14","author":"Ershov","year":"1975","journal-title":"Algebrai Logika"},{"key":"S0022481200017175_ref024","first-page":"37","article-title":"The theory of representations for Boolean algebras","volume":"40","author":"Stone","year":"1936","journal-title":"Transactions of the American Mathematical Society"},{"key":"S0022481200017175_ref012","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1007\/BFb0076217","volume-title":"Recursion theory week, Proceedings of a conference held in Oberwolfach, West Germany, April 15\u201321, 1984","author":"Fejer","year":"1985"},{"key":"S0022481200017175_ref006","first-page":"864","volume":"57","author":"Ambos-Spies","year":"1992","journal-title":"The theory of the recursively enumerable weak truth-table degrees is undecidable"},{"key":"S0022481200017175_ref013","volume-title":"Lattice theory: First concepts and distributive lattices","author":"Gr\u00e4tzer","year":"1971"},{"key":"S0022481200017175_ref005","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1984-0719661-8"},{"key":"S0022481200017175_ref007","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-97062-7"},{"key":"S0022481200017175_ref022","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-02460-7"},{"key":"S0022481200017175_ref002","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(85)80020-6"},{"key":"S0022481200017175_ref023","first-page":"921","volume":"48","author":"Stob","year":"1983","journal-title":"Wtt-degrees and T-degrees of recursively enumerable sets"},{"key":"S0022481200017175_ref003","first-page":"95","volume-title":"Trends in theoretical computer science","author":"Ambos-Spies","year":"1987"},{"key":"S0022481200017175_ref008","volume-title":"Lattice theory","author":"Birkhoff","year":"1948"},{"key":"S0022481200017175_ref014","volume-title":"Introduction to automata theory, languages, and computation","author":"Hopcroft","year":"1979"},{"key":"S0022481200017175_ref015","first-page":"193","volume":"58","author":"Jockusch","year":"1993","journal-title":"On the \u03a32-theory of the upper semilattice of Turing degrees"},{"key":"S0022481200017175_ref016","doi-asserted-by":"publisher","DOI":"10.1016\/0003-4843(75)90007-8"},{"key":"S0022481200017175_ref020","first-page":"331","volume-title":"Generalized recursion theory II","volume":"94","author":"Shore","year":"1978"},{"key":"S0022481200017175_ref021","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)90078-T"},{"key":"S0022481200017175_ref018","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-21755-9"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200017175","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,14]],"date-time":"2020-04-14T14:23:01Z","timestamp":1586874181000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200017175\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,9]]},"references-count":24,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1996,9]]}},"alternative-id":["S0022481200017175"],"URL":"https:\/\/doi.org\/10.2307\/2275790","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996,9]]}}}