{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T15:23:39Z","timestamp":1742916219375,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":52,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642150241"},{"type":"electronic","value":"9783642150258"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-15025-8_13","type":"book-chapter","created":{"date-parts":[[2010,8,16]],"date-time":"2010-08-16T06:52:44Z","timestamp":1281941564000},"page":"227-250","source":"Crossref","is-referenced-by-count":2,"title":["The Model Checking Problem for Prefix Classes of Second-Order Logic: A Survey"],"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","reference":[{"key":"13_CR1","volume-title":"Data on the Web: From Relations to Semistructured Data and XML","author":"S. Abiteboul","year":"1999","unstructured":"Abiteboul, S., Buneman, P., Suciu, D.: Data on the Web: From Relations to Semistructured Data and XML. Morgan Kaufmann, San Francisco (1999)"},{"key":"13_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"338","DOI":"10.1007\/978-3-540-24749-4_30","volume-title":"STACS 2004","author":"R. Barbanchon","year":"2004","unstructured":"Barbanchon, R., Grandjean, E.: The minimal logically-defined NP-complete problem. In: Diekert, V., Habib, M. (eds.) STACS 2004. LNCS, vol.\u00a02996, pp. 338\u2013349. Springer, Heidelberg (2004)"},{"key":"13_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1007\/3-540-60045-0_38","volume-title":"Computer Aided Verification","author":"D. Basin","year":"1995","unstructured":"Basin, D., Klarlund, N.: Hardware verification using monadic second-order logic. In: Wolper, P. (ed.) CAV 1995. LNCS, vol.\u00a0939, pp. 31\u201341. Springer, Heidelberg (1995)"},{"key":"13_CR4","unstructured":"Baumgartner, R., Flesca, S., Gottlob, G.: Visual web information extraction with Lixto. In: VLDB, pp. 119\u2013128 (2001)"},{"key":"13_CR5","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"H.L. Bodlaender","year":"1996","unstructured":"Bodlaender, H.L.: A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth. SIAM Journal on Computing\u00a025, 1305\u20131317 (1996)","journal-title":"SIAM Journal on Computing"},{"key":"13_CR6","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-59207-2","volume-title":"The Classical Decision Problem","author":"E. B\u00f6rger","year":"1997","unstructured":"B\u00f6rger, E., Gr\u00e4del, E., Gurevich, Y.: The Classical Decision Problem. Springer, Heidelberg (1997)"},{"key":"13_CR7","unstructured":"Br\u00fcggemann-Klein, A., Murata, M., Wood, D.: Regular tree and regular hedge languages over non-ranked alphabets: Version 1, April 3, 2001. Technical Report HKUST-TCSC-2001-05, Hong Kong University of Science and Technology, Hong Kong SAR, China (2001)"},{"key":"13_CR8","first-page":"1","volume-title":"Proc. International Congress on Logic, Methodology and Philosophy of Science","author":"J.R. B\u00fcchi","year":"1960","unstructured":"B\u00fcchi, J.R.: On a Decision Method in Restriced Second-Order Arithmetic. In: Nagel, E., et al. (eds.) Proc. International Congress on Logic, Methodology and Philosophy of Science, pp. 1\u201311. Stanford University Press, Stanford (1960)"},{"key":"13_CR9","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1002\/malq.19600060105","volume":"6","author":"J.R. B\u00fcchi","year":"1960","unstructured":"B\u00fcchi, J.R.: Weak second-order arithmetic and finite automata. Zeitschrift f\u00fcr mathematische Logik und Grundlagen der Mathematik\u00a06, 66\u201392 (1960)","journal-title":"Zeitschrift f\u00fcr mathematische Logik und Grundlagen der Mathematik"},{"key":"13_CR10","unstructured":"Comon, H., Dauchet, M., Gilleron, R., Jacquemard, F., Lugiez, D., L\u00f6ding, C., Tison, S., Tommasi, M.: Tree Automata Techniques and Applications (Web book) (2008), http:\/\/tata.gforge.inria.fr\/ (viewed September 25, 2009)"},{"key":"13_CR11","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B. Courcelle","year":"1990","unstructured":"Courcelle, B.: The Monadic Second-Order Logic of Graphs I: Recognizable Sets of Finite Graphs. Information and Computation\u00a085, 12\u201375 (1990)","journal-title":"Information and Computation"},{"key":"13_CR12","doi-asserted-by":"publisher","first-page":"406","DOI":"10.1016\/S0022-0000(70)80041-1","volume":"4","author":"J. Doner","year":"1970","unstructured":"Doner, J.: Tree acceptors and some of their applications. Journal of Computer and System Sciences\u00a04, 406\u2013451 (1970)","journal-title":"Journal of Computer and System Sciences"},{"key":"13_CR13","volume-title":"Perspectives in Mathematical Logic","author":"H.D. Ebbinghaus","year":"1995","unstructured":"Ebbinghaus, H.D., Flum, J.: Finite Model Theory. In: Perspectives in Mathematical Logic. Springer, Heidelberg (1995)"},{"key":"13_CR14","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/0168-0072(95)00033-X","volume":"78","author":"T. Eiter","year":"1996","unstructured":"Eiter, T., Gottlob, G., Gurevich, Y.: Normal Forms for Second-Order Logic over Finite Structures, and Classification of NP Optimization Problems. Annals of Pure and Applied Logic\u00a078, 111\u2013125 (1996)","journal-title":"Annals of Pure and Applied Logic"},{"key":"13_CR15","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1145\/331605.331609","volume":"47","author":"T. Eiter","year":"2000","unstructured":"Eiter, T., Gottlob, G., Gurevich, Y.: Existential Second-Order Logic over Strings. Journal of the ACM\u00a047, 77\u2013131 (2000)","journal-title":"Journal of the ACM"},{"key":"13_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/3-540-46011-X_4","volume-title":"Developments in Language Theory","author":"T. Eiter","year":"2002","unstructured":"Eiter, T., Gottlob, G., Schwentick, T.: Second-Order Logic over Strings: Regular and Non-Regular Fragments. In: Kuich, W., Rozenberg, G., Salomaa, A. (eds.) DLT 2001. LNCS, vol.\u00a02295, pp. 37\u201356. Springer, Heidelberg (2002)"},{"key":"13_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"516","DOI":"10.1007\/BFb0028773","volume-title":"Computer Aided Verification","author":"J. Elgaard","year":"1998","unstructured":"Elgaard, J., Klarlund, N., M\u00f8ller, A.: MONA 1.x: New techniques for WS1S and WS2S. In: Y. Vardi, M. (ed.) CAV 1998. LNCS, vol.\u00a01427, pp. 516\u2013520. Springer, Heidelberg (1998)"},{"key":"13_CR18","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1090\/S0002-9947-1961-0139530-9","volume":"98","author":"C.C. Elgot","year":"1961","unstructured":"Elgot, C.C.: Decision problems of finite automata design and related arithmetics. Transactions of the American Mathematical Society\u00a098, 21\u201351 (1961)","journal-title":"Transactions of the American Mathematical Society"},{"key":"13_CR19","unstructured":"Fagin, R.: Generalized First-Order Spectra and Polynomial-Time Recognizable Sets. In: Karp, R.M. (ed.) Complexity of Computation, pp. 43\u201374. AMS (1974)"},{"key":"13_CR20","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1007\/978-3-540-25984-8_16","volume-title":"Automated Reasoning","author":"G. Gottlob","year":"2004","unstructured":"Gottlob, G.: Second-order logic over finite structures - report on a research programme. In: Basin, D., Rusinowitch, M. (eds.) IJCAR 2004. LNCS (LNAI), vol.\u00a03097, pp. 229\u2013243. Springer, Heidelberg (2004)"},{"key":"13_CR21","doi-asserted-by":"crossref","unstructured":"Gottlob, G., Koch, C.: Monadic queries over tree-structured data. In: LICS, pp. 189\u2013202 (2002)","DOI":"10.1109\/LICS.2002.1029828"},{"key":"13_CR22","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1145\/962446.962450","volume":"51","author":"G. Gottlob","year":"2004","unstructured":"Gottlob, G., Koch, C.: Monadic datalog and the expressive power of languages for web information extraction. Journal of the ACM\u00a051, 74\u2013113 (2004)","journal-title":"Journal of the ACM"},{"key":"13_CR23","doi-asserted-by":"crossref","unstructured":"Gottlob, G., Koch, C., Baumgartner, R., Herzog, M., Flesca, S.: The Lixto data extraction project - back and forth between theory and practice. In: PODS, pp. 1\u201312 (2004)","DOI":"10.1145\/1055558.1055560"},{"key":"13_CR24","doi-asserted-by":"publisher","first-page":"444","DOI":"10.1145\/1071610.1071614","volume":"30","author":"G. Gottlob","year":"2005","unstructured":"Gottlob, G., Koch, C., Pichler, R.: Efficient algorithms for processing XPath queries. ACM Trans. Database Syst.\u00a030, 444\u2013491 (2005)","journal-title":"ACM Trans. Database Syst."},{"key":"13_CR25","doi-asserted-by":"publisher","first-page":"664","DOI":"10.1109\/SFCS.2000.892334","volume-title":"41st Annual Symposium on Foundations of Computer Science (FOCS 2000)","author":"G. Gottlob","year":"2000","unstructured":"Gottlob, G., Kolaitis, P., Schwentick, T.: Existential second-order logic over graphs: Charting the tractability frontier. In: 41st Annual Symposium on Foundations of Computer Science (FOCS 2000), Redondo Beach, California, USA, November 12-14, pp. 664\u2013674. IEEE Computer Society Press, Los Alamitos (2000)"},{"key":"13_CR26","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1145\/972639.972646","volume":"51","author":"G. Gottlob","year":"2004","unstructured":"Gottlob, G., Kolaitis, P., Schwentick, T.: Existential second-order logic over graphs: Charting the tractability frontier. Journal of the ACM\u00a051, 312\u2013362 (2004)","journal-title":"Journal of the ACM"},{"key":"13_CR27","doi-asserted-by":"crossref","unstructured":"Gottlob, G., Pichler, R., Wei, F.: Monadic datalog over finite structures with bounded treewidth. In: PODS, pp. 165\u2013174 (2007)","DOI":"10.1145\/1265530.1265554"},{"key":"13_CR28","first-page":"14","volume-title":"Proceedings 14th Annual Symposium on Logic in Computer Science (LICS 1999)","author":"E. Gr\u00e4del","year":"1999","unstructured":"Gr\u00e4del, E., Rosen, E.: Two-Variable Descriptions of Regularity. In: Proceedings 14th Annual Symposium on Logic in Computer Science (LICS 1999), Trento, Italy, July 2-5, pp. 14\u201323. IEEE Computer Science Press, Los Alamitos (1999)"},{"key":"13_CR29","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/BF01699468","volume":"13","author":"E. Grandjean","year":"1985","unstructured":"Grandjean, E.: Universal quantifiers and time complexity of random access machines. Mathematical Systems Theory\u00a013, 171\u2013187 (1985)","journal-title":"Mathematical Systems Theory"},{"key":"13_CR30","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/j.entcs.2004.05.014","volume":"123","author":"Y. Hacha\u00efchi","year":"2005","unstructured":"Hacha\u00efchi, Y.: Fragments of monadic second-order logics over word structures. Electr. Notes Theor. Comput. Sci.\u00a0123, 111\u2013123 (2005)","journal-title":"Electr. Notes Theor. Comput. Sci."},{"key":"13_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1007\/3-540-60630-0_5","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"J. Henriksen","year":"1995","unstructured":"Henriksen, J., Jensen, J., J\u00f8rgensen, M., Klarlund, N., Paige, B., Rauhe, T., Sandholm, A.: Mona: Monadic second-order logic in practice. In: Brinksma, E., Steffen, B., Cleaveland, W.R., Larsen, K.G., Margaria, T. (eds.) TACAS 1995. LNCS, vol.\u00a01019, pp. 89\u2013110. Springer, Heidelberg (1995)"},{"key":"13_CR32","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0539-5","volume-title":"Descriptive Complexity","author":"N. Immerman","year":"1999","unstructured":"Immerman, N.: Descriptive Complexity. Springer, Heidelberg (1999)"},{"key":"13_CR33","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/78935.78936","volume":"37","author":"P. Kolaitis","year":"1990","unstructured":"Kolaitis, P., Papadimitriou, C.: Some Computational Aspects of Circumscription. Journal of the ACM\u00a037, 1\u201315 (1990)","journal-title":"Journal of the ACM"},{"key":"13_CR34","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1023\/B:GRAM.0000016586.10841.cd","volume":"6","author":"T. Langholm","year":"2003","unstructured":"Langholm, T., Bezem, M.: A descriptive characterisation of even linear languages. Grammars\u00a06, 169\u2013181 (2003)","journal-title":"Grammars"},{"key":"13_CR35","doi-asserted-by":"crossref","unstructured":"Lautemann, C., Schwentick, T., Th\u00e9rien, D.: Logics for context-free languages. In: Proc. 1994 Annual Conference of the EACSL, pp. 205\u2013216 (1995)","DOI":"10.1007\/BFb0022257"},{"key":"13_CR36","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/0022-0000(89)90019-6","volume":"39","author":"D. Leivant","year":"1989","unstructured":"Leivant, D.: Descriptive Characterizations of Computational Complexity. Journal of Computer and System Sciences\u00a039, 51\u201383 (1989)","journal-title":"Journal of Computer and System Sciences"},{"key":"13_CR37","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1007\/BF01276438","volume":"2","author":"J.F. Lynch","year":"1992","unstructured":"Lynch, J.F.: The quantifier structure of sentences that characterize nondeterministic time complexity. Computational Complexity\u00a02, 40\u201366 (1992)","journal-title":"Computational Complexity"},{"key":"13_CR38","volume-title":"Counter-Free Automata","author":"R. McNaughton","year":"1971","unstructured":"McNaughton, R., Papert, S.: Counter-Free Automata. MIT Press, Cambridge (1971)"},{"key":"13_CR39","doi-asserted-by":"publisher","first-page":"633","DOI":"10.1016\/S0304-3975(01)00301-2","volume":"275","author":"F. Neven","year":"2002","unstructured":"Neven, F., Schwentick, T.: Query automata on finite trees. Theoretical Computer Science\u00a0275, 633\u2013674 (2002)","journal-title":"Theoretical Computer Science"},{"key":"13_CR40","unstructured":"Olive, F.: A Conjunctive Logical Characterization of Nondeterministic Linear Time. In: Nielsen, M. (ed.) CSL 1997. LNCS, vol.\u00a01414. Springer, Heidelberg (1997) (to appear)"},{"key":"13_CR41","doi-asserted-by":"crossref","unstructured":"Pin, J.E.: Varieties of Formal Languages. North Oxford\/Plenum, London\/New York (1986)","DOI":"10.1007\/978-1-4613-2215-3"},{"key":"13_CR42","first-page":"145","volume":"54","author":"J.E. Pin","year":"1994","unstructured":"Pin, J.E.: Logic On Words. Bulletin of the EATCS\u00a054, 145\u2013165 (1994)","journal-title":"Bulletin of the EATCS"},{"key":"13_CR43","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1007\/BF02127803","volume":"16","author":"J.E. Pin","year":"1996","unstructured":"Pin, J.E.: Semigroups and Automata on Words. Annals of Mathematics and Artificial Intelligence\u00a016, 343\u2013384 (1996)","journal-title":"Annals of Mathematics and Artificial Intelligence"},{"key":"13_CR44","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","volume":"3","author":"L.J. Stockmeyer","year":"1977","unstructured":"Stockmeyer, L.J.: The Polynomial-Time Hierarchy. Theoretical Computer Science\u00a03, 1\u201322 (1977)","journal-title":"Theoretical Computer Science"},{"key":"13_CR45","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0289-9","volume-title":"Finite Automata, Formal Logic, and Circuit Complexity","author":"H. Straubing","year":"1994","unstructured":"Straubing, H.: Finite Automata, Formal Logic, and Circuit Complexity. Birkh\u00e4user, Basel (1994)"},{"key":"13_CR46","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1006\/inco.1995.1067","volume":"118","author":"H. Straubing","year":"1995","unstructured":"Straubing, H., Th\u00e9rien, D., Thomas, W.: Regular Languages Defined with Generalized Quantifiers. Information and Computation\u00a0118, 289\u2013301 (1995)","journal-title":"Information and Computation"},{"key":"13_CR47","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1007\/BF01691346","volume":"2","author":"J. Thatcher","year":"1968","unstructured":"Thatcher, J., Wright, J.: Generalized finite automata theory with an application to a decision problem of second-order logic. Mathematical Systems Theory\u00a02, 57\u201381 (1968)","journal-title":"Mathematical Systems Theory"},{"key":"13_CR48","doi-asserted-by":"crossref","unstructured":"Thomas, W.: Automata on Infinite Objects. In: van Leeuwen, J. (ed.) Handbook of Theoretical Computer Science, vol. B. Elsevier Science Publishers B.V, North-Holland (1990)","DOI":"10.1016\/B978-0-444-88074-1.50009-3"},{"key":"13_CR49","first-page":"389","volume-title":"Handbook of Formal Language Theory","author":"W. Thomas","year":"1996","unstructured":"Thomas, W.: Languages, Automata, and Logic. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Language Theory, vol.\u00a0III, pp. 389\u2013455. Springer, Heidelberg (1996)"},{"key":"13_CR50","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1002\/jgt.3190120111","volume":"12","author":"C. Thomassen","year":"1988","unstructured":"Thomassen, C.: On the Presence of Disjoint Subgraphs of a Specified Type. Journal of Graph Theory\u00a012, 101\u2013111 (1988)","journal-title":"Journal of Graph Theory"},{"key":"13_CR51","first-page":"326","volume":"140","author":"B. Trakhtenbrot","year":"1961","unstructured":"Trakhtenbrot, B.: Finite Automata and the Logic of Monadic Predicates. Dokl. Akad. Nauk SSSR\u00a0140, 326\u2013329 (1961)","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"13_CR52","unstructured":"World Wide Web Consortium: XPath recomendation (1999), http:\/\/www.w3c.org\/TR\/xpath\/ (viewed September 25, 2009)"}],"container-title":["Lecture Notes in Computer Science","Fields of Logic and Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-15025-8_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,24]],"date-time":"2025-02-24T15:36:17Z","timestamp":1740411377000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-15025-8_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642150241","9783642150258"],"references-count":52,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-15025-8_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}