Thomas Place ; Lorijn van Rooijen ; Marc Zeitoun - On Separation by Locally Testable and Locally Threshold Testable Languages

lmcs:1163 - Logical Methods in Computer Science, September 18, 2014, Volume 10, Issue 3 - https://doi.org/10.2168/LMCS-10(3:24)2014
On Separation by Locally Testable and Locally Threshold Testable LanguagesArticle

Authors: Thomas Place ; Lorijn van Rooijen ; Marc Zeitoun ORCID

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.

https://doi.org/10.2168/LMCS-10(3:24)2014
Source: arXiv.org:1308.0181
Volume: Volume 10, Issue 3
Published on: September 18, 2014
Imported on: November 25, 2013
Keywords: Computer Science - Formal Languages and Automata Theory
Licence: arXiv.org - Non-exclusive license to distribute

Classifications

Mathematics Subject Classification 20201
Sources:
  • [1] zbMATH Open.

9 Documents citing this article

Share and export

Consultation statistics

This page has been seen 2321 times.
This article's PDF has been downloaded 534 times.