2026-07-23T04:54:46Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:1355 2024-03-06T10:32:59Z ddc:004 open_access

Efficient Algorithms for Membership in Boolean Hierarchies of Regular Languages Glasser, Christian Schmitz, Heinz Selivanov, Victor Automata and formal languages computational complexity dot-depth hierarchy Boolean hierarchy decidability efficient algorithms 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$. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Christian Glasser and Heinz Schmitz and Victor Selivanov 2008 Is Part Of LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2008.1355 urn:nbn:de:0030-drops-13554 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1355 eng https://creativecommons.org/licenses/by-nd/3.0/legalcode