{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:22:32Z","timestamp":1725456152049},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540600176"},{"type":"electronic","value":"9783540494041"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/bfb0022255","type":"book-chapter","created":{"date-parts":[[2005,11,22]],"date-time":"2005-11-22T06:12:29Z","timestamp":1132639949000},"page":"177-189","source":"Crossref","is-referenced-by-count":0,"title":["First-order spectra with one binary predicate"],"prefix":"10.1007","author":[{"given":"Arnaud","family":"Durand","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Solomampionona","family":"Ranaivoson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,15]]},"reference":[{"key":"13_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0168-0072(83)90038-6","volume":"24","author":"M. Ajtai","year":"1983","unstructured":"M. Ajtai. \u2211\n                  1\n                  1\n                -formulae on finite structures. Ann. Pure Appl. Logic, 24:pp.1\u201348, 1983.","journal-title":"Ann. Pure Appl. Logic"},{"key":"13_CR2","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1016\/S0022-0000(73)80028-5","volume":"7","author":"S.A Cook","year":"1973","unstructured":"S.A Cook. A hierarchy for nondeterministic time complexity. J. Comput. Systems Sci., vol.7:pp.343\u2013353, 1973.","journal-title":"J. Comput. Systems Sci."},{"key":"13_CR3","first-page":"43","volume":"7","author":"R. Fagin","year":"1974","unstructured":"R. Fagin. Generalized first-order spectra and polynomial-time recognizable sets. Complexity of computations, vol.7:pp.43\u201373, 1974.","journal-title":"Complexity of computations"},{"key":"13_CR4","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. Z. Math. Logik. Grundlag. Math., 21:pp.89\u201396, 1975.","journal-title":"Z. Math. Logik. Grundlag. Math."},{"key":"13_CR5","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1002\/malq.19750210117","volume":"21","author":"R. Fagin","year":"1975","unstructured":"R. Fagin. A spectrum hierarchy. Z. Math. Logik Grundlag. Math., (21):pp.123\u2013134, 1975.","journal-title":"Z. Math. Logik Grundlag. Math."},{"key":"13_CR6","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/0304-3975(93)90218-I","volume":"116","author":"R. Fagin","year":"1993","unstructured":"R. Fagin. Finite-model theory \u2014 a personal perspective. Theoretical Computer Science, (116):pp.3\u201331, 1993.","journal-title":"Theoretical Computer Science"},{"unstructured":"R. Fagin, L.J. Stockmeyer, and M.Y. Vardi. On monadic np vs monadic co \u2014 np. IBM Research Report, 1993.","key":"13_CR7"},{"key":"13_CR8","doi-asserted-by":"publisher","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 J. Comput., vol.13:pp.356\u2013373, 1984.","journal-title":"SIAM J. Comput."},{"key":"13_CR9","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/BF01699468","volume":"18","author":"E. Grandjean","year":"1985","unstructured":"E. Grandjean. Universal quantifiers and time complexity of random access machine. Math. Systems Theory, vol.18:pp.171\u2013187, 1985.","journal-title":"Math. Systems Theory"},{"issue":"2","key":"13_CR10","doi-asserted-by":"publisher","first-page":"136","DOI":"10.1016\/0022-0000(90)90009-A","volume":"40","author":"E. Grandjean","year":"1990","unstructured":"E. Grandjean. First-order spectra with one variable. J. Comput. Systems Sci., vol.40(2):pp.136\u2013153, 1990.","journal-title":"J. Comput. Systems Sci."},{"key":"13_CR11","doi-asserted-by":"crossref","first-page":"139","DOI":"10.2307\/2272354","volume":"39","author":"N.D Jones","year":"1974","unstructured":"N.D Jones and A.L Selman. Turing machines and the spectra of first-order formulas with equality. J. Symb. Logic, vol.39:pp.139\u2013150, 1974.","journal-title":"J. Symb. Logic"},{"key":"13_CR12","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/BF01786976","volume":"15","author":"J.F. Lynch","year":"1982","unstructured":"J.F. Lynch. Complexity classes and theories of finite models. Math. Systems Theory, vol.15:pp.127\u2013144, 1982.","journal-title":"Math. Systems Theory"},{"unstructured":"F. Olive. Personal communication.","key":"13_CR13"},{"unstructured":"P. Pudlak. The observational predicate calculus and complexity of computations. Comment. Math. Univ. Carolin., vol.16, 1975.","key":"13_CR14"},{"key":"13_CR15","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1002\/malq.19870330107","volume":"33","author":"M. Rougemont De","year":"1987","unstructured":"M. De Rougemont. Second-order and inductive definability on finite structures. Zeitschrift fur Mathematische Logik und Grundlagen der Mathematik, vol.33:pp.47\u201363, 1987.","journal-title":"Zeitschrift fur Mathematische Logik und Grundlagen der Mathematik"},{"unstructured":"A.R. Woods. Some problems in logic and number theory and their connections. PhD thesis, University of Manchester, 1981.","key":"13_CR16"}],"container-title":["Lecture Notes in Computer Science","Computer Science Logic"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0022255","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,1,21]],"date-time":"2019-01-21T12:59:10Z","timestamp":1548075550000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0022255"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540600176","9783540494041"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/bfb0022255","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]}}}