English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The purpose of this paper is to provide efficient algorithms that decidemembership for classes of several Boolean hierarchies for which efficiency (oreven decidability) were previously not known. We develop new forbidden-chaincharacterizations for the single levels of these hierarchies and obtain thefollowing results: - The classes of the Boolean hierarchy over level $\Sigma_1$of the dot-depth hierarchy are decidable in $NL$ (previously only thedecidability was known). The same remains true if predicates mod $d$ for fixed$d$ are allowed. - If modular predicates for arbitrary $d$ are allowed, thenthe classes of the Boolean hierarchy over level $\Sigma_1$ are decidable. - Forthe restricted case of a two-letter alphabet, the classes of the Booleanhierarchy over level $\Sigma_2$ of the Straubing-Th\'erien hierarchy aredecidable in $NL$. This is the first decidability result for this hierarchy. -The membership problems for all mentioned Boolean-hierarchy classes arelogspace many-one hard for $NL$. - The membership problems for quasi-aperiodiclanguages and for $d$-quasi-aperiodic languages are logspace many-one completefor $PSPACE$.

Efficient Algorithms for Membership in Boolean Hierarchies of Regular Languages