{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T03:10:52Z","timestamp":1767928252221,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540600176","type":"print"},{"value":"9783540494041","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/bfb0022257","type":"book-chapter","created":{"date-parts":[[2005,11,22]],"date-time":"2005-11-22T06:12:29Z","timestamp":1132639949000},"page":"205-216","source":"Crossref","is-referenced-by-count":30,"title":["Logics for context-free languages"],"prefix":"10.1007","author":[{"given":"Clemens","family":"Lautemann","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas","family":"Schwentick","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Denis","family":"Th\u00e9rien","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,15]]},"reference":[{"issue":"1","key":"15_CR1","doi-asserted-by":"crossref","first-page":"113","DOI":"10.2307\/2274958","volume":"55","author":"M. Ajtai","year":"1990","unstructured":"M. Ajtai and R. Fagin. Reachability is harder for directed than for undirected finite graphs. Journal of Symbolic Logic, 55(1):113\u2013150, 1990.","journal-title":"Journal of Symbolic Logic"},{"key":"15_CR2","doi-asserted-by":"publisher","first-page":"478","DOI":"10.1016\/0022-0000(92)90014-A","volume":"44","author":"D. A. M. Barrington","year":"1992","unstructured":"D. A. M. Barrington, K. Compton, H. Straubing, and D. Th\u00e9rien. Regular languages in NC1. Journal of Computer and System Sciences, 44:478\u2013499, 1992.","journal-title":"Journal of Computer and System Sciences"},{"key":"15_CR3","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1002\/malq.19600060105","volume":"6","author":"J. R. B\u00fcchi","year":"1960","unstructured":"J. R. B\u00fcchi. Weak second order arithmetic and finite automata. Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik, 6:66\u201392, 1960.","journal-title":"Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik"},{"key":"15_CR4","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 f\u00fcr Mathematische Logik und Grundlagen der Mathematik, 33:47\u201363, 1987.","journal-title":"Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik"},{"key":"15_CR5","doi-asserted-by":"crossref","first-page":"406","DOI":"10.1016\/S0022-0000(70)80041-1","volume":"4","author":"J. Doner","year":"1970","unstructured":"J. Doner. Tree acceptors and some of their applications. Journal of Computer and System Sciences, 4:406\u2013451, 1970.","journal-title":"Journal of Computer and System Sciences"},{"key":"15_CR6","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. Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik, 21:89\u201396, 1975.","journal-title":"Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik"},{"key":"15_CR7","doi-asserted-by":"crossref","unstructured":"R. Fagin, L. J. Stockmeyer, and M. Y. Vardi. On monadic NP vs. monadic Co-NP. In Proc. 8\nth Annual Conference Structure in Complexity Theory, pages 19\u201330, 1993. To appear in Information and Computation.","DOI":"10.1109\/SCT.1993.336544"},{"key":"15_CR8","unstructured":"F. G\u00e9cseg and M. Steinby. Tree Automata. Akad\u00e9miai Kiad\u00f3, 1984."},{"key":"15_CR9","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/S0019-9958(67)90353-1","volume":"11","author":"J. Mezei","year":"1967","unstructured":"J. Mezei and J. B. Wright. Algebraic automata and context-free sets. Information and Control, 11:3\u201329, 1967.","journal-title":"Information and Control"},{"key":"15_CR10","unstructured":"A. Salomaa. Formal Languages. Academic Press, 1987."},{"key":"15_CR11","doi-asserted-by":"crossref","unstructured":"T. Schwentick. Graph connectivity and monadic NP. In Proc. 35st IEEE Symp. on Foundations of Computer Science, pages 614\u2013622, 1994.","DOI":"10.1109\/SFCS.1994.365730"},{"key":"15_CR12","doi-asserted-by":"crossref","unstructured":"T. Schwentick. Graph connectivity, monadic NP and built-in relations of moderate degree. In Proc. 22nd International Colloq. on Automata, Languages, and Programming, 1995. to appear.","DOI":"10.1007\/3-540-60084-1_92"},{"key":"15_CR13","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1007\/BF01691346","volume":"2","author":"J. W. Thatcher","year":"1968","unstructured":"J. W. Thatcher and J. B. Wright. Generalized finite automata theory with an application to a decision problem of second-order-logic. Mathematical System Theory, 2:57\u201381, 1968.","journal-title":"Mathematical System Theory"}],"container-title":["Lecture Notes in Computer Science","Computer Science Logic"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0022257","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,5]],"date-time":"2019-02-05T06:13:53Z","timestamp":1549347233000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0022257"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540600176","9783540494041"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/bfb0022257","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995]]}}}