{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:24:23Z","timestamp":1725488663230},"publisher-location":"Berlin, Heidelberg","reference-count":38,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540671008"},{"type":"electronic","value":"9783540465645"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-46564-2_10","type":"book-chapter","created":{"date-parts":[[2007,8,11]],"date-time":"2007-08-11T10:03:18Z","timestamp":1186826598000},"page":"156-175","source":"Crossref","is-referenced-by-count":2,"title":["Capturing LOGSPACE over Hereditarily-Finite Sets"],"prefix":"10.1007","author":[{"given":"Alexander","family":"Leontjev","sequence":"first","affiliation":[]},{"given":"Vladimir","family":"Sazonov","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2001,11,9]]},"reference":[{"key":"10_CR1","volume-title":"Foundations of Databases","author":"S. Abiteboul","year":"1995","unstructured":"Abiteboul, S., Hull, R., Vianu, V.: Foundations of Databases. Addison-Wesley, Reading-Massachusetts, 1995"},{"key":"10_CR2","series-title":"Lect Notes Comput Sci","first-page":"1","volume-title":"Database Theory \u2014 ICDT\u201997","author":"S. Abiteboul","year":"1995","unstructured":"Abiteboul, S.: Querying semi-structured data. Database Theory \u2014 ICDT\u201997, 6th International Conference, Delphi, Greece, January 1997, Proceedings. Lecture Notes in Computer Science 1186 Springer (1995) 1\u201318"},{"key":"10_CR3","unstructured":"Abiteboul, S., Beeri, C.: On the power of languages for the manipulation of complex objects. INRIA research report 846 (1988). Abstract in Proc. International Workshop on Theory and Applications of Nested Relations and Complex Objects. Darmstadt (1987)"},{"key":"10_CR4","series-title":"Lect Notes Comput Sci","first-page":"262","volume-title":"Database Theory \u2014 ICDT\u201997","author":"S. Abiteboul","year":"1995","unstructured":"Abiteboul, S., Vianu, V.: Queries and computation on the Web. Database Theory \u2014 ICDT\u201997, 6th International Conference, Delphi, Greece, January 1997, Proceedings. Lecture Notes in Computer Science 1186 Springer (1995) 262\u2013275"},{"key":"10_CR5","unstructured":"Aczel, P.: Non-Well-Founded Sets. CSLI Lecture Notes. No 14 (1988)"},{"key":"10_CR6","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-11035-5","volume-title":"Admissible Sets and Structures","author":"J.K. Barwise","year":"1975","unstructured":"Barwise, J.K.: Admissible Sets and Structures. Springer, Berlin, 1975"},{"key":"10_CR7","doi-asserted-by":"crossref","unstructured":"Buneman, P., Davidson, S., Hillebrand, G., Suciu, D.: A query Language and Optimization Techniques for Unstructured Data. Proc. of SIGMOD, San Diego, 1996","DOI":"10.1145\/233269.233368"},{"key":"10_CR8","doi-asserted-by":"crossref","unstructured":"Val Breazu-Tannen and Subrahmanyam, R.: Logical and computational aspects of programming with sets\/bags\/lists, a manuscript, 1991.","DOI":"10.1007\/3-540-54233-7_125"},{"key":"10_CR9","series-title":"Lect Notes Comput Sci","first-page":"56","volume-title":"CSL\u201987","author":"E. Dahlhaus","year":"1987","unstructured":"Dahlhaus, E.: Is SETL a suitable language for parallel programming \u2014 a theoretical approach. B\u00f6rger, E., Kleine Buning, H., Richter, M.M. ed. CSL\u201987. LNCS 329 (1987) 56\u201363"},{"key":"10_CR10","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"160","DOI":"10.1007\/3-540-16442-1_12","volume-title":"ESOP\u201986","author":"E. Dahlhaus","year":"1986","unstructured":"Dahlhaus, E., Makowsky, J.: The Choice of programming Primitives in SETL-like Languages. ESOP\u201986. LNCS 213 (1986) 160\u2013172"},{"key":"10_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0890-5401(92)90074-P","volume":"101","author":"E. Dahlhaus","year":"1992","unstructured":"Dahlhaus, E., Makowsky, J.: Query languages for hierarchic databases. Information and Computation 101 (1992) 1\u201332","journal-title":"Information and Computation"},{"key":"10_CR12","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1090\/pspum\/013.2\/0376348","volume":"13","author":"R.O. Gandy","year":"1974","unstructured":"Gandy, R.O.: Set theoretic functions for elementary syntax. Proc. Symp. in Pure Math. Vol. 13, Part II (1974) 103\u2013126","journal-title":"Proc. Symp. in Pure Math."},{"key":"10_CR13","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R. and Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H.Freeman and Company, New York, 1979."},{"key":"10_CR14","doi-asserted-by":"crossref","unstructured":"Grumbach, S., Vianu, V.: Tractable query languages for complex object databases. Rapports de Recherche N 1573. INRIA. 1991","DOI":"10.1145\/113413.113442"},{"key":"10_CR15","first-page":"210","volume":"24","author":"Y. Gurevich","year":"1983","unstructured":"Gurevich, Y.: Algebras of feasible functions. FOCS 24 (1983) 210\u2013214","journal-title":"FOCS"},{"key":"10_CR16","doi-asserted-by":"crossref","unstructured":"Immerman, N.: \u2018Relational queries computable in polynomial time\u2019, in: Proc. 14th. ACM Symp. on Theory of Computing, (1982) 147\u2013152; cf. also Inform. and Control 68 (1986) 86\u2013104.","DOI":"10.1016\/S0019-9958(86)80029-8"},{"issue":"4","key":"10_CR17","doi-asserted-by":"publisher","first-page":"760","DOI":"10.1137\/0216051","volume":"16","author":"N. Immerman","year":"1987","unstructured":"Immerman, N.: Languages which captures complexity classes. SIAM J. Comput., 164 (1987) 760\u2013778","journal-title":"SIAM J. Comput."},{"key":"10_CR18","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1090\/psapm\/038\/1020810","volume":"38","author":"N. Immerman","year":"1989","unstructured":"Immerman, N.: Descriptive and computational complexity. Proceedings of Symposia in Applied Mathematics, 38 (1989) 75\u201391","journal-title":"Proceedings of Symposia in Applied Mathematics"},{"issue":"N 1","key":"10_CR19","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/0304-3975(94)00287-8","volume":"155","author":"N. Immerman","year":"1996","unstructured":"Immerman, N., Patnaik, S. and Stemple, D.: The expressiveness of a family of finite set languages. Theoretical Computer Science, 155,N 1 (1996) 111\u2013140","journal-title":"Theoretical Computer Science"},{"key":"10_CR20","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1016\/0003-4843(72)90001-0","volume":"4","author":"R.B. Jensen","year":"1972","unstructured":"Jensen, R.B.: The fine structure of the constructible hierarchy. Ann. Math. Logic 4 (1972) 229\u2013308","journal-title":"Ann. Math. Logic"},{"key":"10_CR21","doi-asserted-by":"crossref","unstructured":"Kosky, A.: Observational properties of databases with object identity. Technical Report MS-CIS-95-20. Dept. of Computer and Information Science, University of Pennsylvania (1995)","DOI":"10.14236\/ewic\/DBPL1995.16"},{"key":"10_CR22","doi-asserted-by":"crossref","unstructured":"Kuper, G.M., Vardi, M.Y.: A new approach to database logic. Proc. 3rd ACM Symp. on Principles of Database Systems 1984","DOI":"10.21236\/ADA141130"},{"key":"10_CR23","unstructured":"Levy, A.: A hierarchy of formulas in set theory. Mem. Amer. Math. Soc. No. 57 (1965) 76pp. MR 32 N 7399"},{"issue":"1","key":"10_CR24","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/S0304-3975(96)00174-0","volume":"175","author":"A. Lisitsa","year":"1997","unstructured":"Lisitsa, A. and Sazonov, V.Yu: Delta-languages for sets and LOGSPACE computable graph transformers. Theoretical Computer Science 175,1 (1997), 183\u2013222","journal-title":"Theoretical Computer Science"},{"issue":"1\u20132","key":"10_CR25","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1016\/S0304-3975(98)00312-0","volume":"224","author":"A. Lisitsa","year":"1999","unstructured":"Lisitsa, A. and Sazonov, V.Yu: Linear ordering on graphs, anti-founded sets and polynomial time computability, Theoretical Computer Science 224,1\u20132 (1999) 173\u2013213. (Cf. also earlier versions in Proc. of the 4th International Symp. \u2018Logical Foundations of Computer Science\u2019, Yaroslavl, Russia, 1997, Springer LNCS 1234 (1997), 178\u2013188, and http:\/\/dimacs.rutgers.edu\/TechnicalReports\/1997.html .)","journal-title":"Theoretical Computer Science"},{"key":"10_CR26","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"172","DOI":"10.1007\/3-540-63385-5_42","volume-title":"Computational Logic and Proof Theory","author":"A. Lisitsa","year":"1997","unstructured":"Lisitsa, A. and Sazonov, V.Yu: Bounded Hyperset Theory and Web-like Data Bases. In: Georg Gottlob, Alexander Leitsch, Daniele Mundici (Eds.): Computational Logic and Proof Theory, 5th Kurt G\u00f6del Colloquium, KGC\u201997, Vienna, Austria, August 25\u201329, 1997, Proceedings. LNCS 1289, Springer, (1997) 172\u2013185. (Cf. also http:\/\/dimacs.rutgers.edu\/TechnicalReports\/1997.html .)"},{"key":"10_CR27","unstructured":"Livchak, A.B.: Languages of polynomial queries. Raschet i optimizacija teplotehnicheskih ob\u2019ektov s pomosh\u2019ju EVM, Sverdlovsk, 1982, p. 41 (in Russian)."},{"key":"10_CR28","doi-asserted-by":"crossref","unstructured":"Mendelzon, A. O., Mihaila, G.A., Milo, T.: Querying the World Wide Web. Draft, available by ftp:\/\/milo@math.tau.ac.il (1996)","DOI":"10.1007\/s007990050004"},{"issue":"N7","key":"10_CR29","first-page":"319","volume":"16","author":"V.Yu. Sazonov","year":"1980","unstructured":"Sazonov, V.Yu.: Polynomial computability and recursivity in finite domains. Elektronische Informationsverarbeitung und Kybernetik. 16,N7 (1980) 319\u2013323","journal-title":"Elektronische Informationsverarbeitung und Kybernetik"},{"key":"10_CR30","unstructured":"Sazonov, V.Yu.: Bounded set theory and polynomial computability. All Union Conf. Appl. Logic., Proc. Novosibirsk (1985) 188\u2013191 (In Russian)"},{"key":"10_CR31","first-page":"30","volume":"107","author":"V.Yu. Sazonov","year":"1985","unstructured":"Sazonov, V.Yu.: The Collection Principle and the Existential Quantifier. Logikomatematicheskie problemy MOZ., Vychislitel\u2019nye sistemy 107 (1985) 30\u201339 (In Russian). (English translation in: Amer. Math. Soc. Transl. (2) Vol. 142 (1989) 1\u20138)","journal-title":"Logikomatematicheskie problemy MOZ., Vychislitel\u2019nye sistemy"},{"key":"10_CR32","first-page":"110","volume":"122","author":"V.Yu. Sazonov","year":"1987","unstructured":"Sazonov, V.Yu.: Bounded set theory, polynomial computability and \u0394-programming. Application aspects of mathematical logic. Computing systems 122 (1987) 110\u2013132 (In Russian) Cf. also a short English version of this paper in: LNCS 278 Springer (1987) 391\u2013397","journal-title":"Computing systems"},{"key":"10_CR33","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1016\/0304-3975(93)90345-T","volume":"119","author":"V.Yu. Sazonov","year":"1993","unstructured":"Sazonov, V.Yu.: Hereditarily-finite sets, data bases and polynomial-time computability. Theoretical Computer Science 119 Elsevier (1993) 187\u2013214","journal-title":"Theoretical Computer Science"},{"key":"10_CR34","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1007\/BFb0022280","volume-title":"Computer Science Logic","author":"V.Yu. Sazonov","year":"1995","unstructured":"Sazonov, V.Yu.: A bounded set theory with anti-foundation axiom and inductive definability. Computer Science Logic, 8th Workshop, CSL\u201994 Kazimierz, Poland, September 1994, Selected Papers. LNCS 933 Springer (1995) 527\u2013541"},{"key":"10_CR35","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-94-017-0487-8_5","volume":"I","author":"V. Sazonov","year":"1997","unstructured":"Sazonov, V.Yu: On Bounded Set Theory. Invited talk on the 10th International Congress on Logic, Methodology and Philosophy of Sciences, Florence, August 1995, in Volume I: Logic and Scientific Method, Kluwer Academic Publishers, 1997, pp. 85\u2013103","journal-title":"Logic and Scientific Method"},{"key":"10_CR36","volume-title":"Mathematical Logic","author":"J. R. Shoenfield","year":"1967","unstructured":"Shoenfield, J. R.: Mathematical Logic. Addison-Wesley, Reading, MA, 1967"},{"key":"10_CR37","unstructured":"Szelepcs\u00e9nyi, R.: 1987, The method of forcing for nondeterministic automata. Bull. European Association Theor. Comp. Sci. (Oct. 1987) 96\u2013100"},{"key":"10_CR38","unstructured":"Vardi, M.Y.: The complexity of relational query languages. Proc. of the 14th. ACM Symp. on Theory of Computing, (1982) 137\u2013146"}],"container-title":["Lecture Notes in Computer Science","Foundations of Information and Knowledge Systems"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-46564-2_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,21]],"date-time":"2021-08-21T15:39:27Z","timestamp":1629560367000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-46564-2_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540671008","9783540465645"],"references-count":38,"URL":"https:\/\/doi.org\/10.1007\/3-540-46564-2_10","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}