Decidability of the two-quantifier theory of the recursively enumerable weak truth-table degrees and other distributive upper semi-lattices
We give a decision procedure for the ∀∃-theory of the weak truth-table (wtt) 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. wtt-degrees by a map which preserves the least and greatest ele...
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Dokumenttyp: | Article (Journal) |
| Sprache: | Englisch |
| Veröffentlicht: |
1996
|
| In: |
The journal of symbolic logic
Year: 1996, Jahrgang: 61, Heft: 3, Pages: 880-905 |
| ISSN: | 1943-5886 |
| DOI: | 10.2307/2275790 |
| Online-Zugang: | Verlag, lizenzpflichtig, Volltext: https://doi.org/10.2307/2275790 Verlag, lizenzpflichtig, Volltext: https://www.cambridge.org/core/journals/journal-of-symbolic-logic/article/abs/decidability-of-the-twoquantifier-theory-of-the-recursively-enumerable-weak-truthtable-degrees-and-other-distributive-upper-semilattices/278E9ACC07A3217F0595D6371716D8DE 
|
| Verfasserangaben: | Klaus Ambos-Spies, Peter A. Fejer, Steffen Lempp, Manuel Lerman |
MARC
| LEADER | 00000caa a2200000 c 4500 | ||
|---|---|---|---|
| 001 | 1843120240 | ||
| 003 | DE-627 | ||
| 005 | 20230710180505.0 | ||
| 007 | cr uuu---uuuuu | ||
| 008 | 230419s1996 xx |||||o 00| ||eng c | ||
| 024 | 7 | |a 10.2307/2275790 |2 doi | |
| 035 | |a (DE-627)1843120240 | ||
| 035 | |a (DE-599)KXP1843120240 | ||
| 035 | |a (OCoLC)1389826045 | ||
| 040 | |a DE-627 |b ger |c DE-627 |e rda | ||
| 041 | |a eng | ||
| 084 | |a 28 |2 sdnb | ||
| 100 | 1 | |a Ambos-Spies, Klaus |d 1951- |e VerfasserIn |0 (DE-588)141551607 |0 (DE-627)629951861 |0 (DE-576)16006810X |4 aut | |
| 245 | 1 | 0 | |a Decidability of the two-quantifier theory of the recursively enumerable weak truth-table degrees and other distributive upper semi-lattices |c Klaus Ambos-Spies, Peter A. Fejer, Steffen Lempp, Manuel Lerman |
| 264 | 1 | |c 1996 | |
| 300 | |a 26 | ||
| 336 | |a Text |b txt |2 rdacontent | ||
| 337 | |a Computermedien |b c |2 rdamedia | ||
| 338 | |a Online-Ressource |b cr |2 rdacarrier | ||
| 500 | |a Elektronische Reproduktion der Druck-Ausgabe 12. März 2014 | ||
| 500 | |a Gesehen am 19.04.2023 | ||
| 520 | |a We give a decision procedure for the ∀∃-theory of the weak truth-table (wtt) 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. wtt-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.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 (pm) degrees of the recursive sets. These applications to the pm degrees require no new complexity-theoretic results. The fact that the pm-degrees of the recursive sets have a decidable two-quantifier theory answers a question raised by Shore and Slaman in [21]. | ||
| 650 | 4 | |a decidable fragment | |
| 650 | 4 | |a recursive polynomial many-one degree | |
| 650 | 4 | |a Recursively enumerable weak truth-table degree | |
| 700 | 1 | |a Fejer, Peter A. |e VerfasserIn |4 aut | |
| 700 | 1 | |a Lempp, Steffen |d 1959- |e VerfasserIn |0 (DE-588)139529365 |0 (DE-627)703360426 |0 (DE-576)311017681 |4 aut | |
| 700 | 1 | |a Lerman, Manuel |d 1943- |e VerfasserIn |0 (DE-588)109731166 |0 (DE-627)691056463 |0 (DE-576)348619626 |4 aut | |
| 773 | 0 | 8 | |i Enthalten in |t The journal of symbolic logic |d Cambridge : Cambridge Univ. Press, 1936 |g 61(1996), 3, Seite 880-905 |h Online-Ressource |w (DE-627)312113447 |w (DE-600)2010607-5 |w (DE-576)094449333 |x 1943-5886 |7 nnas |a Decidability of the two-quantifier theory of the recursively enumerable weak truth-table degrees and other distributive upper semi-lattices |
| 773 | 1 | 8 | |g volume:61 |g year:1996 |g number:3 |g pages:880-905 |g extent:26 |a Decidability of the two-quantifier theory of the recursively enumerable weak truth-table degrees and other distributive upper semi-lattices |
| 856 | 4 | 0 | |u https://doi.org/10.2307/2275790 |x Verlag |x Resolving-System |z lizenzpflichtig |3 Volltext |
| 856 | 4 | 0 | |u https://www.cambridge.org/core/journals/journal-of-symbolic-logic/article/abs/decidability-of-the-twoquantifier-theory-of-the-recursively-enumerable-weak-truthtable-degrees-and-other-distributive-upper-semilattices/278E9ACC07A3217F0595D6371716D8DE |x Verlag |z lizenzpflichtig |3 Volltext |
| 951 | |a AR | ||
| 992 | |a 20230419 | ||
| 993 | |a Article | ||
| 994 | |a 1996 | ||
| 998 | |g 141551607 |a Ambos-Spies, Klaus |m 141551607:Ambos-Spies, Klaus |d 110000 |d 110300 |e 110000PA141551607 |e 110300PA141551607 |k 0/110000/ |k 1/110000/110300/ |p 1 |x j | ||
| 999 | |a KXP-PPN1843120240 |e 4311113404 | ||
| BIB | |a Y | ||
| SER | |a journal | ||
| JSO | |a {"type":{"bibl":"article-journal","media":"Online-Ressource"},"note":["Elektronische Reproduktion der Druck-Ausgabe 12. März 2014","Gesehen am 19.04.2023"],"recId":"1843120240","language":["eng"],"person":[{"roleDisplay":"VerfasserIn","display":"Ambos-Spies, Klaus","role":"aut","family":"Ambos-Spies","given":"Klaus"},{"family":"Fejer","given":"Peter A.","display":"Fejer, Peter A.","roleDisplay":"VerfasserIn","role":"aut"},{"role":"aut","roleDisplay":"VerfasserIn","display":"Lempp, Steffen","given":"Steffen","family":"Lempp"},{"family":"Lerman","given":"Manuel","roleDisplay":"VerfasserIn","display":"Lerman, Manuel","role":"aut"}],"title":[{"title_sort":"Decidability of the two-quantifier theory of the recursively enumerable weak truth-table degrees and other distributive upper semi-lattices","title":"Decidability of the two-quantifier theory of the recursively enumerable weak truth-table degrees and other distributive upper semi-lattices"}],"physDesc":[{"extent":"26 S."}],"relHost":[{"physDesc":[{"extent":"Online-Ressource"}],"id":{"issn":["1943-5886"],"eki":["312113447"],"zdb":["2010607-5"]},"origin":[{"publisherPlace":"Cambridge ; Urbana, Ill.","dateIssuedDisp":"1936-","publisher":"Cambridge Univ. Press ; Assoc.","dateIssuedKey":"1936"}],"name":{"displayForm":["publ. quarterly by the Association for Symbolic Logic. Ed. by Alonzo Church [u.a.]"]},"part":{"extent":"26","volume":"61","text":"61(1996), 3, Seite 880-905","issue":"3","pages":"880-905","year":"1996"},"pubHistory":["1.1936 -"],"recId":"312113447","corporate":[{"display":"Association for Symbolic Logic","roleDisplay":"Herausgebendes Organ","role":"isb"}],"language":["eng"],"type":{"bibl":"periodical","media":"Online-Ressource"},"disp":"Decidability of the two-quantifier theory of the recursively enumerable weak truth-table degrees and other distributive upper semi-latticesThe journal of symbolic logic","note":["Gesehen am 14.11.24"],"title":[{"title_sort":"journal of symbolic logic","title":"The journal of symbolic logic"}]}],"name":{"displayForm":["Klaus Ambos-Spies, Peter A. Fejer, Steffen Lempp, Manuel Lerman"]},"origin":[{"dateIssuedDisp":"1996","dateIssuedKey":"1996"}],"id":{"doi":["10.2307/2275790"],"eki":["1843120240"]}} | ||
| SRT | |a AMBOSSPIESDECIDABILI1996 | ||