ECCC-Report TR07-094https://eccc.weizmann.ac.il/report/2007/094Comments and Revisions published for TR07-094en-usMon, 01 Oct 2007 16:15:22 +0200
Paper TR07-094
| Efficient Algorithms for Membership in Boolean Hierarchies of Regular Languages |
Christian Glaßer,
Heinz Schmitz,
Victor Selivanov
https://eccc.weizmann.ac.il/report/2007/094The 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 the Boolean hierarchy over level Sigma_1 of the dot-depth hierarchy are decidable in NL (previously only the decidability was known).
2. The same remains true if predicates mod d for fixed d are added.
3. If modular predicates for arbitrary d are allowed, then the classes of the Boolean hierarchy over level Sigma_1 are decidable.
4. For the restricted case of a two-letter alphabet, the classes of the Boolean hierarchy over level Sigma_2 of the Straubing-Therien hierarchy are decidable in NL. This is the first decidability result for this hierarchy.
5. The membership problems for all mentioned Boolean-hierarchy classes are logspace many-one hard for NL.
6. The membership problems for quasi-aperiodic languages and for d-quasi-aperiodic languages are logspace many-one complete for PSPACE.
Mon, 01 Oct 2007 16:15:22 +0200https://eccc.weizmann.ac.il/report/2007/094