Creative Commons Attribution 4.0 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: https://drops.dagstuhl.de/opus/volltexte/2021/15557/
Hugenroth, Christopher
Separating Regular Languages over Infinite Words with Respect to the Wagner Hierarchy
| pdf-format: |
|
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 | |
| Seminar: | 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021) | |
| Issue date: | 2021 | |
| Date of publication: | 29.11.2021 |
