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.2018.47
URN: urn:nbn:de:0030-drops-99463
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9946/
Go to the corresponding LIPIcs Volume Portal

Place, Thomas ; Zeitoun, Marc

The Complexity of Separation for Levels in Concatenation Hierarchies

pdf-format:
LIPIcs-FSTTCS-2018-47.pdf (0.5 MB)

Abstract

We investigate the complexity of the separation problem associated to classes of regular languages. For a class C, C-separation takes two regular languages as input and asks whether there exists a third language in C which includes the first and is disjoint from the second. First, in contrast with the situation for the classical membership problem, we prove that for most classes C, the complexity of C-separation does not depend on how the input languages are represented: it is the same for nondeterministic finite automata and monoid morphisms. Then, we investigate specific classes belonging to finitely based concatenation hierarchies. It was recently proved that the problem is always decidable for levels 1/2 and 1 of any such hierarchy (with inefficient algorithms). Here, we build on these results to show that when the alphabet is fixed, there are polynomial time algorithms for both levels. Finally, we investigate levels 3/2 and 2 of the famous Straubing-Thérien hierarchy. We show that separation is PSpace-complete for level 3/2 and between PSpace-hard and EXPTime for level 2.

BibTeX - Entry

@InProceedings{place_et_al:LIPIcs:2018:9946,
  author =	{Thomas Place and Marc Zeitoun},
  title =	{{The Complexity of Separation for Levels in Concatenation Hierarchies}},
  booktitle =	{38th IARCS Annual Conference on Foundations of Software  Technology and Theoretical Computer Science (FSTTCS 2018)},
  pages =	{47:1--47:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-093-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{122},
  editor =	{Sumit Ganguly and Paritosh Pandya},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9946},
  URN =		{urn:nbn:de:0030-drops-99463},
  doi =		{10.4230/LIPIcs.FSTTCS.2018.47},
  annote =	{Keywords: Regular languages, separation, concatenation hierarchies, complexity}
}

Keywords: Regular languages, separation, concatenation hierarchies, complexity
Collection: 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)
Issue Date: 2018
Date of publication: 05.12.2018

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