{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,17]],"date-time":"2025-01-17T09:43:08Z","timestamp":1737106988171,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540434535"},{"type":"electronic","value":"9783540460114"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-46011-x_4","type":"book-chapter","created":{"date-parts":[[2007,6,18]],"date-time":"2007-06-18T22:54:16Z","timestamp":1182207256000},"page":"37-56","source":"Crossref","is-referenced-by-count":4,"title":["Second-Order Logic over Strings: Regular and Non-regular Fragments"],"prefix":"10.1007","author":[{"given":"Thomas","family":"Eiter","sequence":"first","affiliation":[]},{"given":"Georg","family":"Gottlob","sequence":"additional","affiliation":[]},{"given":"Thomas","family":"Schwentick","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2002,3,19]]},"reference":[{"issue":"6","key":"4_CR1","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"H. L. Bodlaender","year":"1996","unstructured":"H. L. Bodlaender. A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on Computing, 25(6):1305\u20131317, 1996.","journal-title":"SIAM Journal on Computing"},{"key":"4_CR2","doi-asserted-by":"crossref","unstructured":"E. B\u00f6rger, E. Gr\u00e4del, and Y. Gurevich. The Classical Decision Problem. Springer, 1997.","DOI":"10.1007\/978-3-642-59207-2"},{"key":"4_CR3","unstructured":"J. R. B\u00fcchi. On a decision method in restriced second-order arithmetic. In E. Nagel et al., editor, Proc. International Congress on Logic, Methodology and Philosophy of Science, pp. 1\u201311, Stanford, CA, 1960. Stanford University Press."},{"key":"4_CR4","doi-asserted-by":"publisher","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":"4_CR5","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B. Courcelle","year":"1990","unstructured":"B. Courcelle. The monadic second-order logic of graphs I: recognizable sets of finite graphs. Information and Computation, 85:12\u201375, 1990.","journal-title":"Information and Computation"},{"key":"4_CR6","doi-asserted-by":"crossref","unstructured":"H.-D. Ebbinghaus and J. Flum. Finite Model Theory. Springer, 1995.","DOI":"10.1007\/3-540-28788-4"},{"key":"4_CR7","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/0168-0072(95)00033-X","volume":"78","author":"T. Eiter","year":"1996","unstructured":"T. Eiter, G. Gottlob, and Y. Gurevich. Normal forms for second-order logic over finite structures, and classification of NP optimization problems. Annals of Pure and Applied Logic, 78:111\u2013125, 1996.","journal-title":"Annals of Pure and Applied Logic"},{"issue":"1","key":"4_CR8","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1145\/331605.331609","volume":"47","author":"T. Eiter","year":"2000","unstructured":"T. Eiter, G. Gottlob, and Y. Gurevich. Existential second-order logic over strings. Journal of the ACM, 47(1):77\u2013131, 2000.","journal-title":"Journal of the ACM"},{"key":"4_CR9","unstructured":"R. Fagin. Generalized first-order spectra and polynomial-time recognizable sets. In R. M. Karp, editor, Complexity of Computation, pp. 43\u201374. AMS, 1974."},{"key":"4_CR10","doi-asserted-by":"crossref","unstructured":"G. Gottlob, P. Kolaitis, and T. Schwentick. Existential second-order logic over graphs: charting the tractability frontier. In Proc. 41st Annual Symposium on Foundations of Computer Science (FOCS 2000), pp. 664\u2013674. IEEE Computer Society Press, 2000.","DOI":"10.1109\/SFCS.2000.892334"},{"key":"4_CR11","doi-asserted-by":"crossref","unstructured":"E. Gr\u00e4del and E. Rosen. Two-variable descriptions of regularity. In Proc. 14th Annual Symposium on Logic in Computer Science (LICS-99), pp. 14\u201323. IEEE CS Press, 1999.","DOI":"10.1109\/LICS.1999.782580"},{"key":"4_CR12","doi-asserted-by":"crossref","unstructured":"N. Immerman. Descriptive Complexity. Springer, 1997.","DOI":"10.1090\/dimacs\/031"},{"issue":"1","key":"4_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/78935.78936","volume":"37","author":"P. Kolaitis","year":"1990","unstructured":"P. Kolaitis and C. Papadimitriou. Some computational aspects of circumscription. Journal of the ACM, 37(1):1\u201315, 1990.","journal-title":"Journal of the ACM"},{"key":"4_CR14","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/0022-0000(89)90019-6","volume":"39","author":"D. Leivant","year":"1989","unstructured":"D. Leivant. Descriptive characterizations of computational complexity. Journal of Computer and System Sciences, 39:51\u201383, 1989.","journal-title":"Journal of Computer and System Sciences"},{"key":"4_CR15","first-page":"145","volume":"54","author":"J.-E. Pin","year":"1994","unstructured":"J.-E. Pin. Logic on words. Bulletin of the EATCS, 54:145\u2013165, 1994.","journal-title":"Bulletin of the EATCS"},{"key":"4_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","volume":"3","author":"L. J. Stockmeyer","year":"1977","unstructured":"L. J. Stockmeyer. The polynomial-time hierarchy. Theoretical Comp. Sc., 3:1\u201322, 1977.","journal-title":"Theoretical Comp. Sc."},{"key":"4_CR17","doi-asserted-by":"crossref","unstructured":"H. Straubing. Finite Automata, Formal Logic, and Circuit Complexity. Birkh\u00e4user, 1994.","DOI":"10.1007\/978-1-4612-0289-9"},{"key":"4_CR18","doi-asserted-by":"crossref","unstructured":"W. Thomas. Automata on infinite objects. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, volume B, chapter 4. Elsevier Science Pub., 1990.","DOI":"10.1016\/B978-0-444-88074-1.50009-3"},{"issue":"1","key":"4_CR19","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1002\/jgt.3190120111","volume":"12","author":"C. Thomassen","year":"1988","unstructured":"C. Thomassen. On the presence of disjoint subgraphs of a specified type. Journal of Graph Theory, 12:1, 101\u2013111, 1988.","journal-title":"Journal of Graph Theory"},{"key":"4_CR20","first-page":"326","volume":"140","author":"B. Trakhtenbrot","year":"1961","unstructured":"B. Trakhtenbrot. Finite automata and the logic of monadic predicates. Dokl. Akad. Nauk SSSR, 140:326\u2013329, 1961.","journal-title":"Dokl. Akad. Nauk SSSR"}],"container-title":["Lecture Notes in Computer Science","Developments in Language Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-46011-X_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,17]],"date-time":"2025-01-17T09:01:45Z","timestamp":1737104505000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-46011-X_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540434535","9783540460114"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/3-540-46011-x_4","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]}}}