{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,1]],"date-time":"2022-04-01T16:10:11Z","timestamp":1648829411972},"reference-count":25,"publisher":"Elsevier BV","issue":"1-3","license":[{"start":{"date-parts":[[2003,7,1]],"date-time":"2003-07-01T00:00:00Z","timestamp":1057017600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,8,22]],"date-time":"2013-08-22T00:00:00Z","timestamp":1377129600000},"content-version":"vor","delay-in-days":3705,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[2003,7]]},"DOI":"10.1016\/s0304-3975(03)00133-6","type":"journal-article","created":{"date-parts":[[2003,4,7]],"date-time":"2003-04-07T19:40:02Z","timestamp":1049744402000},"page":"421-429","source":"Crossref","is-referenced-by-count":2,"title":["A descriptive complexity approach to the linear hierarchy"],"prefix":"10.1016","volume":"304","author":[{"given":"Yassine","family":"Hacha\u00efchi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S0304-3975(03)00133-6_BIB1","unstructured":"J.H. Bennett, On spectra, Doctoral Dissertation, Princeton University, 1962."},{"key":"10.1016\/S0304-3975(03)00133-6_BIB2","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1002\/malq.19600060105","article-title":"Weak second-order arithmetic and finite automata","volume":"6","author":"B\u00fcchi","year":"1960","journal-title":"Zeit. Math. Logik und Grund. Math."},{"key":"10.1016\/S0304-3975(03)00133-6_BIB3","unstructured":"A. Durand, C. Lautemann, M. More, Counting results in weak formalisms, Rapport SDAD, Universit\u00e9 de Caen, 1998."},{"key":"10.1016\/S0304-3975(03)00133-6_BIB4","series-title":"Finite Model Theory","author":"Ebbinghaus","year":"1999"},{"key":"10.1016\/S0304-3975(03)00133-6_BIB5","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1090\/S0002-9947-1961-0139530-9","article-title":"Decision problems of finite automata and related arithmetics","volume":"98","author":"Elgot","year":"1961","journal-title":"Trans. AMS"},{"key":"10.1016\/S0304-3975(03)00133-6_BIB6","unstructured":"R. Fagin, Generalized first-order spectra and polynomial-time recognizable sets, in: R. Karp (Ed.), The Complexity of Computation, SIAM-AMS Proc., Vol. 7, 1974, pp. 27\u201341."},{"key":"10.1016\/S0304-3975(03)00133-6_BIB7","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1142\/S0129054190000217","article-title":"On the notion of linear time computability","volume":"1","author":"Gr\u00e4del","year":"1990","journal-title":"Internat. J. Found. Comput. Sci."},{"key":"10.1016\/S0304-3975(03)00133-6_BIB8","doi-asserted-by":"crossref","unstructured":"E. Grandjean, Sorting, linear time and the satisfiability problem, Ann. Math. Artif. Intell. 16 (1996) 183\u2013236.","DOI":"10.1007\/BF02127798"},{"key":"10.1016\/S0304-3975(03)00133-6_BIB9","doi-asserted-by":"crossref","unstructured":"E. Grandjean, F. Olive, Monadic logical definability of NP-complete problems, in: CSL\u201994, Lecture Notes in Computer Science, Vol. 933, Springer, Berlin, 1995, pp. 190\u2013204.","DOI":"10.1007\/BFb0022256"},{"key":"10.1016\/S0304-3975(03)00133-6_BIB10","doi-asserted-by":"crossref","unstructured":"Y. Gurevich, S. Shelah, Nearly linear time, Logic at Boltik\u201989, Lecture Notes in Computer Science, Vol. 363, Springer, Berlin, 1989, pp. 108\u2013118.","DOI":"10.1007\/3-540-51237-3_10"},{"key":"10.1016\/S0304-3975(03)00133-6_BIB11","unstructured":"Y. Hacha\u0131̈chi, Contibutions \u00e0 la th\u00e9orie des mod\u00e8les finis et \u00e0 la complexit\u00e9 descriptive, Doctoral Dissertation, Universit\u00e9 Denis Diderot, Paris 7, July 2001."},{"key":"10.1016\/S0304-3975(03)00133-6_BIB12","unstructured":"K. Harrow, Sub-elementary classes of functions and relations, Doctoral Dissertation, New York University, 1973."},{"key":"10.1016\/S0304-3975(03)00133-6_BIB13","unstructured":"H. H\u00e4rtig, \u00dcber einen Quantificator mit zwei Wirkungsbereichen, in: Kalmar (Ed.), Colloq. on Foundations of Mathematics, Mathematical Machines and Their Applications, 1965, pp. 31\u201336."},{"key":"10.1016\/S0304-3975(03)00133-6_BIB14","doi-asserted-by":"crossref","first-page":"760","DOI":"10.1137\/0216051","article-title":"Languages that capture complexity classes","volume":"16","author":"Immerman","year":"1987","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0304-3975(03)00133-6_BIB15","doi-asserted-by":"crossref","unstructured":"N. Immerman, Descriptive Complexity, Graduate Texts in Computer Science, Springer, New York, 1999.","DOI":"10.1007\/978-1-4612-0539-5"},{"key":"10.1016\/S0304-3975(03)00133-6_BIB16","doi-asserted-by":"crossref","unstructured":"C. Lautemann, N. Schweikardt, T. Schwentick, A logical characterization of nondeterministic linear time on turing machines, STACS 99, 1999, pp. 143\u2013152.","DOI":"10.1007\/3-540-49116-3_13"},{"key":"10.1016\/S0304-3975(03)00133-6_BIB17","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/BF01786976","article-title":"Complexity classes and theories of finite models","volume":"15","author":"Lynch","year":"1982","journal-title":"Math. System Theory"},{"key":"10.1016\/S0304-3975(03)00133-6_BIB18","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/0304-3975(85)90136-7","article-title":"A logical approach of Petri Net languages","volume":"39","author":"Parigot","year":"1985","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0304-3975(03)00133-6_BIB19","doi-asserted-by":"crossref","first-page":"105","DOI":"10.2307\/2268308","article-title":"Concatenation as a basis for arithmetic from a logical point of view","volume":"11","author":"Quine","year":"1946","journal-title":"J. Symbolic Logic"},{"key":"10.1016\/S0304-3975(03)00133-6_BIB20","first-page":"373","article-title":"Plurality quantification","volume":"27","author":"Rescher","year":"1962","journal-title":"J. Symbolic Logic"},{"key":"10.1016\/S0304-3975(03)00133-6_BIB21","doi-asserted-by":"crossref","unstructured":"R. Smullyan, Theory of formal systems, Annals of Mathematical Studies, Vol. 47, Princeton University Press, Princeton, NJ, 1961.","DOI":"10.1515\/9781400882007"},{"key":"10.1016\/S0304-3975(03)00133-6_BIB22","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","article-title":"The polynomial time hierarchy","volume":"3","author":"Stockmeyer","year":"1977","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0304-3975(03)00133-6_BIB23","doi-asserted-by":"crossref","unstructured":"W. Thomas, Languages, automata and logic, in: G. Rozenberg, A. Salomaa (Eds.), Handbook of Formal Languages, Vol. 3, Springer, Berlin, 1997, pp. 389\u2013455.","DOI":"10.1007\/978-3-642-59126-6_7"},{"key":"10.1016\/S0304-3975(03)00133-6_BIB24","first-page":"326","article-title":"Finite automata and the logic of monadic second order predicates","volume":"140","author":"Trakhtenbrot","year":"1961","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"10.1016\/S0304-3975(03)00133-6_BIB25","doi-asserted-by":"crossref","first-page":"194","DOI":"10.1137\/0207018","article-title":"Rudimentary predicates and relative computation","volume":"7","author":"Wrathall","year":"1978","journal-title":"SIAM J. Comput."}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397503001336?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397503001336?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2021,6,5]],"date-time":"2021-06-05T19:35:02Z","timestamp":1622921702000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0304397503001336"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,7]]},"references-count":25,"journal-issue":{"issue":"1-3","published-print":{"date-parts":[[2003,7]]}},"alternative-id":["S0304397503001336"],"URL":"https:\/\/doi.org\/10.1016\/s0304-3975(03)00133-6","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[2003,7]]}}}