Michał Skrzypczak - Separation Property for wB- and wS-regular Languages

lmcs:1224 - Logical Methods in Computer Science, February 12, 2014, Volume 10, Issue 1 - https://doi.org/10.2168/LMCS-10(1:8)2014
Separation Property for wB- and wS-regular LanguagesArticle

Authors: Michał Skrzypczak

    In this paper we show that {\omega}B- and {\omega}S-regular languages satisfy the following separation-type theorem If L1,L2 are disjoint languages of {\omega}-words both recognised by {\omega}B- (resp. {\omega}S)-automata then there exists an {\omega}-regular language Lsep that contains L1, and whose complement contains L2. In particular, if a language and its complement are recognised by {\omega}B- (resp. {\omega}S)-automata then the language is {\omega}-regular. The result is especially interesting because, as shown by Boja\'nczyk and Colcombet, {\omega}B-regular languages are complements of {\omega}S-regular languages. Therefore, the above theorem shows that these are two mutually dual classes that both have the separation property. Usually (e.g. in descriptive set theory or recursion theory) exactly one class from a pair C, Cc has the separation property. The proof technique reduces the separation property for {\omega}-word languages to profinite languages using Ramsey's theorem and topological methods. After that reduction, the analysis of the separation property in the profinite monoid is relatively simple. The whole construction is technically not complicated, moreover it seems to be quite extensible. The paper uses a framework for the analysis of B- and S-regular languages in the context of the profinite monoid that was proposed by Toru\'nczyk.


    Volume: Volume 10, Issue 1
    Published on: February 12, 2014
    Imported on: January 17, 2012
    Keywords: Computer Science - Formal Languages and Automata Theory

    4 Documents citing this article

    Consultation statistics

    This page has been seen 1544 times.
    This article's PDF has been downloaded 309 times.