{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,21]],"date-time":"2026-03-21T02:34:36Z","timestamp":1774060476174,"version":"3.50.1"},"publisher-location":"Berlin\/Heidelberg","reference-count":16,"publisher":"Springer-Verlag","isbn-type":[{"value":"3540537090","type":"print"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0020821","type":"book-chapter","created":{"date-parts":[[2005,11,13]],"date-time":"2005-11-13T06:07:52Z","timestamp":1131862072000},"page":"466-477","source":"Crossref","is-referenced-by-count":15,"title":["The expressive power of second order Horn logic"],"prefix":"10.1007","author":[{"given":"Erich","family":"Gr\u00e4del","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"39_CR1","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1007\/BF00289267","volume":"15","author":"S. Aanderaa","year":"1981","unstructured":"S. Aanderaa and E. B\u00f6rger, The equivalence of Horn and network complexity for Boolean functions, Acta Informatica 15 (1981),303\u2013307.","journal-title":"Acta Informatica"},{"key":"39_CR2","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/0022-0000(82)90012-5","volume":"25","author":"A. Chandra","year":"1982","unstructured":"A. Chandra and D. Harel, Structure and Complexity of Relational Queries, J. Comp. Syst. Sciences 25 (1982), 99\u2013128.","journal-title":"J. Comp. Syst. Sciences"},{"key":"39_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0743-1066(85)90002-0","volume":"1","author":"A. Chandra","year":"1985","unstructured":"A. Chandra and D. Harel, Horn Clause Queries and Generalizations, J. Logic Programming 1 (1985), 1\u201315.","journal-title":"J. Logic Programming"},{"key":"39_CR4","doi-asserted-by":"crossref","unstructured":"E. Dahlhaus, Skolem Normal Forms Concerning the Least Fixed Point, in: \u201cComputation Theory and Logic\u201d (E. B\u00f6rger, Ed.), Lecture Notes in Computer Science Nr. 270, Springer 1987, 101\u2013106.","DOI":"10.1007\/3-540-18170-9_158"},{"key":"39_CR5","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1016\/0743-1066(84)90014-1","volume":"3","author":"W. Dowling","year":"1984","unstructured":"W. Dowling and F. Gallier, Linear-Time Algorithms for Testing the Satisfiability of Propositional Horn Formulae, J. Logic Programming 3 (1984), 267\u2013284.","journal-title":"J. Logic Programming"},{"key":"39_CR6","first-page":"43","volume":"7","author":"R. Fagin","year":"1974","unstructured":"R. Fagin, Generalized First-Order Spectra and Polynomial-Time Recognizable Sets, SIAM-AMS Proc. 7 (1974), 43\u201373.","journal-title":"SIAM-AMS Proc."},{"key":"39_CR7","unstructured":"Y. Gurevich, Logic and the Challenge of Computer Science, in: \u201cTrends in Theoretical Computer Science\u201d (E. B\u00f6rger, Ed.), Computer Science Press (1988), 1\u201357."},{"key":"39_CR8","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/S0019-9958(86)80029-8","volume":"68","author":"N. Immerman","year":"1986","unstructured":"N. Immerman, Relational Queries Computable in Polynomial Time, Inf. and Control 68 (1986), 86\u2013104.","journal-title":"Inf. and Control"},{"key":"39_CR9","doi-asserted-by":"publisher","first-page":"760","DOI":"10.1137\/0216051","volume":"16","author":"N. Immerman","year":"1987","unstructured":"N. Immerman, Languages that Capture Complexity Classes, SIAM J. Comput. 16 (1987), 760\u2013778.","journal-title":"SIAM J. Comput."},{"key":"39_CR10","doi-asserted-by":"crossref","unstructured":"N. Immerman, Expressibility as a Complexity Measure: Results and Directions, Proc. of 2nd Conf. on Structure in Complexity Theory (1987), 194\u2013202.","DOI":"10.1109\/PSCT.1987.10319271"},{"key":"39_CR11","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1090\/psapm\/038\/1020810","volume":"38","author":"N. Immerman","year":"1989","unstructured":"N. Immerman, Descriptive and Computational Complexity, in: \u201cComputational Complexity Theory\u201d, Proc. AMS Symposia in Appl. Math. 38 (1989), 75\u201391.","journal-title":"Proc. AMS Symposia in Appl. Math."},{"key":"39_CR12","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1016\/0743-1066(87)90014-8","volume":"4","author":"A. Itai","year":"1987","unstructured":"A. Itai and J. Makowsky, Unification as a complexity measure for Logic Programming, J. Logic Programming 4 (1987), 105\u2013117.","journal-title":"J. Logic Programming"},{"key":"39_CR13","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1016\/0304-3975(76)90068-2","volume":"3","author":"N. Jones","year":"1977","unstructured":"N. Jones and W. Laaser, Complete problems for deterministic polynomial time, Theoret. Comp. Sci 3 (1977), 105\u2013117.","journal-title":"Theoret. Comp. Sci"},{"key":"39_CR14","unstructured":"P. Kolaitis, The Expressive Power of Stratified Logic Programs, to appear in Information and Computation."},{"key":"39_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","volume":"3","author":"L. Stockmeyer","year":"1977","unstructured":"L. Stockmeyer, The polynomial-time hierarchy, Theoret. Comp. Sci. 3 (1977), 1\u201322.","journal-title":"Theoret. Comp. Sci."},{"key":"39_CR16","doi-asserted-by":"crossref","unstructured":"M. Vardi, Complexity of Relational Query Languages, Proc. of 14th STOC (1982), 137\u2013146.","DOI":"10.1145\/800070.802186"}],"container-title":["Lecture Notes in Computer Science","STACS 91"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0020821.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,31]],"date-time":"2024-01-31T16:35:57Z","timestamp":1706718957000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0020821"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["3540537090"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/bfb0020821","relation":{},"subject":[]}}