{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:14:44Z","timestamp":1763468084412},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540615118"},{"type":"electronic","value":"9783540686873"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-61511-3_91","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T16:50:41Z","timestamp":1330275041000},"page":"275-287","source":"Crossref","is-referenced-by-count":25,"title":["An improved lower bound for the elementary theories of trees"],"prefix":"10.1007","author":[{"given":"Sergei","family":"Vorobyov","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,4]]},"reference":[{"key":"28_CR1","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1016\/0304-3975(94)90209-7","volume":"122","author":"H. A\u00eft-Kaci","year":"1994","unstructured":"H. A\u00eft-Kaci, A. Podelski, and G. Smolka. A feature constraint system for logic programming with entailment. Theor. Comput. Sci., 122:263\u2013283, 1994. Preliminary version: 5th Intern. Conf. Fifth Generation Computer Systems, June 1992.","journal-title":"Theor. Comput. Sci."},{"key":"28_CR2","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/0743-1066(95)00033-G","volume":"24","author":"R. Backofen","year":"1995","unstructured":"R. Backofen. A complete axiomatization of a theory with feature and arity constraints. J. Logic Programming, 24:37\u201371, 1995.","journal-title":"J. Logic Programming"},{"key":"28_CR3","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1016\/0304-3975(94)00188-O","volume":"146","author":"R. Backofen","year":"1995","unstructured":"R. Backofen and G. Smolka. A complete and recursive feature theory. Theor. Comput. Sci., 146:243\u2013268, 1995. Also: Report DFKI-RR-92-30, 1992.","journal-title":"Theor. Comput. Sci."},{"key":"28_CR4","doi-asserted-by":"crossref","unstructured":"R. Backofen and R. Treinen. How to win a game with features. In Constraints in Computational Logics'94, volume 845 of Lect. Notes Comput. Sci., pages 320\u2013335. Springer-Verlag, 1994.","DOI":"10.1007\/BFb0016863"},{"key":"28_CR5","doi-asserted-by":"crossref","first-page":"371","DOI":"10.1016\/S0747-7171(89)80017-3","volume":"7","author":"H. Comon","year":"1989","unstructured":"H. Comon and P. Lescanne. Equational problems and disunification. J. Symb. Computation, 7:371\u2013425, 1989.","journal-title":"J. Symb. Computation"},{"key":"28_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0168-0072(90)90080-L","volume":"48","author":"K. J. Compton","year":"1990","unstructured":"K. J. Compton and C. W. Henson. A uniform method for proving lower bounds on the computational complexity of logical. theories. Annals Pure Appl. Logic, 48:1\u201379, 1990.","journal-title":"Annals Pure Appl. Logic"},{"key":"28_CR7","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1070\/RM1965v020n04ABEH001188","volume":"20","author":"Y. L. Ershov","year":"1965","unstructured":"Yu. L. Ershov, I. A. Lavrov, A. D. Taimanov, and M. A. Taitslin. Elementary theories. Russian Math. Surveys, 20:35\u2013105, 1965.","journal-title":"Russian Math. Surveys"},{"key":"28_CR8","doi-asserted-by":"crossref","unstructured":"J. Ferrante and C. W. Rackoff. The computational complexity of logical theories, volume 718 of Lect. Notes Math. Springer-Verlag, 1979.","DOI":"10.1007\/BFb0062837"},{"key":"28_CR9","first-page":"27","volume":"7","author":"M. J. Fisher","year":"1974","unstructured":"M. J. Fisher and M. O. Rabin. Super-exponential complexity of Presburger arithmetic. In SIAM-AMS Proceedings, volume 7, pages 27\u201341, 1974.","journal-title":"SIAM-AMS Proceedings"},{"key":"28_CR10","unstructured":"W. Hodges. Model Theory, volume 42 of Encyclopedia of Mathematics and its Applications. Cambridge Univ. Press, 1993."},{"key":"28_CR11","doi-asserted-by":"publisher","first-page":"503","DOI":"10.1016\/0743-1066(94)90033-7","volume":"19","author":"J. Jaffar","year":"1994","unstructured":"J. Jaffar and M. J. Maher. Constraint logic programming: A survey. J. Logic Programming, 19 & 20:503\u2013581, 1994.","journal-title":"J. Logic Programming"},{"key":"28_CR12","doi-asserted-by":"crossref","unstructured":"K. Kunen. Answer sets and negation as failure. In J.-L. Lassez, editor, 4th International Conference on Logic Programming, volume 1, pages 219\u2013228. MIT Press, 1987.","DOI":"10.1016\/0743-1066(87)90007-0"},{"key":"28_CR13","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1016\/0743-1066(87)90007-0","volume":"4","author":"K. Kunen","year":"1987","unstructured":"K. Kunen. Negation in logic programming. J. Logic Programming, 4:289\u2013308, 1987.","journal-title":"J. Logic Programming"},{"key":"28_CR14","doi-asserted-by":"crossref","unstructured":"M. J. Maher. Complete axiomatizations of the algebras of finite, rational, and infinite trees. In 3rd Annual IEEE Symp. on Logic in Computer Science LICS'88), pages 348\u2013357, 1988.","DOI":"10.1109\/LICS.1988.5132"},{"key":"28_CR15","doi-asserted-by":"crossref","unstructured":"A. I. Malcev. Axiomatizable classes of locally free algebras. In B. F. Wells, editor, The Metamathematics of Algebraic Systems (Collected Papers: 1936\u20131967), volume 66 of Studies in Logic and the Foundations of Mathematics, chapter 23, pages 262\u2013281. North-Holland Pub. Co., 1971.","DOI":"10.1016\/S0049-237X(08)70560-3"},{"key":"28_CR16","doi-asserted-by":"crossref","unstructured":"A. R. Meyer. Weak monadic second-order theory of successor is not elementaryrecursive. In R. Parikh, editor, Logic Colloquium: Symposium on Logic Held at Boston, 1972\u20131973, volume 453 of Lect. Notes Math., pages 132\u2013154. Springer-Verlag, 1975.","DOI":"10.1007\/BFb0064872"},{"key":"28_CR17","unstructured":"P. Odifreddi. Classical recursion theory, volume 125 of Studies in Logic and the Foundations of Mathematics. North-Holland Pub. Co., 1989. Second Edition, 1992."},{"issue":"1","key":"28_CR18","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1145\/322047.322061","volume":"25","author":"J. I. Seiferas","year":"1978","unstructured":"J. I. Seiferas, M. J. Fisher, and A. R. Meyer. Separating nondeterministic time complexity classes. J. ACM, 25(1):146\u2013167, 1978.","journal-title":"J. ACM"},{"key":"28_CR19","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/0743-1066(92)90039-6","volume":"12","author":"G. Smolka","year":"1992","unstructured":"G. Smolka. Feature constraint logics for unification grammars. J. Logic Programming, 12:51\u201387, 1992.","journal-title":"J. Logic Programming"},{"key":"28_CR20","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1016\/0743-1066(94)90044-2","volume":"18","author":"G. Smolka","year":"1994","unstructured":"G. Smolka and R. Treinen. Records for logic programming. J. Logic Programming, 18:229\u2013258, 1994. Also: Report DFKI-RR-92-23, 1992.","journal-title":"J. Logic Programming"},{"key":"28_CR21","doi-asserted-by":"crossref","unstructured":"R. M. Smullyan. Theory of Formal Systems. Princeton University Press, revised edition, 1961.","DOI":"10.1515\/9781400882007"},{"key":"28_CR22","unstructured":"L. J. Stockmeyer. The complexity of decision problems in automata theory and logic. PhD thesis, MIT Lab for Computer Science, 1974. (Also \/MIT\/LCS Tech Rep 133)."},{"key":"28_CR23","doi-asserted-by":"crossref","unstructured":"L. J. Stockmeyer and A. R. Meyer. Word problems requiring exponential time: preliminary report. In 5th Symp. on Theory of Computing, pages 1\u20139, 1973.","DOI":"10.1145\/800125.804029"},{"key":"28_CR24","unstructured":"S. Vorobyov. Theory of finite trees revisited: Application of model-theoretic algebra. Technical Report CRIN-94-R-135, Centre de Recherche en Informatique de Nancy, October 1994."}],"container-title":["Lecture Notes in Computer Science","Automated Deduction \u2014 Cade-13"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-61511-3_91.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T16:07:26Z","timestamp":1605629246000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-61511-3_91"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540615118","9783540686873"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/3-540-61511-3_91","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]}}}