{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,30]],"date-time":"2022-03-30T17:19:40Z","timestamp":1648660780497},"reference-count":22,"publisher":"World Scientific Pub Co Pte Lt","issue":"06","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2020,9]]},"abstract":"<jats:p> We consider an extension of tree automata on infinite trees that can use equality and disequality constraints between direct subtrees of a node. Recently, it has been shown that the emptiness problem for these kind of automata with a parity acceptance condition is decidable and that the corresponding class of languages is closed under Boolean operations. In this paper, we show that the class of languages recognizable by such tree automata with a B\u00fcchi acceptance condition is closed under projection. This construction yields a new algorithm for the emptiness problem, implies that a regular tree is accepted if the language is non-empty (for the B\u00fcchi condition), and can be used to obtain a decision procedure for an extension of monadic second-order logic with predicates for subtree comparisons. <\/jats:p>","DOI":"10.1142\/s012905412041004x","type":"journal-article","created":{"date-parts":[[2020,10,5]],"date-time":"2020-10-05T08:11:59Z","timestamp":1601885519000},"page":"749-775","source":"Crossref","is-referenced-by-count":0,"title":["Projection for B\u00fcchi Tree Automata with Constraints between Siblings"],"prefix":"10.1142","volume":"31","author":[{"given":"Patrick","family":"Landwehr","sequence":"first","affiliation":[{"name":"RWTH-Aachen University, Ahornstr. 55, 52072 Aachen, Germany"}]},{"given":"Christof","family":"L\u00f6ding","sequence":"additional","affiliation":[{"name":"RWTH-Aachen University, Ahornstr. 55, 52072 Aachen, Germany"}]}],"member":"219","published-online":{"date-parts":[[2020,10,5]]},"reference":[{"key":"S012905412041004XBIB001","volume-title":"Principles of Model Checking","author":"Baier C.","year":"2008"},{"key":"S012905412041004XBIB002","first-page":"263","volume-title":"LICS","author":"Bargu\u00f1\u00f3 L.","year":"2010"},{"key":"S012905412041004XBIB004","first-page":"161","volume-title":"STACS","author":"Bogaert B.","year":"1992"},{"key":"S012905412041004XBIB005","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1145\/2933575.2934504","volume-title":"LICS","author":"Carayol A.","year":"2016"},{"key":"S012905412041004XBIB007","doi-asserted-by":"publisher","DOI":"10.1142\/S012905411000743X"},{"issue":"4","key":"S012905412041004XBIB008","doi-asserted-by":"crossref","first-page":"23:1","DOI":"10.1145\/2508028.2501600","volume":"60","author":"Godoy G.","year":"2013","journal-title":"J. ACM"},{"key":"S012905412041004XBIB009","first-page":"485","volume-title":"STOC","author":"Godoy G.","year":"2010"},{"key":"S012905412041004XBIB010","doi-asserted-by":"crossref","first-page":"386","DOI":"10.1007\/978-3-540-78127-1_21","volume-title":"Pillars of Computer Science","author":"Kaminski M.","year":"2008"},{"key":"S012905412041004XBIB011","first-page":"681","volume-title":"ICALP","author":"Klaedtke F.","year":"2003"},{"key":"S012905412041004XBIB013","first-page":"531","volume-title":"FOCS","author":"Kupferman O.","year":"2005"},{"key":"S012905412041004XBIB014","first-page":"478","volume-title":"Developments in Language Theory \u2014 22nd International Conference, DLT 2018","author":"Landwehr P.","year":"2018"},{"key":"S012905412041004XBIB015","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1016\/0304-3975(84)90049-5","volume":"32","author":"Miyano S.","year":"1984","journal-title":"Theor. Comput. Sci."},{"key":"S012905412041004XBIB016","first-page":"275","volume-title":"ICALP","author":"Muller D. E.","year":"1986"},{"issue":"1","key":"S012905412041004XBIB017","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1016\/0304-3975(94)00214-4","volume":"141","author":"Muller D. E.","year":"1995","journal-title":"Theor. Comput. Sci."},{"key":"S012905412041004XBIB018","first-page":"1","volume":"141","author":"Rabin M. O.","year":"1969","journal-title":"Transactions of the American Mathematical Society"},{"key":"S012905412041004XBIB019","first-page":"1","volume-title":"Mathematical Logic and Foundations of Set Theory","author":"Rabin M. O.","year":"1970"},{"key":"S012905412041004XBIB020","first-page":"319","volume-title":"FOCS","author":"Safra S.","year":"1988"},{"key":"S012905412041004XBIB021","first-page":"155","volume-title":"ACM SIGACT-SIGMOD-SIGART","author":"Seidl H.","year":"2003"},{"issue":"1","key":"S012905412041004XBIB022","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1007\/BF01691346","volume":"2","author":"Thatcher J. W.","year":"1968","journal-title":"Math. Systems Theory"},{"key":"S012905412041004XBIB023","doi-asserted-by":"crossref","first-page":"389","DOI":"10.1007\/978-3-642-59126-6_7","volume-title":"Handbook of Formal Language Theory","author":"Thomas W.","year":"1997"},{"key":"S012905412041004XBIB024","first-page":"629","volume-title":"Logic and Automata \u2014 History and Perspectives","author":"Vardi M. Y.","year":"2007"},{"issue":"3","key":"S012905412041004XBIB025","doi-asserted-by":"crossref","first-page":"418","DOI":"10.1016\/j.ipl.2014.11.005","volume":"115","author":"Veanes M.","year":"2015","journal-title":"Inf. Process. Lett."}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S012905412041004X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,13]],"date-time":"2020-11-13T08:59:26Z","timestamp":1605257966000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S012905412041004X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9]]},"references-count":22,"journal-issue":{"issue":"06","published-print":{"date-parts":[[2020,9]]}},"alternative-id":["10.1142\/S012905412041004X"],"URL":"https:\/\/doi.org\/10.1142\/s012905412041004x","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,9]]}}}