Efficient Algorithms for Membership in Boolean Hierarchies of Regular Languages

Christian Glasser, Heinz Schmitz & Victor Selivanov
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...
This data center is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.
We found no citations for this text. For information on how to provide citation information, please see our documentation.