Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > LOGSPACE DECISION ALGORITHMS:
Reports tagged with logspace decision algorithms:
TR07-094 | 3rd August 2007
Christian Glaßer, Heinz Schmitz, Victor Selivanov

Efficient Algorithms for Membership in Boolean Hierarchies of Regular Languages

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:

1. The classes of ... more >>>




ISSN 1433-8092 | Imprint