License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2013.363
URN: urn:nbn:de:0030-drops-43867
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2013/4386/
Go to the corresponding LIPIcs Volume Portal

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

Separating Regular Languages by Locally Testable and Locally Threshold Testable Languages

pdf-format:
27.pdf (0.4 MB)

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.

BibTeX - Entry

@InProceedings{place_et_al:LIPIcs:2013:4386,
  author =	{Thomas Place and Lorijn van Rooijen and Marc Zeitoun},
  title =	{{Separating Regular Languages by Locally Testable and Locally Threshold Testable Languages}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
  pages =	{363--375},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-64-4},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{24},
  editor =	{Anil Seth and Nisheeth K. Vishnoi},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2013/4386},
  URN =		{urn:nbn:de:0030-drops-43867},
  doi =		{10.4230/LIPIcs.FSTTCS.2013.363},
  annote =	{Keywords: Automata, Logics, Monoids, Locally testable, Separation, Context-free.}
}

Keywords: Automata, Logics, Monoids, Locally testable, Separation, Context-free.
Collection: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)
Issue Date: 2013
Date of publication: 10.12.2013

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI