Standard

Efficient algorithms for membership in boolean hierarchies of regular languages. / Glaßer, Christian; Schmitz, Heinz; Selivanov, Victor.

In: Theoretical Computer Science, Vol. 646, 01.01.2016, p. 86-108.

Research output: Contribution to journal › Article › peer-review

Harvard

Glaßer, C, Schmitz, H & Selivanov, V 2016, 'Efficient algorithms for membership in boolean hierarchies of regular languages', Theoretical Computer Science, vol. 646, pp. 86-108. https://doi.org/10.1016/j.tcs.2016.07.017

APA

Glaßer, C., Schmitz, H., & Selivanov, V. (2016). Efficient algorithms for membership in boolean hierarchies of regular languages. Theoretical Computer Science, 646, 86-108. https://doi.org/10.1016/j.tcs.2016.07.017

Vancouver

Glaßer C, Schmitz H, Selivanov V. Efficient algorithms for membership in boolean hierarchies of regular languages. Theoretical Computer Science. 2016 Jan 1;646:86-108. https://doi.org/10.1016/j.tcs.2016.07.017

Author

Glaßer, Christian ; Schmitz, Heinz ; Selivanov, Victor. / Efficient algorithms for membership in boolean hierarchies of regular languages. In: Theoretical Computer Science. 2016 ; Vol. 646. pp. 86-108.

BibTeX

@article{f51118085d4844db98dfb9dd38de557d,
title = "Efficient algorithms for membership in boolean hierarchies of regular languages",
abstract = "This paper provides 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 Σ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 Σ1 are decidable.• For the restricted case of a two-letter alphabet, the classes of the Boolean hierarchy over level Σ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.",
keywords = "Automata and formal languages, Boolean hierarchy, Computational complexity, Decidability, Dot-depth hierarchy, Efficient algorithms",
author = "Christian Gla{\ss}er and Heinz Schmitz and Victor Selivanov",
year = "2016",
month = jan,
day = "1",
doi = "10.1016/j.tcs.2016.07.017",
language = "English",
volume = "646",
pages = "86--108",
journal = "Theoretical Computer Science",
issn = "0304-3975",
publisher = "Elsevier",

}

RIS

TY - JOUR

T1 - Efficient algorithms for membership in boolean hierarchies of regular languages

AU - Glaßer, Christian

AU - Schmitz, Heinz

AU - Selivanov, Victor

PY - 2016/1/1

Y1 - 2016/1/1

N2 - This paper provides 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 Σ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 Σ1 are decidable.• For the restricted case of a two-letter alphabet, the classes of the Boolean hierarchy over level Σ2 of the Straubing–Thé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.

AB - This paper provides 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 Σ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 Σ1 are decidable.• For the restricted case of a two-letter alphabet, the classes of the Boolean hierarchy over level Σ2 of the Straubing–Thé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.

KW - Automata and formal languages

KW - Boolean hierarchy

KW - Computational complexity

KW - Decidability

KW - Dot-depth hierarchy

KW - Efficient algorithms

UR - http://www.scopus.com/inward/record.url?scp=84999098837&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2016.07.017

DO - 10.1016/j.tcs.2016.07.017

M3 - Article

AN - SCOPUS:84999098837

VL - 646

SP - 86

EP - 108

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

ER -

ID: 126985832