{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T06:23:30Z","timestamp":1770963810628,"version":"3.50.1"},"reference-count":15,"publisher":"World Scientific Pub Co Pte Ltd","issue":"01","funder":[{"name":"the OP VVV MEYS","award":["CZ.02.1.01\/0.0\/0.0\/16_019\/0000765"],"award-info":[{"award-number":["CZ.02.1.01\/0.0\/0.0\/16_019\/0000765"]}]},{"name":"\u201cResearch Center for Informatics\u201d and the Czech Technical University in Prague","award":["SGS20\/208\/OHK3\/3T\/18"],"award-info":[{"award-number":["SGS20\/208\/OHK3\/3T\/18"]}]},{"DOI":"10.13039\/501100000266","name":"the Engineering and Physical Sciences Research Council","doi-asserted-by":"crossref","award":["EP\/V044621\/1"],"award-info":[{"award-number":["EP\/V044621\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001862","name":"the Swedish Research Council","doi-asserted-by":"crossref","award":["2020-03852"],"award-info":[{"award-number":["2020-03852"]}],"id":[{"id":"10.13039\/501100001862","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2026,1]]},"abstract":"<jats:p>This paper deals with properties of synchronizing terms for finite tree automata, which is a generalization of the synchronization principle of deterministic finite string automata (DFA). Such terms correspond to a connected subgraph, where a state in the root is always the same regardless of states of subtrees attached to it. We ask, what is the maximum height of the smallest synchronizing term of a deterministic bottom-up tree automaton (DFTA) with n states. This naturally leads to two types of synchronizing terms, called weak and strong, that depend on whether a variable, i.e., a placeholder for a subtree, must be present in at least one leaf or all of them. We prove that the maximum height in the case of weak synchronization has a theoretical upper bound [Formula: see text], where [Formula: see text] is the maximum length of the shortest synchronizing string of an n-state DFAs. For strong synchronization, we prove exponential bounds. We provide a theoretical upper bound of [Formula: see text] for the height and two constructions of automata approaching it. One achieves the height of [Formula: see text] with an alphabet of linear size and maximum arity\u00a0r, and the other achieves [Formula: see text] with an alphabet of quadratic size.<\/jats:p>","DOI":"10.1142\/s0129054125410096","type":"journal-article","created":{"date-parts":[[2025,9,8]],"date-time":"2025-09-08T10:27:41Z","timestamp":1757327261000},"page":"215-239","source":"Crossref","is-referenced-by-count":0,"title":["On the Smallest Synchronizing Terms of Finite Tree Automata"],"prefix":"10.1142","volume":"37","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9165-6280","authenticated-orcid":false,"given":"V\u00e1clav","family":"Bla\u017eej","sequence":"first","affiliation":[{"name":"University of Warwick, Coventry, CV4 7AL, United Kingdom"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9329-1000","authenticated-orcid":false,"given":"Jan","family":"Janou\u0161ek","sequence":"additional","affiliation":[{"name":"Department of Theoretical Computer Science, Faculty of Information Technology, Czech Technical University in Prague, Th\u00e1kurova 9, Prague, 160 00, Czechia"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3783-8870","authenticated-orcid":false,"given":"\u0160t\u011bp\u00e1n","family":"Plach\u00fd","sequence":"additional","affiliation":[{"name":"Department of Theoretical Computer Science, Faculty of Information Technology, Czech Technical University in Prague, Th\u00e1kurova 9, Prague, 160 00, Czechia"},{"name":"Department of Computing Science, Ume\u00e5 University, Campustorget 5, Ume\u00e5, 901 87, Sweden"}]}],"member":"219","published-online":{"date-parts":[[2025,9,6]]},"reference":[{"key":"S0129054125410096BIB001","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-40247-0_5"},{"key":"S0129054125410096BIB002","unstructured":"H. Comon, M. Dauchet, R. Gilleron, C. L\u00f6ding, F. Jacquemard, D. Lugiez, S. Tison and M. Tommasi, Tree automata techniques and applications (2008)."},{"key":"S0129054125410096BIB003","doi-asserted-by":"crossref","unstructured":"F. G\u00e9cseg and  M. Steinby ,  Handbook of Formal Languages: Volume 3 Beyond Words (Springer,  Berlin, Heidelberg,  1997), ch. Tree Languages, pp. 1\u201368.","DOI":"10.1007\/978-3-642-59126-6_1"},{"key":"S0129054125410096BIB004","doi-asserted-by":"publisher","DOI":"10.3103\/S1066369X10010056"},{"key":"S0129054125410096BIB005","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38536-0_7"},{"key":"S0129054125410096BIB006","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-0208(08)73432-7"},{"key":"S0129054125410096BIB007","volume-title":"Handbook of Automata Theory","author":"Pin J.","year":"2021"},{"key":"S0129054125410096BIB008","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-38919-2_47"},{"key":"S0129054125410096BIB009","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-07469-1_8"},{"key":"S0129054125410096BIB010","doi-asserted-by":"publisher","DOI":"10.1007\/BF01069104"},{"key":"S0129054125410096BIB011","doi-asserted-by":"publisher","DOI":"10.1088\/1742-6596\/1352\/1\/012047"},{"issue":"2","key":"S0129054125410096BIB012","first-page":"367","volume":"24","author":"Shitov Y.","year":"2019","journal-title":"Journal of Automata, Languages and Combinatorics"},{"key":"S0129054125410096BIB013","unstructured":"M. Szykula, Improving the upper bound on the length of the shortest reset word,\n                      35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)\n                      ,\n                      Leibniz International Proceedings in Informatics (LIPIcs)\n                      96\n                      (Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2018), pp. 56:1\u201356:13."},{"issue":"3","key":"S0129054125410096BIB014","first-page":"208","volume":"14","author":"\u010cern\u00fd J.","year":"1964","journal-title":"Matematicko-fyzik\u00e1lny \u010dasopis"},{"issue":"4","key":"S0129054125410096BIB015","first-page":"289","volume":"07","author":"\u010cern\u00fd J.","year":"1971","journal-title":"Kybernetika"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054125410096","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T05:37:06Z","timestamp":1770961026000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S0129054125410096"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,9,6]]},"references-count":15,"journal-issue":{"issue":"01","published-print":{"date-parts":[[2026,1]]}},"alternative-id":["10.1142\/S0129054125410096"],"URL":"https:\/\/doi.org\/10.1142\/s0129054125410096","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,9,6]]}}}