2026-08-17T07:55:36Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4386 2024-03-06T10:34:59Z ddc:004 open_access

Separating Regular Languages by Locally Testable and Locally Threshold Testable Languages Place, Thomas van Rooijen, Lorijn Zeitoun, Marc Automata Logics Monoids Locally testable Separation Context-free. A separator for two languages is a third language containing the first one and disjoint from the second one. We investigate the following decision problem: given two regular input languages, decide whether there exists a locally testable (resp. a locally threshold testable) separator. In both cases, we design a decision procedure based on the occurrence of special patterns in automata accepting the input languages. We prove that the problem is computationally harder than deciding membership. The correctness proof of the algorithm yields a stronger result, namely a description of a possible separator. Finally, we discuss the same problem for context-free input languages. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Thomas Place and Lorijn van Rooijen and Marc Zeitoun 2013 Is Part Of LIPIcs, Volume 24, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2013.363 urn:nbn:de:0030-drops-43867 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.363 eng https://creativecommons.org/licenses/by/3.0/legalcode