Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH scholarly article en Clemente, Lorenzo; Skrzypczak, Michał https://www.dagstuhl.de/lipics License: Creative Commons Attribution 4.0 license (CC BY 4.0)
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-141952
URL:

;

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


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI