{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,11]],"date-time":"2026-11-11T16:01:13Z","timestamp":1794412873310,"version":"4.9.1"},"publisher-location":"Berlin, Heidelberg","reference-count":61,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540569398","type":"print"},{"value":"9783540478263","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1993]]},"DOI":"10.1007\/3-540-56939-1_106","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T06:57:10Z","timestamp":1330239430000},"page":"606-620","source":"Crossref","is-referenced-by-count":0,"title":["Computing on structures"],"prefix":"10.1007","author":[{"given":"Serge","family":"Abiteboul","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Victor","family":"Vianu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2005,5,28]]},"reference":[{"key":"50_CR1","unstructured":"Afrati, F., S.S. Cosmadakis, M. Yannakakis, On Datalog vs. polynomial time, Proc. 10th ACM Symp. on Principles of Database Systems, 1991."},{"key":"50_CR2","doi-asserted-by":"crossref","unstructured":"S. Abiteboul and P.C. Kanellakis. Object identity as a query language primitive. In Proc. ACM SIGMOD Symp. on the Management of Data, pages 159\u2013173, 1989. to appear in J. ACM.","DOI":"10.1145\/67544.66941"},{"key":"50_CR3","doi-asserted-by":"crossref","unstructured":"S. Abiteboul and V. Vianu. Fixpoint extensions of first-order logic and Datalog-like languages. In Proc. 4th IEEE Symp. on Logic in Computer Science, pages 71\u201379, 1989.","DOI":"10.1109\/LICS.1989.39160"},{"key":"50_CR4","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/0022-0000(90)90036-K","volume":"41","author":"S. Abiteboul","year":"1990","unstructured":"S. Abiteboul and V. Vianu. Procedural languages for database queries and updates. Journal of Computer and System Sciences, 41:181\u2013229, 1990.","journal-title":"Journal of Computer and System Sciences"},{"key":"50_CR5","doi-asserted-by":"crossref","unstructured":"S. Abiteboul and V. Vianu. Generic computation and its complexity. In Proc. ACM SIGACT Symp. on the Theory of Computing, pages 209\u2013219, 1991.","DOI":"10.1145\/103418.103444"},{"key":"50_CR6","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1016\/0022-0000(91)90032-Z","volume":"43","author":"S. Abiteboul","year":"1991","unstructured":"S. Abiteboul and V. Vianu. Datalog extensions for database queries and updates. Journal of Computer and System Sciences, 43:62\u2013124, 1991.","journal-title":"Journal of Computer and System Sciences"},{"key":"50_CR7","unstructured":"S. Abiteboul and V. Vianu. Computing with first-order logic. To appear in Journal of Computer and System Sciences."},{"key":"50_CR8","unstructured":"S. Abiteboul, Moshe Y. Vardi, and V. Vianu. Fixpoint. logics, relational machines, and computational complexity. In Proc. Conf. on Structure in Complexity Theory, Boston, 1992."},{"key":"50_CR9","doi-asserted-by":"crossref","unstructured":"S. Abiteboul, Moshe Y. Vardi, and V. Vianu. Computing with infinitary logic. To appear in Int'l. Conf. on Database Theory, Berlin, 1992.","DOI":"10.1007\/3-540-56039-4_36"},{"key":"50_CR10","doi-asserted-by":"crossref","unstructured":"Barwise, J., Admissible Sets and Structures, Springer-Verlag, 1975.","DOI":"10.1007\/978-3-662-11035-5"},{"key":"50_CR11","doi-asserted-by":"crossref","first-page":"292","DOI":"10.2307\/2272133","volume":"42","author":"J. Barwise","year":"1977","unstructured":"Barwise, J., On Moschovakis closure ordinals, J. Symbolic Logic, 42 (1977), pp. 292\u2013296.","journal-title":"J. Symbolic Logic"},{"key":"50_CR12","unstructured":"Barwise, J., S. Feferman (eds.), Model-Theoretic Logics, Springer-Verlag, 1985."},{"key":"50_CR13","unstructured":"S. R. Buss. Bounded Arithmetics. Bibliopolis, 1986."},{"issue":"2","key":"50_CR14","doi-asserted-by":"crossref","first-page":"156","DOI":"10.1016\/0022-0000(80)90032-X","volume":"21","author":"A. K. Chandra","year":"1980","unstructured":"A.K. Chandra and D. Harel. Computable queries for relational data bases. Journal of Computer and System Sciences, 21(2):156\u2013178, 1980.","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"50_CR15","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/0022-0000(82)90012-5","volume":"25","author":"A. K. Chandra","year":"1982","unstructured":"A.K. Chandra and D. Harel. Structure and complexity of relational queries. Journal of Computer and System Sciences, 25(1):99\u2013128, 1982.","journal-title":"Journal of Computer and System Sciences"},{"key":"50_CR16","doi-asserted-by":"crossref","unstructured":"A.K. Chandra. Programming primitives for database languages. In Proc. ACM Symp. on Principles of Programming Languages, pages 50\u201362, 1981.","DOI":"10.1145\/567532.567537"},{"key":"50_CR17","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1145\/322234.322243","volume":"28","author":"A. Chandra","year":"1981","unstructured":"A. Chandra, D. Kozen, and L. Stockmeyer. Alternation. Journal of the ACM, 28:114\u2013133, 1981.","journal-title":"Journal of the ACM"},{"key":"50_CR18","doi-asserted-by":"crossref","unstructured":"K. J. Compton. An algebra and a logic for NC1. In Proc. 3rd IEEE Symp. on Logic in Computer Science, pages 12\u201321, 1988.","DOI":"10.1109\/LICS.1988.5096"},{"key":"50_CR19","unstructured":"A. Dawar, S. Lindell, and S. Weinstein. Infinitary logic and inductive definability over finite structures. Research report, Univ. of Pennsylvania, 1991."},{"key":"50_CR20","unstructured":"K. Denninghoff and V. Vianu, The Power of Methods with Parallel Semantics, In Proc. Intern. Conf. on Very Large Data Bases, pages 221\u2013232, 1991."},{"key":"50_CR21","unstructured":"R. Fagin. Generalised first-order spectra and polynomial-time recognizable sets. In R. M. Karp, editor, Complexity of Computation, SIAM-AMS Proceedings, Vol. 7, pages 43\u201373, 1974."},{"key":"50_CR22","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1002\/malq.19750210112","volume":"21","author":"R. Fagin","year":"1975","unstructured":"R. Fagin. Monadic generalized spectra. Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik, 21:89\u201396, 1975.","journal-title":"Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik"},{"key":"50_CR23","doi-asserted-by":"crossref","unstructured":"Fagin R., Finite-Model Theory\u2014a Personal Perspective, Proc. 3rd Int'l. Conf. on Database Theory, Springer-Verlag, Lecture Notes in Computer Science 470, 1990, pp. 3\u201324, to appear in Theoretical Computer Science.","DOI":"10.1007\/3-540-53507-1_67"},{"key":"50_CR24","unstructured":"T. Feder. Stable networks and product graphs. PhD thesis, Stanford University, 1981."},{"key":"50_CR25","doi-asserted-by":"crossref","unstructured":"H. Friedman. Algorithmic procedures, generalized turing algorithms, and elementary recursion theory. In R.O.Gangy and C.M.E.Yates, editors, Logic Colloquium '69, pages 361\u2013389. North Holland, 1971.","DOI":"10.1016\/S0049-237X(08)71238-2"},{"key":"50_CR26","doi-asserted-by":"crossref","unstructured":"A. Goerdt. Characterizing complexity classesby higher-type primitive-recursive definitions. In Proc. 4th IEEE Symp. on Logic in Computer Science, pages 364\u2013374, 1989.","DOI":"10.1109\/LICS.1989.39191"},{"key":"50_CR27","doi-asserted-by":"crossref","first-page":"356","DOI":"10.1137\/0213025","volume":"13","author":"E. Grandjean","year":"1984","unstructured":"E. Grandjean. The spectra of first-order sentences and computational complexity. SIAM Journal on Computing, 13:356\u2013373, 1984.","journal-title":"SIAM Journal on Computing"},{"key":"50_CR28","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1007\/BF01699468","volume":"13","author":"E. Grandjean","year":"1985","unstructured":"E. Grandjean. Universal quantifiers and time complexity of random access machines. Mathematical System Theory, 13:171\u2013187, 1985.","journal-title":"Mathematical System Theory"},{"key":"50_CR29","doi-asserted-by":"crossref","unstructured":"Y. Gurevich. Algebras of feasible functions. In Proc. 24th IEEE Symp. on Foundations of Computer Science, pages 210\u2013214, 1983.","DOI":"10.1109\/SFCS.1983.5"},{"key":"50_CR30","doi-asserted-by":"crossref","unstructured":"Y. Gurevich. Toward logic tailored for computational complexity. In M. M. Ricther et al., editor, Computation and Proof Theory, Lecture Notes in Mathematics 1104, pages 175\u2013216. Springer-Verlag, 1984.","DOI":"10.1007\/BFb0099486"},{"key":"50_CR31","unstructured":"Y. Gurevich. Logic and the challenge of computer science. In E. B\u00f6rger, editor, Current trends in theoretical computer science, pages 1\u201357. Computer Science Press, 1988."},{"key":"50_CR32","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1016\/0168-0072(86)90055-2","volume":"32","author":"Y. Gurevich","year":"1986","unstructured":"Y. Gurevich and S. Shelah. Fixed-point extensions of first-order logic. Annals of Pure and Applied Logic, 32:265\u2013280, 1986.","journal-title":"Annals of Pure and Applied Logic"},{"key":"50_CR33","doi-asserted-by":"crossref","unstructured":"J-Y. Girard, A. Scedrov, and P. SCott. Bounded linear logic: a modular approach to polynomial time computability. In S. R. Buss and P. Scott, editors, Feasible Mathematics, pages 195\u2013207. Birkhauser, 1990.","DOI":"10.1007\/978-1-4612-3466-1_11"},{"key":"50_CR34","doi-asserted-by":"crossref","first-page":"336","DOI":"10.1007\/BF00289513","volume":"1","author":"J. Hartmanis","year":"1972","unstructured":"J. Hartmanis. On nondeterminacy in simple computing devices. Acta Informatica, 1:336\u2013344, 1972.","journal-title":"Acta Informatica"},{"key":"50_CR35","doi-asserted-by":"crossref","unstructured":"N. Immerman and E. S. Lander. Describing graphs: a first-order approach to graph canonization. In A. Selman, editor, Complexity Theory Retrospective, pages 59\u201381. Springer-Verlag, 1990.","DOI":"10.1007\/978-1-4612-4478-3_5"},{"key":"50_CR36","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1016\/0022-0000(82)90011-3","volume":"25","author":"N. Immerman","year":"1982","unstructured":"N. Immerman. Upper and lower bounds for first-order expresibility. Journal of Computer and System Sciences, 25:76\u201398, 1982.","journal-title":"Journal of Computer and System Sciences"},{"key":"50_CR37","doi-asserted-by":"crossref","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. Information and Control, 68:86\u2013104, 1986.","journal-title":"Information and Control"},{"key":"50_CR38","doi-asserted-by":"crossref","unstructured":"N. Immerman. Expressibility as a complexity measure: results and directions. In Second Structure in Complexity Conference, pages 194\u2013202, 1987.","DOI":"10.1109\/PSCT.1987.10319271"},{"key":"50_CR39","doi-asserted-by":"crossref","first-page":"760","DOI":"10.1137\/0216051","volume":"16","author":"N. Immerman","year":"1987","unstructured":"N. Immerman. Languages that capture complexity classes. SIAM Journal of Computing, 16:760\u2013778, 1987.","journal-title":"SIAM Journal of Computing"},{"key":"50_CR40","doi-asserted-by":"crossref","unstructured":"N. Immerman. Descriptive and computational complexity. In J. Hartmanis, editor, Computational Complexity Theory, Proc. Symp. Applied Math., Vol. 38, pages 75\u201391. American Mathematical Society, 1989.","DOI":"10.1090\/psapm\/038\/1020810"},{"key":"50_CR41","doi-asserted-by":"crossref","first-page":"139","DOI":"10.2307\/2272354","volume":"39","author":"N. G. Jones","year":"1974","unstructured":"N. G. Jones and A.L. Selman. Turing machines and the spectra of first-order formulas. Journal of Symbolic Logic, 39:139\u2013150, 1974.","journal-title":"Journal of Symbolic Logic"},{"key":"50_CR42","doi-asserted-by":"crossref","unstructured":"P. C. Kanellakis. Elements of relational database theory. In J. Van Leeuwen, editor, Handbook of Theoretical Computer Science, pages 1074\u20131156. North Holland, 1991.","DOI":"10.1016\/B978-0-444-88074-1.50022-6"},{"key":"50_CR43","doi-asserted-by":"crossref","unstructured":"Ph. G. Kolaitis and M. Y. Vardi. 0\u20131 laws for infinitary logics. In Proc. 5th IEEE Symp. on Logic in Computer Science, pages 156\u2013167, 1990.","DOI":"10.1109\/LICS.1990.113742"},{"key":"50_CR44","doi-asserted-by":"crossref","unstructured":"Ph. G. Kolaitis and M. Y. Vardi. On the expressive power of Datalog: tools and a case study. In Proc. 9th ACM Symp. on Principles of Database Systems, pages 61\u201371, 1990. Full version appeared in IBM Research Report RJ8010, March 1991.","DOI":"10.1145\/298514.298542"},{"key":"50_CR45","unstructured":"Kolaitis, P., M.Y. Vardi, Fixpoint vs. infinitary logic in finite-model theory, to appear in Proc. 7th IEEE Symp. on Logic in Computer Science, 1992."},{"key":"50_CR46","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1016\/0022-0000(89)90019-6","volume":"39","author":"D. Leivant","year":"1989","unstructured":"D. Leivant. Descriptive characterization of computational complexity. Journal of Computer and System Sciences, 39:51\u201383, 1989.","journal-title":"Journal of Computer and System Sciences"},{"key":"50_CR47","unstructured":"D. Leivant. Monotonic use of space and computational complexity over abstract structures. Unpublished manuscript, 1989."},{"key":"50_CR48","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/0890-5401(90)90006-4","volume":"89","author":"D. Leivant","year":"1990","unstructured":"D. Leivant. Inductive definitions over finite structures. Information and Computation, 89:95\u2013108, 1990.","journal-title":"Information and Computation"},{"key":"50_CR49","doi-asserted-by":"crossref","unstructured":"D. Leivant. A foundational delineation of computational feasibility. In Proc. 6th IEEE Symp. on Logic in Computer Science, pages 2\u201311, 1991.","DOI":"10.1109\/LICS.1991.151625"},{"key":"50_CR50","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/0304-3975(91)90048-7","volume":"85","author":"S. Lindell","year":"1991","unstructured":"S. Lindell. An analysis of fixed point queries on binary trees. Theoretical Computer Science, 85:75\u201395, 1991.","journal-title":"Theoretical Computer Science"},{"key":"50_CR51","unstructured":"D. Luckham and D. Park. The undecidability of the equivalence problem for program schemata. Technical Report UCSC-CRL-89-40, UCSC, December 1989. to appear in ACM Transactions on Database Systems."},{"key":"50_CR52","doi-asserted-by":"crossref","first-page":"220","DOI":"10.1016\/S0022-0000(70)80022-8","volume":"4","author":"D. Luckham","year":"1970","unstructured":"D. Luckham, D. Park, and M. Paterson. Formalized computer programs. Journal of Computer and System Sciences, 4:220\u2013249, 1970.","journal-title":"Journal of Computer and System Sciences"},{"key":"50_CR53","unstructured":"Y. N. Moschovakis. Elementary Induction on Abstract Structures. North Holland, 1974."},{"key":"50_CR54","doi-asserted-by":"crossref","unstructured":"M. de Rougemont. Uniform definability on finite structures with successor. In Proc. 16th ACM Symp. on Theory of Computing, pages 409\u2013417, 1984.","DOI":"10.1145\/800057.808707"},{"key":"50_CR55","first-page":"319","volume":"16","author":"V. Yu. Sazonov","year":"1980","unstructured":"V. Yu. Sazonov. Polynomial computability and recursivity in finite domains. Elektronische Informationverarbeitung und Kybernetik, 16:319\u2013323, 1980.","journal-title":"Elektronische Informationverarbeitung und Kybernetik"},{"key":"50_CR56","doi-asserted-by":"crossref","unstructured":"J. C. Shepherdson. Algorithmic procedures, generalized turing algorithms, and elementary recursion theory. In L.A. Harrington et al., editor, Harvey Friedman's research on the foundations of mathematics, pages 285\u2013308. North Holland, 1985.","DOI":"10.1016\/S0049-237X(09)70163-6"},{"key":"50_CR57","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","volume":"3","author":"L. J. Stockmeyer","year":"1977","unstructured":"L. J. Stockmeyer. The polynomial-time hierarchy. Theoretical Computer Science, 3:1\u201322, 1977.","journal-title":"Theoretical Computer Science"},{"key":"50_CR58","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1080\/01445348608837096","volume":"7","author":"A. Tarski","year":"1986","unstructured":"A. Tarski. What are logical notions? History and Philosophy of Logic, 7:143\u2013154, 1986. (Ed. J. Corcoran).","journal-title":"History and Philosophy of Logic"},{"key":"50_CR59","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1016\/0304-3975(88)90052-7","volume":"60","author":"J. Tiuryn","year":"1988","unstructured":"J. Tiuryn and P. Urzyczyn. Some relationships between logic of programs and complexity theory. Theoretical Computer Science, 60:83\u2013108, 1988.","journal-title":"Theoretical Computer Science"},{"key":"50_CR60","unstructured":"J.D. Ullman. Principles of Database and Knowledge Base Systems: Volume I and II. Computer Science Press, 1988."},{"key":"50_CR61","doi-asserted-by":"crossref","unstructured":"M.Y. Vardi. The complexity of relational query languages. In Proc. ACM SIGACT Symp. on the Theory of Computing, pages 137\u2013146, 1982.","DOI":"10.1145\/800070.802186"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-56939-1_106.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T17:58:57Z","timestamp":1742579937000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-56939-1_106"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993]]},"ISBN":["9783540569398","9783540478263"],"references-count":61,"URL":"https:\/\/doi.org\/10.1007\/3-540-56939-1_106","relation":{"is-part-of":[{"id-type":"doi","id":"https:\/\/doi.org\/10.1007\/3-540-56939-1","asserted-by":"object"}]},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993]]}}}