{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,27]],"date-time":"2025-10-27T20:33:09Z","timestamp":1761597189885},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540249986"},{"type":"electronic","value":"9783540318569"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/978-3-540-31856-9_27","type":"book-chapter","created":{"date-parts":[[2010,3,2]],"date-time":"2010-03-02T18:06:19Z","timestamp":1267553179000},"page":"327-339","source":"Crossref","is-referenced-by-count":19,"title":["Regular Tree Languages Definable in FO"],"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":"27_CR1","doi-asserted-by":"crossref","unstructured":"Beauquier, D., Pin, J.-E.: Factors of words. In: Proc. of Intl. Coll. on Automata, Languages and Programming, pp. 63\u201379 (1989)","DOI":"10.1007\/BFb0035752"},{"key":"27_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1007\/978-3-540-28644-8_9","volume-title":"CONCUR 2004 - Concurrency Theory","author":"M. Boja\u0144czyk","year":"2004","unstructured":"Boja\u0144czyk, M., Walukiewicz, I.: Characterizing EF and EX tree logics. In: Gardner, P., Yoshida, N. (eds.) CONCUR 2004. LNCS, vol.\u00a03170, pp. 131\u2013145. Springer, Heidelberg (2004)"},{"key":"27_CR3","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."},{"issue":"1","key":"27_CR4","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/0304-3975(91)90075-D","volume":"88","author":"S. Cho","year":"1991","unstructured":"Cho, S., Huynh, D.T.: Finite-automaton aperiodicity is PSPACE-complete. Theoretical Computer Science\u00a088(1), 99\u2013116 (1991)","journal-title":"Theoretical Computer Science"},{"issue":"1993","key":"27_CR5","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1016\/0022-0000(93)90005-H","volume":"46","author":"J. Cohen","year":"1993","unstructured":"Cohen, J., Perrin, D., Pin, J.-E.: On the expressive power of temporal logic for finite words. Journal of Computer and Science Systems\u00a046(1993), 271\u2013294 (1993)","journal-title":"Journal of Computer and Science Systems"},{"key":"27_CR6","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":"27_CR7","doi-asserted-by":"crossref","unstructured":"\u00c9sik, Z., Weil, P.: On logically defined recognizable tree languages. In: FSTTCS, pp. 195\u2013207 (2003)","DOI":"10.1007\/978-3-540-24597-1_17"},{"key":"27_CR8","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1051\/ita\/1991250201251","volume":"25","author":"U. Heuter","year":"1991","unstructured":"Heuter, U.: First-order properties of trees, star-free expressions, and aperiodicity. Informatique Th\u00e9orique et Applications\u00a025, 125\u2013146 (1991)","journal-title":"Informatique Th\u00e9orique et Applications"},{"key":"27_CR9","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)"},{"key":"27_CR10","volume-title":"Counter-free Automata","author":"R. McNaughton","year":"1971","unstructured":"McNaughton, R., Papert, S.: Counter-free Automata. MIT Press, Cambridge (1971)"},{"key":"27_CR11","doi-asserted-by":"crossref","unstructured":"Pin, J.-E.: The expressive power of existential first order sentences of B\u00fcchi\u2019s sequential calculus. In: Proc. of Intl. Coll. on Automata, Languages and Programming, pp. 300\u2013311 (1996)","DOI":"10.1007\/3-540-61440-0_137"},{"key":"27_CR12","series-title":"Lecture Notes in Computer Science","first-page":"125","volume-title":"TAPSOFT \u201995: Theory and Practice of Software Development","author":"A. Potthoff","year":"1995","unstructured":"Potthoff, A.: First-order logic on finite trees. In: Mosses, P.D., Schwartzbach, M.I., Nielsen, M. (eds.) CAAP 1995, FASE 1995, and TAPSOFT 1995. LNCS, vol.\u00a0915, pp. 125\u2013139. Springer, Heidelberg (1995)"},{"key":"27_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"396","DOI":"10.1007\/3-540-57163-9_34","volume-title":"Fundamentals of Computation Theory","author":"A. Potthoff","year":"1993","unstructured":"Potthoff, A., Thomas, W.: Regular tree languages without unary symbols are star-free. In: \u00c9sik, Z. (ed.) FCT 1993. LNCS, vol.\u00a0710, pp. 396\u2013405. Springer, Heidelberg (1993)"},{"key":"27_CR14","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1016\/S0019-9958(65)90108-7","volume":"8","author":"M.P. Sch\u00fctzenberger","year":"1965","unstructured":"Sch\u00fctzenberger, M.P.: On finite monoids having only trivial subgroups. Information and Control\u00a08, 190\u2013194 (1965)","journal-title":"Information and Control"},{"key":"27_CR15","doi-asserted-by":"crossref","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":"27_CR16","volume-title":"Handbook of Formal Languages, ch. 7","author":"W. Thomas","year":"1997","unstructured":"Thomas, W.: Handbook of Formal Languages, ch. 7, vol.\u00a03. Springer, Heidelberg (1997)"},{"key":"27_CR17","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 with an application to a decision problem of second order logic. Math. Syst. Theory\u00a02, 57\u201382 (1968)","journal-title":"Math. Syst. Theory"},{"key":"27_CR18","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/0022-4049(85)90071-4","volume":"36","author":"D. Th\u00e9rien","year":"1985","unstructured":"Th\u00e9rien, D., Weiss, A.: Graph congruences and wreath products. J. Pure and Applied Algebra\u00a036, 205\u2013215 (1985)","journal-title":"J. Pure and Applied Algebra"},{"issue":"1","key":"27_CR19","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/0304-3975(95)00131-X","volume":"154","author":"T. Wilke","year":"1996","unstructured":"Wilke, T.: An algebraic characterization of frontier testable tree languages. Theoretical Computer Science\u00a0154(1), 85\u2013106 (1996)","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","STACS 2005"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-31856-9_27.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T04:29:47Z","timestamp":1605760187000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-31856-9_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540249986","9783540318569"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-31856-9_27","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}