{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T17:35:41Z","timestamp":1725471341692},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540454588"},{"type":"electronic","value":"9783540454595"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11874683_22","type":"book-chapter","created":{"date-parts":[[2006,9,27]],"date-time":"2006-09-27T13:47:26Z","timestamp":1159364846000},"page":"334-348","source":"Crossref","is-referenced-by-count":2,"title":["First-Order Queries over One Unary Function"],"prefix":"10.1007","author":[{"given":"Arnaud","family":"Durand","sequence":"first","affiliation":[]},{"given":"Fr\u00e9d\u00e9ric","family":"Olive","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"22_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/11874683_11","volume-title":"Computer Science Logic","author":"G. Bagan","year":"2006","unstructured":"Bagan, G.: MSO queries on tree decomposable structures are computable with linear delay. In: \u00c9sik, Z. (ed.) CSL 2006. LNCS, vol.\u00a04207, pp. 167\u2013181. Springer, Heidelberg (2006)"},{"key":"22_CR2","unstructured":"Courcelle, B.: Linear delay enumeration and monadic second-order logic (submitted, 2006)"},{"key":"22_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/BFb0028015","volume-title":"Computer Science Logic","author":"A. Durand","year":"1998","unstructured":"Durand, A., Fagin, R., Loescher, B.: Spectra with only unary function symbols. In: Nielsen, M., Thomas, W. (eds.) CSL 1997. LNCS, vol.\u00a01414, pp. 111\u2013126. Springer, Heidelberg (1998)"},{"key":"22_CR4","unstructured":"Durand, A., Grandjean, E.: The complexity of acyclic conjunctive queries revisited. Draft (2005)"},{"key":"22_CR5","doi-asserted-by":"crossref","unstructured":"Durand, A., Grandjean, E.: First-order queries on structures of bounded degree are computable with constant delay. ACM Transactions on Computational Logic (to appear, 2006)","DOI":"10.1145\/1276920.1276923"},{"key":"22_CR6","unstructured":"Durand, A., Grandjean, E., Olive, F.: New results on arity vs. number of variables. Research report 20-2004, LIF, Marseille, France (April 2004)"},{"issue":"6","key":"22_CR7","doi-asserted-by":"publisher","first-page":"716","DOI":"10.1145\/602220.602222","volume":"49","author":"J. Flum","year":"2002","unstructured":"Flum, J., Frick, M., Grohe, M.: Query evaluation via tree decompositions. Journal of the ACM\u00a049(6), 716\u2013752 (2002)","journal-title":"Journal of the ACM"},{"key":"22_CR8","doi-asserted-by":"publisher","first-page":"1184","DOI":"10.1145\/504794.504798","volume":"48","author":"M. Frick","year":"2001","unstructured":"Frick, M., Grohe, M.: Deciding first-order properties of locally tree decomposable structures. Journal of the ACM\u00a048, 1184\u20131206 (2001)","journal-title":"Journal of the ACM"},{"issue":"2","key":"22_CR9","doi-asserted-by":"publisher","first-page":"460","DOI":"10.2307\/2272244","volume":"41","author":"Y. Gurevich","year":"1976","unstructured":"Gurevich, Y.: The decision problem for standard classes. J. Symb. Logic\u00a041(2), 460\u2013464 (1976)","journal-title":"J. Symb. Logic"},{"key":"22_CR10","first-page":"291","volume-title":"18th IEEE Conference in Logic in Computer Science","author":"Y. Gurevich","year":"2003","unstructured":"Gurevich, Y., Shelah, S.: On spectra of one unary function. In: 18th IEEE Conference in Logic in Computer Science, pp. 291\u2013300. IEEE Computer Society Press, Los Alamitos (2003)"},{"key":"22_CR11","series-title":"EATCS Series","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-07003-1","volume-title":"Elements of finite model theory","author":"L. Libkin","year":"2004","unstructured":"Libkin, L.: Elements of finite model theory. EATCS Series. Springer, Heidelberg (2004)"},{"key":"22_CR12","unstructured":"Lindell, S.: A normal form for first-order logic over doubly-linked data structures (submitted, 2006)"},{"issue":"3","key":"22_CR13","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1006\/jcss.1999.1626","volume":"58","author":"C. Papadimitriou","year":"1999","unstructured":"Papadimitriou, C., Yannakakis, M.: On the complexity of database queries. Journal of Computer and System Sciences\u00a058(3), 407\u2013427 (1999)","journal-title":"Journal of Computer and System Sciences"},{"issue":"6","key":"22_CR14","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1017\/S0960129500070079","volume":"6","author":"D. Seese","year":"1996","unstructured":"Seese, D.: Linear time computable problems and first-order descriptions. Mathematical Structures in Computer Science\u00a06(6), 505\u2013526 (1996)","journal-title":"Mathematical Structures in Computer Science"},{"key":"22_CR15","first-page":"266","volume-title":"ACM Symposium on Principles of Database Systems","author":"M.Y. Vardi","year":"1995","unstructured":"Vardi, M.Y.: On the complexity of bounded-variable queries. In: ACM Symposium on Principles of Database Systems, pp. 266\u2013276. ACM Press, New York (1995)"},{"key":"22_CR16","unstructured":"Yannakakis, M.: Algorithms for acyclic database schemes. In: Proceedings of the 7th International Conference on Very Large Databases, pp. 82\u201394 (1981)"}],"container-title":["Lecture Notes in Computer Science","Computer Science Logic"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11874683_22.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T19:47:32Z","timestamp":1605642452000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11874683_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540454588","9783540454595"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/11874683_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}