{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:34:09Z","timestamp":1759638849975,"version":"3.41.2"},"reference-count":1,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2014,2,12]],"date-time":"2014-02-12T00:00:00Z","timestamp":1392163200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/arxiv.org\/licenses\/nonexclusive-distrib\/1.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>In this paper we show that {\\omega}B- and {\\omega}S-regular languages satisfy\nthe following separation-type theorem If L1,L2 are disjoint languages of\n{\\omega}-words both recognised by {\\omega}B- (resp. {\\omega}S)-automata then\nthere exists an {\\omega}-regular language Lsep that contains L1, and whose\ncomplement contains L2. In particular, if a language and its complement are\nrecognised by {\\omega}B- (resp. {\\omega}S)-automata then the language is\n{\\omega}-regular. The result is especially interesting because, as shown by\nBoja\\'nczyk and Colcombet, {\\omega}B-regular languages are complements of\n{\\omega}S-regular languages. Therefore, the above theorem shows that these are\ntwo mutually dual classes that both have the separation property. Usually (e.g.\nin descriptive set theory or recursion theory) exactly one class from a pair C,\nCc has the separation property. The proof technique reduces the separation\nproperty for {\\omega}-word languages to profinite languages using Ramsey's\ntheorem and topological methods. After that reduction, the analysis of the\nseparation property in the profinite monoid is relatively simple. The whole\nconstruction is technically not complicated, moreover it seems to be quite\nextensible. The paper uses a framework for the analysis of B- and S-regular\nlanguages in the context of the profinite monoid that was proposed by\nToru\\'nczyk.<\/jats:p>","DOI":"10.2168\/lmcs-10(1:8)2014","type":"journal-article","created":{"date-parts":[[2014,7,15]],"date-time":"2014-07-15T09:40:14Z","timestamp":1405417214000},"source":"Crossref","is-referenced-by-count":2,"title":["Separation Property for wB- and wS-regular Languages"],"prefix":"10.46298","volume":"Volume 10, Issue 1","author":[{"given":"Micha\u0142","family":"Skrzypczak","sequence":"first","affiliation":[]}],"member":"25203","published-online":{"date-parts":[[2014,2,12]]},"reference":[{"key":"719:not-found"}],"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/1224\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/1224\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,11]],"date-time":"2023-04-11T20:06:07Z","timestamp":1681243567000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/1224"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,2,12]]},"references-count":1,"URL":"https:\/\/doi.org\/10.2168\/lmcs-10(1:8)2014","relation":{"is-same-as":[{"id-type":"arxiv","id":"1401.3214","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.1401.3214","asserted-by":"subject"}],"is-referenced-by":[{"id-type":"arxiv","id":"1910.02164","asserted-by":"subject"},{"id-type":"doi","id":"10.4230\/lipics.stacs.2020.32","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arxiv.1910.02164","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2014,2,12]]},"article-number":"1224"}}