1 Search Results for "Schmitz, Heinz"

Document
DOI: 10.4230/LIPIcs.STACS.2008.1355
Efficient Algorithms for Membership in Boolean Hierarchies of Regular Languages

Authors: Christian Glasser, Heinz Schmitz, and Victor Selivanov

Published in: LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)

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$.
Cite as

Christian Glasser, Heinz Schmitz, and Victor Selivanov. Efficient Algorithms for Membership in Boolean Hierarchies of Regular Languages. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 337-348, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{glasser_et_al:LIPIcs.STACS.2008.1355,
  author =	{Glasser, Christian and Schmitz, Heinz and Selivanov, Victor},
  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 =	{Albers, Susanne and Weil, Pascal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.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}
}
  • Refine by Author
  • 1 Glasser, Christian
  • 1 Schmitz, Heinz
  • 1 Selivanov, Victor

  • Refine by Classification

  • Refine by Keyword
  • 1 Automata and formal languages
  • 1 Boolean hierarchy
  • 1 computational complexity
  • 1 decidability
  • 1 dot-depth hierarchy
  • Show More...

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2008

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact