{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,3,2]],"date-time":"2024-03-02T07:56:21Z","timestamp":1709366181441},"reference-count":9,"publisher":"World Scientific Pub Co Pte Ltd","issue":"01n02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2024,2]]},"abstract":"<jats:p> The class of Boolean combinations of tree languages recognized by deterministic top-down tree automata (also known as deterministic root-to-frontier automata) is studied. The problem of determining for a given regular tree language whether it belongs to this class is open. We provide some progress by two results: First, a characterization of this class by a natural extension of deterministic top-down tree automata is presented, and as an application we obtain a convenient method to show that certain regular tree languages are outside this class. In the second result, it is shown that, for fixed [Formula: see text], it is decidable whether a regular tree language is a Boolean combination of [Formula: see text] tree languages recognized by deterministic top-down tree automata. <\/jats:p>","DOI":"10.1142\/s0129054123480015","type":"journal-article","created":{"date-parts":[[2023,6,28]],"date-time":"2023-06-28T11:12:30Z","timestamp":1687950750000},"page":"11-22","source":"Crossref","is-referenced-by-count":0,"title":["On the Boolean Closure of Deterministic Top-Down Tree Automata"],"prefix":"10.1142","volume":"35","author":[{"given":"Christof","family":"L\u00f6ding","sequence":"first","affiliation":[{"name":"RWTH Aachen University, Informatik 7, Aachen, Germany"}]},{"given":"Wolfgang","family":"Thomas","sequence":"additional","affiliation":[{"name":"RWTH Aachen University, Informatik 7, Aachen, Germany"}]}],"member":"219","published-online":{"date-parts":[[2023,6,28]]},"reference":[{"issue":"1","key":"S0129054123480015BIB002","first-page":"37","volume":"4","author":"G\u00e9cseg F.","year":"1978","journal-title":"Acta Cybern."},{"key":"S0129054123480015BIB003","volume-title":"Tree Automata","author":"G\u00e9cseg F.","year":"1984"},{"issue":"4","key":"S0129054123480015BIB004","first-page":"255","volume":"10","author":"Jurvanen E.","year":"1992","journal-title":"Acta Cybern."},{"key":"S0129054123480015BIB005","first-page":"3","volume-title":"Developments in Language Theory, At the Crossroads of Mathematics, Computer Science and Biology, Turku, Finland, 12-15 July 1993","author":"Jurvanen E.","year":"1994"},{"key":"S0129054123480015BIB007","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-86593-1_24"},{"key":"S0129054123480015BIB008","doi-asserted-by":"publisher","DOI":"10.1109\/SWCT.1963.8"},{"key":"S0129054123480015BIB009","first-page":"1","volume-title":"Transactions of the American Mathematical Society","volume":"141","author":"Rabin M. O."},{"key":"S0129054123480015BIB010","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-59126-6_7"},{"key":"S0129054123480015BIB011","first-page":"33","volume":"5","author":"Vir\u00e1gh J.","year":"1980","journal-title":"Acta Cybernet."}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054123480015","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,15]],"date-time":"2024-02-15T02:58:47Z","timestamp":1707965927000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S0129054123480015"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,28]]},"references-count":9,"journal-issue":{"issue":"01n02","published-print":{"date-parts":[[2024,2]]}},"alternative-id":["10.1142\/S0129054123480015"],"URL":"https:\/\/doi.org\/10.1142\/s0129054123480015","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,6,28]]}}}