License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2021.46
URN: urn:nbn:de:0030-drops-155574
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/15557/
Go to the corresponding LIPIcs Volume Portal

Hugenroth, Christopher

Separating Regular Languages over Infinite Words with Respect to the Wagner Hierarchy

pdf-format:
LIPIcs-FSTTCS-2021-46.pdf (0.6 MB)

Abstract

We investigate the separation problem for regular ω-languages with respect to the Wagner hierarchy where the input languages are given as deterministic Muller automata (DMA). We show that a minimal separating DMA can be computed in exponential time and that some languages require separators of exponential size. Further, we show that in this setting it can be decided in polynomial time whether a separator exists on a certain level of the Wagner hierarchy and that emptiness of the intersection of two languages given by DMAs can be decided in polynomial time. Finally, we show that separation can also be decided in polynomial time if the input languages are given as deterministic parity automata.

BibTeX - Entry

@InProceedings{hugenroth:LIPIcs.FSTTCS.2021.46,
  author =	{Hugenroth, Christopher},
  title =	{{Separating Regular Languages over Infinite Words with Respect to the Wagner Hierarchy}},
  booktitle =	{41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)},
  pages =	{46:1--46:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-215-0},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{213},
  editor =	{Boja\'{n}czy, Miko{\l}aj and Chekuri, Chandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/15557},
  URN =		{urn:nbn:de:0030-drops-155574},
  doi =		{10.4230/LIPIcs.FSTTCS.2021.46},
  annote =	{Keywords: Separation, Regular, Wagner Hierarchy, Muller Automata, Parity Automata, Product Automata, Membership}
}

Keywords: Separation, Regular, Wagner Hierarchy, Muller Automata, Parity Automata, Product Automata, Membership
Collection: 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)
Issue Date: 2021
Date of publication: 29.11.2021

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