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 model of programs over (finite) monoids, introduced by Barrington andTh\'erien, gives an interesting way to characterise the circuit complexityclass $\mathsf{NC^1}$ and its subclasses and showcases deep connections withalgebraic automata theory. In this article, we investigate the computationalpower of programs over monoids in $\mathbf{J}$, a small variety of finiteaperiodic monoids. First, we give a fine hierarchy within the class oflanguages recognised by programs over monoids from $\mathbf{J}$, based on thelength of programs but also some parametrisation of $\mathbf{J}$. Second, andmost importantly, we make progress in understanding what regular languages canbe recognised by programs over monoids in $\mathbf{J}$. To this end, weintroduce a new class of restricted dot-depth one languages, thresholddot-depth one languages. We show that programs over monoids in $\mathbf{J}$actually can recognise all languages from this class, using a non-trivialtrick, and conjecture that threshold dot-depth one languages with additionalpositional modular counting suffice to characterise the regular languagesrecognised by programs over monoids in $\mathbf{J}$. Finally, using a result byJ. C. Costa, we give an algebraic characterisation of threshold dot-depth onelanguages that supports that conjecture and is of independent interest.

The Power of Programs over Monoids in J and Threshold Dot-depth One Languages