License: Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2008.1355
URN: urn:nbn:de:0030-drops-13554
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2008/1355/
Go to the corresponding LIPIcs Volume Portal

Glasser, Christian ; Schmitz, Heinz ; Selivanov, Victor

Efficient Algorithms for Membership in Boolean Hierarchies of Regular Languages

pdf-format:
22011.GlasserChristian.Paper.1355.pdf (0.2 MB)

Abstract

The purpose of this paper is to provide efficient algorithms that
decide membership for classes of several Boolean hierarchies for
which efficiency (or even decidability) were previously not known.
We develop new forbidden-chain characterizations for the single
levels of these hierarchies and obtain the following results:

- The classes of the Boolean hierarchy over level $Sigma_1$ of the
dot-depth hierarchy are decidable in $NL$ (previously only the
decidability was known). The same remains true if predicates mod
$d$ for fixed $d$ are allowed.

- If modular predicates for arbitrary $d$ are allowed, then the
classes of the Boolean hierarchy over level $Sigma_1$ are
decidable.

- For the restricted case of a two-letter alphabet, the classes of
the Boolean hierarchy over level $Sigma_2$ of the
Straubing-Th{'\e}rien hierarchy are decidable in $NL$. This is
the first decidability result for this hierarchy.

- The membership problems for all mentioned Boolean-hierarchy
classes are logspace many-one hard for $NL$.

- The membership problems for quasi-aperiodic languages and for
$d$-quasi-aperiodic languages are logspace many-one complete for
$PSPACE$.


BibTeX - Entry

@InProceedings{glasser_et_al:LIPIcs:2008:1355,
  author =	{Christian Glasser and Heinz Schmitz and Victor Selivanov},
  title =	{{Efficient Algorithms for Membership in Boolean Hierarchies of Regular Languages}},
  booktitle =	{25th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{337--348},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-06-4},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{1},
  editor =	{Susanne Albers and Pascal Weil},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2008/1355},
  URN =		{urn:nbn:de:0030-drops-13554},
  doi =		{10.4230/LIPIcs.STACS.2008.1355},
  annote =	{Keywords: Automata and formal languages, computational complexity, dot-depth hierarchy, Boolean hierarchy, decidability, efficient algorithms}
}

Keywords: Automata and formal languages, computational complexity, dot-depth hierarchy, Boolean hierarchy, decidability, efficient algorithms
Collection: 25th International Symposium on Theoretical Aspects of Computer Science
Issue Date: 2008
Date of publication: 06.02.2008

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