Creative Commons Attribution 4.0 license (CC BY 4.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2021.126
URN: urn:nbn:de:0030-drops-141952
URL: https://drops.dagstuhl.de/opus/volltexte/2021/14195/
Clemente, Lorenzo ; Skrzypczak, Michał
Deterministic and Game Separability for Regular Languages of Infinite Trees
| pdf-format: |
|
Abstract
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.
BibTeX - Entry
@InProceedings{clemente_et_al:LIPIcs.ICALP.2021.126,
author = {Clemente, Lorenzo and Skrzypczak, Micha{\l}},
title = {{Deterministic and Game Separability for Regular Languages of Infinite Trees}},
booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
pages = {126:1--126:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-195-5},
ISSN = {1868-8969},
year = {2021},
volume = {198},
editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14195},
URN = {urn:nbn:de:0030-drops-141952},
doi = {10.4230/LIPIcs.ICALP.2021.126},
annote = {Keywords: separation, infinite trees, regular languages, deterministic automata, game automata}
}
| Keywords: | separation, infinite trees, regular languages, deterministic automata, game automata | |
| Seminar: | 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) | |
| Issue date: | 2021 | |
| Date of publication: | 02.07.2021 |
