Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: The Power of Programs over Monoids in J and Threshold Dot-depth One
  Languages   The model of programs over (finite) monoids, introduced by Barrington and
Th\'erien, gives an interesting way to characterise the circuit complexity
class $\mathsf{NC^1}$ and its subclasses and showcases deep connections with
algebraic automata theory. In this article, we investigate the computational
power of programs over monoids in $\mathbf{J}$, a small variety of finite
aperiodic monoids. First, we give a fine hierarchy within the class of
languages recognised by programs over monoids from $\mathbf{J}$, based on the
length of programs but also some parametrisation of $\mathbf{J}$. Second, and
most importantly, we make progress in understanding what regular languages can
be recognised by programs over monoids in $\mathbf{J}$. To this end, we
introduce a new class of restricted dot-depth one languages, threshold
dot-depth one languages. We show that programs over monoids in $\mathbf{J}$
actually can recognise all languages from this class, using a non-trivial
trick, and conjecture that threshold dot-depth one languages with additional
positional modular counting suffice to characterise the regular languages
recognised by programs over monoids in $\mathbf{J}$. Finally, using a result by
J. C. Costa, we give an algebraic characterisation of threshold dot-depth one
languages that supports that conjecture and is of independent interest.

6
The categories of this paper are: astro-ph
33
The categories of this paper are: plasm-ph
32
The categories of this paper are: atom-ph
27
The categories of this paper are: comp-gas
9
The categories of this paper are: nlin
22
The categories of this paper are: chao-dyn
20
The categories of this paper are: acc-phys
14
The categories of this paper are: math-ph
0
The categories of this paper are: hep-ph
5
The categories of this paper are: gr-qc
11
The categories of this paper are: hep-lat
13
The categories of this paper are: quant-ph
34
The categories of this paper are: chem-ph
24
The categories of this paper are: dg-ga
12
The categories of this paper are: nucl-th
26
The categories of this paper are: bayes-an