Separating Regular Languages by Locally Testable and Locally Threshold Testable Languages

Place, Thomas; van Rooijen, Lorijn; Zeitoun, Marc

doi:10.4230/LIPIcs.FSTTCS.2013.363

Document

Separating Regular Languages by Locally Testable and Locally Threshold Testable Languages

Authors Thomas Place, Lorijn van Rooijen, Marc Zeitoun

Part of: Volume: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)
Part of: Series: Leibniz International Proceedings in Informatics (LIPIcs)
Part of: Conference: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS)
License: Creative Commons Attribution 3.0 Unported license
Publication Date: 2013-12-10

PDF

File

PDF

LIPIcs.FSTTCS.2013.363.pdf

Filesize: 452 kB
13 pages

Document Identifiers

DOI: 10.4230/LIPIcs.FSTTCS.2013.363
URN: urn:nbn:de:0030-drops-43867

Subject Classification

Keywords

Automata
Logics
Monoids
Locally testable
Separation
Context-free.

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

Abstract

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.

Cite As Get BibTex

Thomas Place, Lorijn van Rooijen, and Marc Zeitoun. Separating Regular Languages by Locally Testable and Locally Threshold Testable Languages. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 363-375, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013) https://doi.org/10.4230/LIPIcs.FSTTCS.2013.363

Author Details

Thomas Place

Lorijn van Rooijen

Marc Zeitoun

Any Issues?

Feedback on the Current Page

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail