{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,12,21]],"date-time":"2023-12-21T19:36:44Z","timestamp":1703187404843},"reference-count":80,"publisher":"Elsevier BV","issue":"1","license":[{"start":{"date-parts":[[1990,7,1]],"date-time":"1990-07-01T00:00:00Z","timestamp":646790400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":8417,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Annals of Pure and Applied Logic"],"published-print":{"date-parts":[[1990,7]]},"DOI":"10.1016\/0168-0072(90)90080-l","type":"journal-article","created":{"date-parts":[[2002,7,25]],"date-time":"2002-07-25T23:38:59Z","timestamp":1027640339000},"page":"1-79","source":"Crossref","is-referenced-by-count":72,"title":["A uniform method for proving lower bounds on the computational complexity of logical theories"],"prefix":"10.1016","volume":"48","author":[{"given":"Kevin J.","family":"Compton","sequence":"first","affiliation":[]},{"given":"C.","family":"Ward Henson","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/0168-0072(90)90080-L_BIB1","doi-asserted-by":"crossref","first-page":"239","DOI":"10.2307\/1970573","article-title":"The elementary theory of finite fields","volume":"88","author":"Ax","year":"1968","journal-title":"Ann. of Math."},{"key":"10.1016\/0168-0072(90)90080-L_BIB2","doi-asserted-by":"crossref","first-page":"437","DOI":"10.2307\/1970476","article-title":"Diophantine problems over local fields III: decidable fields","volume":"83","author":"Ax","year":"1966","journal-title":"Ann. of Math."},{"key":"10.1016\/0168-0072(90)90080-L_BIB3","doi-asserted-by":"crossref","first-page":"292","DOI":"10.2307\/2272133","article-title":"On Moschovakis closure ordinals","volume":"42","author":"Barwise","year":"1977","journal-title":"J. Symbolic Logic"},{"key":"10.1016\/0168-0072(90)90080-L_BIB4","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1090\/S0002-9939-1976-0416890-9","article-title":"Undecidability of the theory of abelian groups with a subgroup","volume":"55","author":"Baur","year":"1976","journal-title":"Proc. Amer. Math. Soc."},{"key":"10.1016\/0168-0072(90)90080-L_BIB5","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1016\/0003-4843(80)90011-X","article-title":"On the elementary theory of quadruples of vector spaces","volume":"19","author":"Baur","year":"1980","journal-title":"Ann. Math. Logic"},{"key":"10.1016\/0168-0072(90)90080-L_BIB6","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/0022-0000(86)90029-2","article-title":"the complexity of elementary algebra and geometry","volume":"32","author":"Ben-Or","year":"1986","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/0168-0072(90)90080-L_BIB7","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1016\/0304-3975(80)90037-7","article-title":"The complexity of logical theories","volume":"11","author":"Berman","year":"1980","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/0168-0072(90)90080-L_BIB8","series-title":"Logic Colloquium '82","first-page":"263","article-title":"Decision problems in predicate logic","author":"B\u00f6rger","year":"1984"},{"key":"10.1016\/0168-0072(90)90080-L_BIB9","first-page":"333","article-title":"Spektralproblem and completeness of logical decision problems","volume":"171","author":"B\u00f6rger","year":"1984"},{"key":"10.1016\/0168-0072(90)90080-L_BIB10","series-title":"Logic","article-title":"Berechenbarkeit, Komplexit\u00e4t","author":"B\u00f6rger","year":"1985"},{"key":"10.1016\/0168-0072(90)90080-L_BIB11","article-title":"Bounds on transfer principles for algebraically closed and discretely valued fields","volume":"204","author":"Brown","year":"1978","journal-title":"Mem. Amer. Math. Soc."},{"key":"10.1016\/0168-0072(90)90080-L_BIB12","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1016\/0304-3975(80)90036-5","article-title":"On time-space classes and their relation to the theory of real addition","volume":"11","author":"Bruss","year":"1980","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/0168-0072(90)90080-L_BIB13","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1007\/BF01470748","article-title":"Turing machines and the Entscheidungsproblem","volume":"148","author":"B\u00fcchi","year":"1962","journal-title":"Math. Ann."},{"key":"10.1016\/0168-0072(90)90080-L_BIB14","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1145\/322234.322243","article-title":"Alternation","volume":"28","author":"Chandra","year":"1981","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/0168-0072(90)90080-L_BIB15","first-page":"44","article-title":"Rings of continuous functions: decision problems","volume":"834","author":"Cherlin","year":"1980"},{"key":"10.1016\/0168-0072(90)90080-L_BIB16","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1016\/0168-0072(87)90017-0","article-title":"Nonconvergence, undecidability, and intractability in asymptotic problems","volume":"36","author":"Compton","year":"1987","journal-title":"Ann. Pure Appl. Logic"},{"key":"10.1016\/0168-0072(90)90080-L_BIB17","first-page":"A981","article-title":"Les corps pseudo-finis ont la propri\u00e9t\u00e9 d'ind\u00e9pendence","volume":"A-B 290","author":"Duret","year":"1980","journal-title":"C.R. Acad. Sci. Paris S\u00e9r."},{"key":"10.1016\/0168-0072(90)90080-L_BIB18","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0022-0000(85)90001-7","article-title":"Decision procedures and expressiveness in the temporal logic of branching time","volume":"30","author":"Emerson","year":"1985","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/0168-0072(90)90080-L_BIB19","first-page":"17","article-title":"Decidability of the elementary theory of relatively complemented distributive lattices and the theory of filters","volume":"3","author":"Er\u0161ov","year":"1964","journal-title":"Algebra i Logika"},{"key":"10.1016\/0168-0072(90)90080-L_BIB20","first-page":"1390","article-title":"On the elementary theory of maximal normed fields","volume":"6","author":"Er\u0161ov","year":"1965","journal-title":"Soviet Math. Dokl."},{"key":"10.1016\/0168-0072(90)90080-L_BIB21","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1070\/RM1965v020n04ABEH001188","article-title":"Elementary theories","volume":"20","author":"Er\u0161ov","year":"1965","journal-title":"Russian Math, Surveys"},{"key":"10.1016\/0168-0072(90)90080-L_BIB22","doi-asserted-by":"crossref","first-page":"57","DOI":"10.4064\/fm-47-1-57-103","article-title":"The first-order properties of products of algebraic systems","volume":"47","author":"Feferman","year":"1959","journal-title":"Fund. Math."},{"key":"10.1016\/0168-0072(90)90080-L_BIB23","series-title":"Doctoral thesis","article-title":"Some upper and lower bounds on decision procedures in logic","author":"Ferrante","year":"1974"},{"key":"10.1016\/0168-0072(90)90080-L_BIB24","article-title":"The Computational Complexity of Logical Theories","volume":"718","author":"Ferrante","year":"1979"},{"key":"10.1016\/0168-0072(90)90080-L_BIB25","doi-asserted-by":"crossref","first-page":"194","DOI":"10.1016\/0022-0000(79)90046-1","article-title":"Propositional dynamic logic of regular programs","volume":"18","author":"Fischer","year":"1979","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/0168-0072(90)90080-L_BIB26","first-page":"27","article-title":"Super-exponential complexity of Presburger arithmetic","volume":"7","author":"Fischer","year":"1974"},{"key":"10.1016\/0168-0072(90)90080-L_BIB27","series-title":"Logic Colloquium '76","first-page":"471","article-title":"Bounded concatenation theory as a uniform method for proving lower complexity bounds","author":"Fleischmann","year":"1977"},{"key":"10.1016\/0168-0072(90)90080-L_BIB28","doi-asserted-by":"crossref","first-page":"203","DOI":"10.2307\/1971045","article-title":"Solving Diophantine problems over all residue class field of a number field and all finite fields","volume":"104","author":"Fried","year":"1976","journal-title":"Ann. of Math."},{"key":"10.1016\/0168-0072(90)90080-L_BIB29","series-title":"Doctoral Thesis","article-title":"Nicht-elementare untere Schranken in der Automaten-theorie","author":"F\u00fcrer","year":"1978"},{"key":"10.1016\/0168-0072(90)90080-L_BIB30","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/0304-3975(82)90115-3","article-title":"The complexity of Presburger arithmetic with bounded quantifier alternation","volume":"18","author":"F\u00fcrer","year":"1982","journal-title":"Theoret. Comp. Sci."},{"key":"10.1016\/0168-0072(90)90080-L_BIB31","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1016\/S0019-9958(83)80043-6","article-title":"Complexity of the first-order theory of almost all finite structures","volume":"57","author":"Grandjean","year":"1983","journal-title":"Inform. and Control"},{"key":"10.1016\/0168-0072(90)90080-L_BIB32","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1090\/trans2\/046\/09","article-title":"Elementary properties of ordered Abelian groups","volume":"46","author":"Gurevich","year":"1965","journal-title":"Amer. Math. Soc. Transl."},{"key":"10.1016\/0168-0072(90)90080-L_BIB33","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1016\/0003-4843(77)90014-6","article-title":"Expanded theory of ordered abelian groups","volume":"12","author":"Gurevich","year":"1977","journal-title":"Ann. Math. Logic"},{"key":"10.1016\/0168-0072(90)90080-L_BIB34","series-title":"Proc. 1979 Intl. cong. Logic, Methodology and Philosophy of Science","first-page":"179","article-title":"Crumbly spaces","author":"Gurevich","year":"1982"},{"key":"10.1016\/0168-0072(90)90080-L_BIB35","series-title":"Proc. 18th Ann. ACM Symp. on Theory of Computing","first-page":"304","article-title":"The complexity of reasoning about knowledge and time","author":"Halpern","year":"1986"},{"key":"10.1016\/0168-0072(90)90080-L_BIB36","series-title":"theory of Numbers","author":"Hardy","year":"1964"},{"key":"10.1016\/0168-0072(90)90080-L_BIB37","series-title":"Languages and Computation","article-title":"Introduction to Automata Theory","author":"Hopcroft","year":"1979"},{"key":"10.1016\/0168-0072(90)90080-L_BIB38","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1016\/S0019-9958(86)80029-8","article-title":"Relational queries computable in polynomial time","volume":"68","author":"Immerman","year":"1986","journal-title":"Inform. and Control"},{"key":"10.1016\/0168-0072(90)90080-L_BIB39","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1016\/0012-365X(85)90112-8","article-title":"On random models of finite power and monadic logic","volume":"54","author":"Kaufmann","year":"1983","journal-title":"Discrete Math."},{"key":"10.1016\/0168-0072(90)90080-L_BIB40","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1007\/BF02276797","article-title":"Model interpretability into trees and applications","volume":"17","author":"Korec","year":"1975","journal-title":"Arch. Math. Logik Grundlag."},{"key":"10.1016\/0168-0072(90)90080-L_BIB41","doi-asserted-by":"crossref","unstructured":"D. Kozen, Complexity of Boolean algebras, Theoret. Comp. Sci. 10 (1080) 221\u2013247","DOI":"10.1016\/0304-3975(80)90048-1"},{"key":"10.1016\/0168-0072(90)90080-L_BIB42","doi-asserted-by":"crossref","unstructured":"G.T. Kozlov and A.I. Kokorin, Elementary theory of abelian groups without torsion, with a predicate selecting a subgroup, Algebra and Logic 8 182\u2013190 (English translation)","DOI":"10.1007\/BF02306692"},{"key":"10.1016\/0168-0072(90)90080-L_BIB43","doi-asserted-by":"crossref","first-page":"304","DOI":"10.1016\/0022-0000(80)90027-6","article-title":"Complexity results for classes of quantificational formulas","volume":"21","author":"Lewis","year":"1980","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/0168-0072(90)90080-L_BIB44","series-title":"Ph.D. Thesis","article-title":"On the computational complexity of the theory of abelian groups","author":"Lo","year":"1984"},{"key":"10.1016\/0168-0072(90)90080-L_BIB45","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/BF01786976","article-title":"Complexity classes and finite models","volume":"15","author":"Lynch","year":"1982","journal-title":"Math. Systems Theory"},{"key":"10.1016\/0168-0072(90)90080-L_BIB46","series-title":"Introduction to the General Theory of Algorithms","author":"Machtey","year":"1978"},{"key":"10.1016\/0168-0072(90)90080-L_BIB47","doi-asserted-by":"crossref","first-page":"73","DOI":"10.4064\/fm-81-1-73-89","article-title":"Model completeness for sheaves of structures","volume":"81","author":"Macintyre","year":"1973","journal-title":"Fund. Math."},{"key":"10.1016\/0168-0072(90)90080-L_BIB48","first-page":"477","article-title":"The inherent computational complexity of theories of ordered sets","author":"Meyer","year":"1974","journal-title":"Proc. 1974 Intl. Cong. of Mathematics"},{"key":"10.1016\/0168-0072(90)90080-L_BIB49A","article-title":"Weak monadic second order theory of successor is not elementary recursive","author":"Meyer","year":"1972","journal-title":"Logic Colloquium"},{"key":"10.1016\/0168-0072(90)90080-L_BIB49B","first-page":"132","volume":"453","year":"1975"},{"key":"10.1016\/0168-0072(90)90080-L_BIB50","series-title":"Counter Free Automata","author":"McNaughton","year":"1971"},{"key":"10.1016\/0168-0072(90)90080-L_BIB51","series-title":"Elementary Induction on Abstract Structures","author":"Moschovakis","year":"1974"},{"key":"10.1016\/0168-0072(90)90080-L_BIB52","series-title":"Logic Colloquium '86","first-page":"219","article-title":"Model theory and representation type of algebras","author":"Prest","year":"1988"},{"key":"10.1016\/0168-0072(90)90080-L_BIB53","series-title":"Proc. 1964 Intl. Cong. Logic, Methodology and Philosophy of Science","first-page":"58","article-title":"A simple method for undecidability proofs and some applications","author":"Rabin","year":"1964"},{"key":"10.1016\/0168-0072(90)90080-L_BIB54","first-page":"1","article-title":"Decidability of second order theories and automata on infinite tress","volume":"141","author":"Rabin","year":"1969","journal-title":"Trans. Amer. Math. Soc."},{"key":"10.1016\/0168-0072(90)90080-L_BIB55","series-title":"Research Report no. 136","article-title":"The complexity of theories of the monadic predicate calculus","author":"Rackoff","year":"1975"},{"key":"10.1016\/0168-0072(90)90080-L_BIB56","series-title":"Doctoral Thesis","article-title":"The computational complexity of some logical theories","author":"Rackoff","year":"1975"},{"key":"10.1016\/0168-0072(90)90080-L_BIB57","doi-asserted-by":"crossref","first-page":"561","DOI":"10.2307\/2272034","article-title":"On the complexity of the theories of weak direct powers","volume":"41","author":"Rackoff","year":"1976","journal-title":"J. Symbolic Logic"},{"key":"10.1016\/0168-0072(90)90080-L_BIB58","series-title":"Proc. 10th Ann. ACM Symp. on theory of Computing","first-page":"320","article-title":"Presburger arithmetic with bounded quantifier alternation","author":"Reddy","year":"1978"},{"key":"10.1016\/0168-0072(90)90080-L_BIB59","series-title":"Proc. 6th Ann. ACM Symp. on Theory of Computing","first-page":"161","article-title":"Structure of complexity in the weak monadic second-order theories of monadic second-order theories of the natural numbers","author":"Robertson","year":"1974"},{"key":"10.1016\/0168-0072(90)90080-L_BIB60","first-page":"113","article-title":"On the concept of a differentially closed field","volume":"8F","author":"Robinson","year":"1959","journal-title":"Bull. Res. Council Israel"},{"key":"10.1016\/0168-0072(90)90080-L_BIB61","doi-asserted-by":"crossref","first-page":"179","DOI":"10.4064\/fm-47-2-179-204","article-title":"Solution of a problem of Tarski","volume":"47","author":"Robinson","year":"1959","journal-title":"Fund. Math."},{"key":"10.1016\/0168-0072(90)90080-L_BIB62","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1090\/S0002-9947-1984-0742421-9","article-title":"Complexity of subcases of Presburger arithmetic","volume":"284","author":"Scarpellini","year":"1984","journal-title":"Trans. Amer. Math. Soc."},{"key":"10.1016\/0168-0072(90)90080-L_BIB63","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1002\/malq.19820282203","article-title":"The elementary theory of torsion free abelian groups with a predicate specifying a subgroup","volume":"28","author":"Schmitt","year":"1982","journal-title":"Z. Math. Logik Grundlag. Math."},{"key":"10.1016\/0168-0072(90)90080-L_BIB64","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1145\/322047.322061","article-title":"Separating nondeterministic time complexity classes","volume":"25","author":"Seiferas","year":"1978","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/0168-0072(90)90080-L_BIB65","first-page":"952","article-title":"An interpretation of free algebras in free groups","volume":"21","author":"Semenov","year":"1980","journal-title":"Soviet Math. Dokl."},{"key":"10.1016\/0168-0072(90)90080-L_BIB66","doi-asserted-by":"crossref","first-page":"587","DOI":"10.1070\/IM1984v022n03ABEH001456","article-title":"Logical theories of one-place functions on the set of natural numbers","volume":"22","author":"Semenov","year":"1984","journal-title":"Math. USSR-Izv."},{"key":"10.1016\/0168-0072(90)90080-L_BIB67","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1007\/BF01668813","article-title":"Theories of abelian groups with predicates specifying a subgroup","volume":"14","author":"Slobodskoi","year":"1976","journal-title":"Algebra and Logic"},{"key":"10.1016\/0168-0072(90)90080-L_BIB68","series-title":"Doctoral Thesis","article-title":"The complexity of decision problems in automata and logic","author":"Stockmeyer","year":"1974"},{"key":"10.1016\/0168-0072(90)90080-L_BIB69","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","article-title":"The polynomial-time hierarchy","volume":"3","author":"Stockmeyer","year":"1977","journal-title":"Theoret. Comp. Sci."},{"key":"10.1016\/0168-0072(90)90080-L_BIB70","doi-asserted-by":"crossref","first-page":"1","DOI":"10.2307\/2273858","article-title":"Classifying the computational complexity of problems","volume":"52","author":"Stockmeyer","year":"1987","journal-title":"J. Symbolic Logic"},{"issue":"Ser. I","key":"10.1016\/0168-0072(90)90080-L_BIB71","first-page":"125","article-title":"\u00c9limination des quantificateurs dans la th\u00e9orie \u00e9l\u00e9mentaire des alg\u00e9bres de Boole munies d'une famille d'id\u00e9aux distingu\u00e9s","author":"Touraille","year":"1985","journal-title":"C.R. Acad. Sci. Paris"},{"key":"10.1016\/0168-0072(90)90080-L_BIB72","first-page":"569","article-title":"The impossibility of an algorithm for the decision problem for finite models","volume":"70","author":"Trakhtenbrot","year":"1950","journal-title":"Dokl. Akad. Nauk SSSR"},{"issue":"2","key":"10.1016\/0168-0072(90)90080-L_BIB73A","doi-asserted-by":"crossref","first-page":"230","DOI":"10.1112\/plms\/s2-42.1.230","article-title":"On computable numbers with an application to the Entscheidungsproblem","author":"Turing","year":"1937","journal-title":"Proc. London Math. Soc."},{"key":"10.1016\/0168-0072(90)90080-L_BIB73B","first-page":"544","article-title":"The impossibility of an algorithm for the decision problem for finite models","volume":"43","author":"Trakhtenbrot","year":"1937","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"10.1016\/0168-0072(90)90080-L_BIB74","doi-asserted-by":"crossref","first-page":"39","DOI":"10.2307\/2964336","article-title":"Sentences true in all constructive models","volume":"25","author":"Vaught","year":"1960","journal-title":"J. Symbolic Logic"},{"key":"10.1016\/0168-0072(90)90080-L_BIB75","series-title":"Proc. 1960 Intl. Cong. Logic, Phil. and Methodology of Sci.","first-page":"14","article-title":"On a theorem of Cobham concerning undecidable theories","author":"Vaught","year":"1962"},{"key":"10.1016\/0168-0072(90)90080-L_BIB76","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1016\/0304-3975(83)90038-5","article-title":"Turing machines with linear alternation, theories of bounded concatenation and the decision problem of first-order theories","volume":"23","author":"Vogel","year":"1983","journal-title":"Theoret. Comp. Sci."},{"key":"10.1016\/0168-0072(90)90080-L_BIB77","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1007\/BF02757008","article-title":"The model theory of differential fields revisited","volume":"25","author":"Wood","year":"1976","journal-title":"Israel J. Math."},{"key":"10.1016\/0168-0072(90)90080-L_BIB78","first-page":"503","article-title":"G\u00f6del theorems, exponential difficulty and undecidability of arithmetic theories: an exposition","volume":"42","author":"Young","year":"1985"}],"container-title":["Annals of Pure and Applied Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:016800729090080L?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:016800729090080L?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,4,13]],"date-time":"2019-04-13T03:52:01Z","timestamp":1555127521000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/016800729090080L"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1990,7]]},"references-count":80,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1990,7]]}},"alternative-id":["016800729090080L"],"URL":"https:\/\/doi.org\/10.1016\/0168-0072(90)90080-l","relation":{},"ISSN":["0168-0072"],"issn-type":[{"value":"0168-0072","type":"print"}],"subject":[],"published":{"date-parts":[[1990,7]]}}}