{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,27]],"date-time":"2025-10-27T20:31:38Z","timestamp":1761597098244},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540705826"},{"type":"electronic","value":"9783540705833"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-70583-3_20","type":"book-chapter","created":{"date-parts":[[2008,8,12]],"date-time":"2008-08-12T12:07:43Z","timestamp":1218542863000},"page":"233-245","source":"Crossref","is-referenced-by-count":7,"title":["Tree Languages Defined in First-Order Logic with One Quantifier Alternation"],"prefix":"10.1007","author":[{"given":"Miko\u0142aj","family":"Boja\u0144czyk","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Luc","family":"Segoufin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"1","key":"20_CR1","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/0304-3975(91)90268-7","volume":"91","author":"M. Arfi","year":"1991","unstructured":"Arfi, M.: Op\u00e9rations polynomiales et hi\u00e9rarchies de concat\u00e9nation. Theor. Comput. Sci.\u00a091(1), 71\u201384 (1991)","journal-title":"Theor. Comput. Sci."},{"doi-asserted-by":"crossref","unstructured":"Benedikt, M., Segoufin, L.: Regular tree languages definable in FO and in FO+mod (preliminary version in STACS 2005) (manuscript, 2008)","key":"20_CR2","DOI":"10.1007\/978-3-540-31856-9_27"},{"key":"20_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1007\/978-3-540-74915-8_14","volume-title":"Computer Science Logic","author":"M. Boja\u0144czyk","year":"2007","unstructured":"Boja\u0144czyk, M.: Forest expressions. In: Duparc, J., Henzinger, T.A. (eds.) CSL 2007. LNCS, vol.\u00a04646, pp. 146\u2013160. Springer, Heidelberg (2007)"},{"doi-asserted-by":"crossref","unstructured":"Boja\u0144czyk, M.: Two-way unary temporal logic over trees. In: Logic in Computer Science, pp. 121\u2013130 (2007)","key":"20_CR4","DOI":"10.1109\/LICS.2007.51"},{"issue":"2-3","key":"20_CR5","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/j.tcs.2006.01.018","volume":"358","author":"M. Boja\u0144czyk","year":"2006","unstructured":"Boja\u0144czyk, M., Walukiewicz, I.: Characterizing EF and EX tree logics. Theoretical Computer Science\u00a0358(2-3), 255\u2013273 (2006)","journal-title":"Theoretical Computer Science"},{"unstructured":"Boja\u0144czyk, M., Walukiewicz, I.: Forest algebras. In: Automata and Logic: History and Perspectives, pp. 107\u2013132. Amsterdam University Press (2007)","key":"20_CR6"},{"issue":"2","key":"20_CR7","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1006\/inco.2001.2953","volume":"179","author":"K. Etessami","year":"2002","unstructured":"Etessami, K., Vardi, M.Y., Wilke, T.: First-order logic with two variables and unary temporal logic. Inf. Comput.\u00a0179(2), 279\u2013295 (2002)","journal-title":"Inf. Comput."},{"doi-asserted-by":"crossref","unstructured":"Straubing, H., Boja\u0144czyk, M., Segoufin, L.: Piecewise testable tree languages. In: Logic in Computer Science (2008)","key":"20_CR8","DOI":"10.1109\/LICS.2008.46"},{"key":"20_CR9","volume-title":"Counter-Free Automata","author":"R. McNaughton","year":"1971","unstructured":"McNaughton, R., Papert, S.: Counter-Free Automata. MIT Press, Cambridge (1971)"},{"key":"20_CR10","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1007\/BF02127803","volume":"16","author":"J.-\u00c9. Pin","year":"1996","unstructured":"Pin, J.-\u00c9.: Logic, semigroups and automata on words. Annals of Mathematics and Artificial Intelligence\u00a016, 343\u2013384 (1996)","journal-title":"Annals of Mathematics and Artificial Intelligence"},{"key":"20_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF02679450","volume":"30","author":"J.-\u00c9. Pin","year":"1997","unstructured":"Pin, J.-\u00c9., Weil, P.: Polynomial closure and unambiguous product. Theory Comput.\u00a0Systems\u00a030, 1\u201330 (1997)","journal-title":"Theory Comput.\u00a0Systems"},{"key":"20_CR12","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"},{"doi-asserted-by":"crossref","unstructured":"Schwentick, T., Th\u00e9rien, D., Vollmer, H.: Partially-ordered two-way automata: A new characterization of DA. In: Devel. in Language Theory, pp. 239\u2013250 (2001)","key":"20_CR13","DOI":"10.1007\/3-540-46011-X_20"},{"doi-asserted-by":"crossref","unstructured":"Simon, I.: Piecewise testable events. In: Automata Theory and Formal Languages, pp. 214\u2013222 (1975)","key":"20_CR14","DOI":"10.1007\/3-540-07407-4_23"},{"doi-asserted-by":"crossref","unstructured":"Th\u00e9rien, D., Wilke, T.: Over words, two variables are as powerful as one quantifier alternation. In: STOC, pp. 256\u2013263 (1998)","key":"20_CR15","DOI":"10.1145\/276698.276749"},{"key":"20_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1007\/3-540-49116-3_3","volume-title":"STACS 99","author":"T. Wilke","year":"1999","unstructured":"Wilke, T.: Classifying discrete temporal properties. In: Meinel, C., Tison, S. (eds.) STACS 1999. LNCS, vol.\u00a01563, pp. 32\u201346. Springer, Heidelberg (1999)"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-70583-3_20.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T00:07:57Z","timestamp":1605744477000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-70583-3_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540705826","9783540705833"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-70583-3_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}