Efficient Algorithms for Membership in Boolean Hierarchies of Regular Languages

Details Efficient Algorithms for Membership in Boolean Hierarchies of Regular Languages Efficient Algorithms for Membership in Boolean Hierarchies of Regular Languages

2008-02-20

arxiv.org/abs/0802.2868v1

Dans Proceedings of the 25th Annual Symposium on the Theoretical Aspects of Computer Science - STACS 2008, Bordeaux : France (

Computer Science

Computational Complexity

Scientific paper

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\'erien 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$.

Affiliated with

Also associated with

No associations

Rating

Efficient Algorithms for Membership in Boolean Hierarchies of Regular Languages does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Efficient Algorithms for Membership in Boolean Hierarchies of Regular Languages, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient Algorithms for Membership in Boolean Hierarchies of Regular Languages will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-647942