{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T20:05:34Z","timestamp":1725566734893},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540282310"},{"type":"electronic","value":"9783540318972"}],"license":[{"start":{"date-parts":[[2005,1,1]],"date-time":"2005-01-01T00:00:00Z","timestamp":1104537600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11538363_20","type":"book-chapter","created":{"date-parts":[[2005,9,27]],"date-time":"2005-09-27T09:35:33Z","timestamp":1127813733000},"page":"276-291","source":"Crossref","is-referenced-by-count":4,"title":["Towards a Characterization of Order-Invariant Queries over Tame Structures"],"prefix":"10.1007","author":[{"given":"Michael","family":"Benedikt","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Luc","family":"Segoufin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"20_CR1","volume-title":"Foundations of Databases","author":"S. Abiteboul","year":"1995","unstructured":"Abiteboul, S., Hull, R., Vianu, V.: Foundations of Databases. Addison-Wesley, Reading (1995)"},{"key":"20_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0035752","volume-title":"Automata, Languages and Programming","author":"D. Beauquier","year":"1989","unstructured":"Beauquier, D., Pin, J.-E.: Factors of words. In: Ronchi Della Rocca, S., Ausiello, G., Dezani-Ciancaglini, M. (eds.) ICALP 1989. LNCS, vol.\u00a0372, Springer, Heidelberg (1989)"},{"key":"20_CR3","doi-asserted-by":"crossref","unstructured":"Benedikt, M., Segoufin, L.: Regular Tree Languages Definable in FO. Available from the authors. An abstract has appeared in STACS (2005)","DOI":"10.1007\/978-3-540-31856-9_27"},{"key":"20_CR4","unstructured":"Br\u00fcggemann-Klein, A., Murata, M., Wood, D.: Regular Tree and Regular Hedge Languages over Unranked Alphabets (2001), Available at \n                    \n                      ftp:\/\/ftp11.informatik.tu-muenchen.de\/pub\/misc\/caterpillars\/"},{"key":"20_CR5","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1002\/malq.19600060105","volume":"6","author":"J. B\u00fcchi","year":"1960","unstructured":"B\u00fcchi, J.: Weak second-order logic and finite automata. S. Math. Logik Grunlagen Math.\u00a06, 66\u201392 (1960)","journal-title":"S. Math. Logik Grunlagen Math."},{"key":"20_CR6","volume-title":"Model Theory","author":"C.C. Chang","year":"1990","unstructured":"Chang, C.C., Keisler, H.J.: Model Theory, North-Holland. Elsevier, Amsterdam (1990)"},{"key":"20_CR7","doi-asserted-by":"crossref","unstructured":"Courcelle, B.: The Monadic Second Order Logic of Graphs I: Recognizable Sets of Finite Graphs Information and Computation (1990)","DOI":"10.1016\/0890-5401(90)90043-H"},{"key":"20_CR8","doi-asserted-by":"crossref","unstructured":"Courcelle, B.: The Monadic Second Order Logic of Graphs V: On Closing the Gap Between Definability and Recognizability Theor. Comput. Sci. (1991)","DOI":"10.1016\/0304-3975(91)90387-H"},{"key":"20_CR9","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/0304-3975(95)00083-6","volume":"160","author":"B. Courcelle","year":"1996","unstructured":"Courcelle, B.: The Monadic Second Order Logic of Graphs X: Linear Orders. Theoretical Computer Science\u00a0160, 87\u2013143 (1996)","journal-title":"Theoretical Computer Science"},{"key":"20_CR10","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":"20_CR11","volume-title":"Finite Model Theory","author":"H.-D. Ebbinghaus","year":"1995","unstructured":"Ebbinghaus, H.-D., Flum, J.: Finite Model Theory. Springer, Heidelberg (1995)"},{"key":"20_CR12","unstructured":"Niemisto, H.: On Locality and Uniform Reduction. To appear in LICS (2005)"},{"key":"20_CR13","unstructured":"Open Problems in Finite Model Theory, \n                    \n                      http:\/\/www-mgi.informatik.rwth-aachen.de\/FMT"},{"key":"20_CR14","doi-asserted-by":"crossref","unstructured":"Grohe, M., Schwentick, T.: Locality of Order-Invariant First-Order Queries. ACM TOCL (2000)","DOI":"10.1145\/343369.343386"},{"key":"20_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0028596","volume-title":"STACS 98","author":"D. Lapoire","year":"1998","unstructured":"Lapoire, D.: Recognizability Equals Monadic Second-Order Definability for Sets of Graphs of Bounded Tree-Width. In: Meinel, C., Morvan, M. (eds.) STACS 1998. LNCS, vol.\u00a01373, Springer, Heidelberg (1998)"},{"key":"20_CR16","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-07003-1","volume-title":"Elements of finite model theory","author":"L. Libkin","year":"2004","unstructured":"Libkin, L.: Elements of finite model theory. Springer, Heidelberg (2004)"},{"issue":"4","key":"20_CR17","doi-asserted-by":"publisher","first-page":"1749","DOI":"10.2307\/2695073","volume":"65","author":"M. Otto","year":"2000","unstructured":"Otto, M.: Epsilon-logic is more expressive then first-order logic on finite structures. Journal of Symbolic Logic\u00a065(4), 1749\u20131757 (2000)","journal-title":"Journal of Symbolic Logic"},{"key":"20_CR18","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/0095-8956(84)90013-3","volume":"36","author":"N. Robertson","year":"1984","unstructured":"Robertson, N., Seymour, P.: Graph Minors III: planar tree-width. J. Combin. Theory Ser. B\u00a036, 49\u201364 (1984)","journal-title":"J. Combin. Theory Ser. B"},{"key":"20_CR19","unstructured":"Rossman, B.: Successor-invariance in the finite. In: LICS (2003)"},{"key":"20_CR20","doi-asserted-by":"crossref","unstructured":"Straubing, H.: Finite Automata, Formal Logic, and Circuit Complexity. Birkh\u00e4user (1994)","DOI":"10.1007\/978-1-4612-0289-9"},{"key":"20_CR21","unstructured":"Comon, H., et al.: Tree Automata: Techniques and Applications, Available at \n                    \n                      http:\/\/www.grappa.univ-lille3.fr\/tata"},{"key":"20_CR22","volume-title":"Handbook of formal languages","author":"W. Thomas","year":"1997","unstructured":"Thomas, W.: Handbook of formal languages, vol.\u00a03, ch. 7. Springer, Heidelberg (1997)"},{"key":"20_CR23","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1007\/BF01691346","volume":"2","author":"J.W. Thatcher","year":"1968","unstructured":"Thatcher, J.W., Wright, J.B.: Generalized finite automata woth an application to a decision problem of second order logic. Math. Syst. Theory\u00a02, 57\u201382 (1968)","journal-title":"Math. Syst. Theory"}],"container-title":["Lecture Notes in Computer Science","Computer Science Logic"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11538363_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T18:48:13Z","timestamp":1558291693000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11538363_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540282310","9783540318972"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/11538363_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}