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.STACS.2015.662
URN: urn:nbn:de:0030-drops-49499
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/4949/
Go to the corresponding LIPIcs Volume Portal

Place, Thomas ; Zeitoun, Marc

Separation and the Successor Relation

pdf-format:
49.pdf (0.6 MB)

Abstract

We investigate two problems for a class C of regular word languages. The
C-membership problem asks for an algorithm to decide whether an input language belongs to C. The C-separation problem asks for an algorithm that, given as input two regular languages, decides whether there exists a third language in C containing the first language, while being disjoint from the second. These problems are considered as means to obtain a deep understanding of the class C.

It is usual for such classes to be defined by logical formalisms. Logics are often built on top of each other, by adding new predicates. A natural construction is to enrich a logic with the successor relation. In this paper, we obtain new and simple proofs of two transfer results: we show that for suitable logically defined classes, the membership, resp. the separation problem for a class enriched with the successor relation reduces to the same problem for the original class.

Our reductions work both for languages of finite words and infinite words. The proofs are mostly self-contained, and only require a basic background on regular languages. This paper therefore gives simple proofs of results that were considered as difficult, such as the decidability of the membership problem for the levels 1, 3/2, 2 and 5/2 of the dot-depth hierarchy.

BibTeX - Entry

@InProceedings{place_et_al:LIPIcs:2015:4949,
  author =	{Thomas Place and Marc Zeitoun},
  title =	{{Separation and the Successor Relation}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{662--675},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Ernst W. Mayr and Nicolas Ollinger},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/4949},
  URN =		{urn:nbn:de:0030-drops-49499},
  doi =		{10.4230/LIPIcs.STACS.2015.662},
  annote =	{Keywords: separation problem, regular word languages, logics, decidable characterizations, semidirect product}
}

Keywords: separation problem, regular word languages, logics, decidable characterizations, semidirect product
Collection: 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)
Issue Date: 2015
Date of publication: 26.02.2015

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