{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:32:51Z","timestamp":1725456771039},"publisher-location":"Berlin\/Heidelberg","reference-count":10,"publisher":"Springer-Verlag","isbn-type":[{"type":"print","value":"3540529535"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0029615","type":"book-chapter","created":{"date-parts":[[2005,12,1]],"date-time":"2005-12-01T05:33:46Z","timestamp":1133415226000},"page":"246-253","source":"Crossref","is-referenced-by-count":1,"title":["Query languages which express all PTIME queries for trees and unicyclic graphs"],"prefix":"10.1007","author":[{"given":"Pratul","family":"Dublish","sequence":"first","affiliation":[]},{"given":"S. N.","family":"Maheshwari","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"24_CR1","unstructured":"A.V.Aho, J.E.Hopcroft and J.D.Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974."},{"key":"24_CR2","doi-asserted-by":"crossref","unstructured":"A.V.Aho and J.D.Ullman, Universality of Data Retrieval Languages, Proc of 6th ACM POPL, 1979.","DOI":"10.1145\/567752.567763"},{"key":"24_CR3","doi-asserted-by":"crossref","unstructured":"A.K. Chandra and D. Harel, Structure and Complexity of Relational Queries, JCSS, 25 (1), 1982.","DOI":"10.1016\/0022-0000(82)90012-5"},{"key":"24_CR4","unstructured":"Jin-yi Cai and N.Immerman, An Optimal Lower Bound on the Number of Variables for Graph Identification, Tech. Report, Dept. of Computer Science, Yale University, 1988."},{"key":"24_CR5","unstructured":"P.Dublish, Optimization and Expressibility of Relational Queries, Ph.D. Thesis, Dept of Computer Science & Engg., IIT Delhi, 1988."},{"key":"24_CR6","unstructured":"P.Dublish and S.N.Maheshwari, Query Languages which Express all PTIME Queries for Trees, Technical Report 2\/89, Institut f\u00fcr Informatik, Universit\u00e4t Hildesheim, 1989."},{"key":"24_CR7","unstructured":"H.Enderton, A Mathematical Introduction to Logic, Academic Press, 1972."},{"key":"24_CR8","doi-asserted-by":"crossref","unstructured":"Y.Gurevich and S.Shelah, Fixed-Point Extensions of First-Order Logic, Proc. of 26th IEEE FOCS, 1985.","DOI":"10.1109\/SFCS.1985.27"},{"key":"24_CR9","doi-asserted-by":"crossref","unstructured":"N.Immerman, Relational Queries Computable in Polynomial Time, Information and Control, 68, 1986.","DOI":"10.1016\/S0019-9958(86)80029-8"},{"key":"24_CR10","unstructured":"S.Lindell, The Logical Complexity of Queries on Unordered Graphs, Ph.D. Thesis, Dept. of Computer Science, UCLA, 1987."}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1990"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.springerlink.com\/index\/pdf\/10.1007\/BFb0029615","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,11]],"date-time":"2020-04-11T08:16:00Z","timestamp":1586592960000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0029615"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["3540529535"],"references-count":10,"URL":"https:\/\/doi.org\/10.1007\/bfb0029615","relation":{},"subject":[]}}