The Power of Programs over Monoids in [Image: see text]
Nathan Grosshans · PubMed Central · 2020
The model of programs over (finite) monoids, introduced by Barrington and Thérien, gives an interesting way to characterise the circuit complexity class [Image: see text] and its subclasses and showcases deep connections with algebraic automata theory. In this article, we investigate the computational power of programs over monoids in [Image: see text], a small variety of finite aperiodic monoids. First, we give a fine hierarchy within the class of languages recognised by programs over monoids from [Image: see text], based on the length of programs but also some parametrisation of [Image: see text]. Second, and most importantly, we make progress in understanding what regular languages can be recognised by programs over monoids in [Image: see text]. We show that those programs actually can recognise all languages from a class of restricted dot-depth one languages, using a non-trivial trick, and conjecture that this class suffices to characterise the regular languages recognised by programs over monoids in [Image: see text].