2026-08-09T16:34:31Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14195 2024-03-06T10:53:43Z ddc:004 open_access

Deterministic and Game Separability for Regular Languages of Infinite Trees Clemente, Lorenzo Skrzypczak, Michał separation infinite trees regular languages deterministic automata game automata We show that it is decidable whether two regular languages of infinite trees are separable by a deterministic language, resp., a game language. We consider two variants of separability, depending on whether the set of priorities of the separator is fixed, or not. In each case, we show that separability can be decided in EXPTIME, and that separating automata of exponential size suffice. We obtain our results by reducing to infinite duration games with ω-regular winning conditions and applying the finite-memory determinacy theorem of Büchi and Landweber. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Lorenzo Clemente and Michał Skrzypczak 2021 Is Part Of LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2021.126 urn:nbn:de:0030-drops-141952 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.126 eng https://creativecommons.org/licenses/by/4.0/legalcode