{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T07:04:33Z","timestamp":1760079873420,"version":"3.41.0"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2015,4,8]],"date-time":"2015-04-08T00:00:00Z","timestamp":1428451200000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2016,5]]},"DOI":"10.1007\/s00224-014-9595-z","type":"journal-article","created":{"date-parts":[[2015,4,7]],"date-time":"2015-04-07T06:19:38Z","timestamp":1428387578000},"page":"614-663","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Regular Languages of Thin Trees"],"prefix":"10.1007","volume":"58","author":[{"given":"Tomasz","family":"Idziaszek","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Micha\u0142","family":"Skrzypczak","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Miko\u0142aj","family":"Boja\u0144czyk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,4,8]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"Boja\u0144czyk, M., Idziaszek, T.: Algebra for infinite forests with an application to the temporal logic EF. In: CONCUR, pp. 131\u2013145 (2009)","key":"9595_CR1","DOI":"10.1007\/978-3-642-04081-8_10"},{"issue":"29","key":"9595_CR2","doi-asserted-by":"crossref","first-page":"3463","DOI":"10.1016\/j.tcs.2011.02.037","volume":"412","author":"A Blumensath","year":"2011","unstructured":"Blumensath, A.: Recognisability for algebras of infinite trees. Theor. Comput. Sci. 412(29), 3463\u20133486 (2011)","journal-title":"Theor. Comput. Sci."},{"doi-asserted-by":"crossref","unstructured":"Boja\u0144czyk, M.: Effective characterizations of tree logics. In: PODS, pp. 53\u201366 (2008)","key":"9595_CR3","DOI":"10.1145\/1376916.1376925"},{"doi-asserted-by":"crossref","unstructured":"Boja\u0144czyk, M., Place, T.: Regular languages of infinite trees that are Boolean combinations of open sets. In: ICALP, pp. 104\u2013115 (2012)","key":"9595_CR4","DOI":"10.1007\/978-3-642-31585-5_13"},{"doi-asserted-by":"crossref","unstructured":"Burris, S., Sankappanavar, H.P.: A Course in Universal Algebra. Number 78 in Graduate Texts in Mathematics. Springer-Verlag (1981)","key":"9595_CR5","DOI":"10.1007\/978-1-4613-8130-3"},{"key":"9595_CR6","first-page":"81","volume-title":"Computer Science Logic 2013 (CSL 2013) volume 23 of Leibniz International Proceedings in Informatics (LIPIcs)","author":"M Bilkowski","year":"2013","unstructured":"Bilkowski, M., Skrzypczak, M.: Unambiguity and uniformization problems on infinite trees. In: Della Rocca, S.R. (ed.) Computer Science Logic 2013 (CSL 2013) volume 23 of Leibniz International Proceedings in Informatics (LIPIcs), pp 81\u2013100. Dagstuhl, Germany (2013). Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik"},{"unstructured":"B\u00fcchi, J.R.: On a decision method in restricted second-order arithmetic. In: Proceedings 1960 International Congress for Logic, Methodology and Philosophy of Science, pp. 1\u201311 (1962)","key":"9595_CR7"},{"unstructured":"Boja\u0144czyk, M., Walukiewicz, I.: Forest algebras. In: Logic and Automata, pp. 107\u2013132 (2008)","key":"9595_CR8"},{"issue":"2\u20133","key":"9595_CR9","doi-asserted-by":"crossref","first-page":"287","DOI":"10.3233\/FI-2009-151","volume":"95","author":"O Finkel","year":"2009","unstructured":"Finkel, O., Simonnet, P.: On recognizable tree languages beyond the Borel hierarchy. Fundam. Inform. 95(2\u20133), 287\u2013303 (2009)","journal-title":"Fundam. Inform."},{"unstructured":"Hummel, S., Michalewski, H., Niwi\u0144ski, D.: On the Borel inseparability of game tree languages. In: STACS, pp. 565\u2013575 (2009)","key":"9595_CR10"},{"unstructured":"Idziaszek, T.: Algebraic Methods in the Theory of Infinite Trees. PhD thesis, University of Warsaw, 2012. unpublished","key":"9595_CR11"},{"key":"9595_CR12","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-4190-4","volume-title":"Classical Descriptive Set Theory","author":"A Kechris","year":"1995","unstructured":"Kechris, A.: Classical Descriptive Set Theory. Springer-Verlag, New York (1995)"},{"doi-asserted-by":"crossref","unstructured":"Kufleitner, M., Lauser, A.: Languages of dot-depth one over infinite words. In: LICS, pp. 23\u201332 (2011)","key":"9595_CR13","DOI":"10.1109\/LICS.2011.24"},{"issue":"1","key":"9595_CR14","doi-asserted-by":"crossref","first-page":"103","DOI":"10.2307\/2586591","volume":"63","author":"S Lifsches","year":"1998","unstructured":"Lifsches, S., Shelah, S.: Uniformization and skolem functions in the class of trees. J. Symb. Log. 63(1), 103\u2013127 (1998)","journal-title":"J. Symb. Log."},{"doi-asserted-by":"crossref","unstructured":"Murlak, F.: The Wadge hierarchy of deterministic tree languages. Logic. Methods Comput. Sci. 4(4) (2008)","key":"9595_CR15","DOI":"10.2168\/LMCS-4(4:15)2008"},{"issue":"303","key":"9595_CR16","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1016\/S0304-3975(02)00452-8","volume":"1","author":"D Niwi\u0144ski","year":"2003","unstructured":"Niwi\u0144ski, D., Walukiewicz, I.: A gap property of deterministic tree languages. Theor. Comput. Sci. 1(303), 215\u2013231 (2003)","journal-title":"Theor. Comput. Sci."},{"unstructured":"Perrin, D., Pin, J.-\u00c9.: Infinite Words: Automata, Semigroups, Logic and Games. Elsevier (2004)","key":"9595_CR17"},{"key":"9595_CR18","first-page":"1","volume":"141","author":"MO Rabin","year":"1969","unstructured":"Rabin, M.O.: Decidability of second-order theories and automata on infinite trees. Trans. American Math. Soc. 141, 1\u201335 (1969)","journal-title":"Trans. American Math. Soc."},{"doi-asserted-by":"crossref","unstructured":"Rabinovich, A., Rubin, S.: Interpretations in trees with countably many branches. In: LICS, pp. 551\u2013560. IEEE (2012)","key":"9595_CR19","DOI":"10.1109\/LICS.2012.65"},{"issue":"2","key":"9595_CR20","doi-asserted-by":"crossref","first-page":"190","DOI":"10.1016\/S0019-9958(65)90108-7","volume":"8","author":"MP Sch\u00fctzenberger","year":"1965","unstructured":"Sch\u00fctzenberger, M.P.: On finite monoids having only trivial subgroups. Inf. Control. 8(2), 190\u2013194 (1965)","journal-title":"Inf. Control."},{"doi-asserted-by":"crossref","unstructured":"Simon, I.: Piecewise testable events. In: Automata Theory and Formal Languages, pp. 214\u2013222 (1975)","key":"9595_CR21","DOI":"10.1007\/3-540-07407-4_23"},{"issue":"2","key":"9595_CR22","doi-asserted-by":"crossref","first-page":"413","DOI":"10.1016\/0304-3975(93)90030-W","volume":"112","author":"J Skurczy\u0144ski","year":"1993","unstructured":"Skurczy\u0144ski, J.: The Borel hierarchy is infinite in the class of regular sets of trees. Theor. Comput. Sci. 112(2), 413\u2013418 (1993)","journal-title":"Theor. Comput. Sci."},{"unstructured":"Thomas, W.: Relationen endlicher valenz \u00fcber der ordnung der nat\u00fcrlichen zahlen. Habilitationsschrift, Universitat Freiburg, apr. 1980","key":"9595_CR23"},{"doi-asserted-by":"crossref","unstructured":"Th\u00e9rien, D., Wilke, T.: Over words, two variables are as powerful as one quantifier alternation. In: STOC, pp. 234\u2013\u2013240 (1998)","key":"9595_CR24","DOI":"10.1145\/276698.276749"},{"key":"9595_CR25","doi-asserted-by":"crossref","first-page":"447","DOI":"10.1142\/S0218196793000287","volume":"3","author":"T Wilke","year":"1993","unstructured":"Wilke, T.: An algebraic theory for regular languages of finite and infinite words. Int. J. Alg. Comput. 3, 447\u2013489 (1993)","journal-title":"Int. J. Alg. Comput."},{"doi-asserted-by":"crossref","unstructured":"Wilke, T.: Classifying discrete temporal properties. Habilitationsschrift, Universitat Kiel, apr. 1998","key":"9595_CR26","DOI":"10.1007\/3-540-49116-3_3"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-014-9595-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-014-9595-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-014-9595-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,21]],"date-time":"2025-05-21T23:26:27Z","timestamp":1747869987000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-014-9595-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,4,8]]},"references-count":26,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,5]]}},"alternative-id":["9595"],"URL":"https:\/\/doi.org\/10.1007\/s00224-014-9595-z","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2015,4,8]]}}}