Nathan Grosshans ; Pierre Mckenzie ; Luc Segoufin - Tameness and the power of programs over monoids in DA

lmcs:7110 - Logical Methods in Computer Science, August 2, 2022, Volume 18, Issue 3 - https://doi.org/10.46298/lmcs-18(3:14)2022
Tameness and the power of programs over monoids in DA

Authors: Nathan Grosshans ; Pierre Mckenzie ; Luc Segoufin

The program-over-monoid model of computation originates with Barrington's proof that the model captures the complexity class $\mathsf{NC^1}$. Here we make progress in understanding the subtleties of the model. First, we identify a new tameness condition on a class of monoids that entails a natural characterization of the regular languages recognizable by programs over monoids from the class. Second, we prove that the class known as $\mathbf{DA}$ satisfies tameness and hence that the regular languages recognized by programs over monoids in $\mathbf{DA}$ are precisely those recognizable in the classical sense by morphisms from $\mathbf{QDA}$. Third, we show by contrast that the well studied class of monoids called $\mathbf{J}$ is not tame. Finally, we exhibit a program-length-based hierarchy within the class of languages recognized by programs over monoids from $\mathbf{DA}$.

Volume: Volume 18, Issue 3
Published on: August 2, 2022
Accepted on: April 13, 2022
Submitted on: January 20, 2021
Keywords: Computer Science - Computational Complexity,Computer Science - Discrete Mathematics,Computer Science - Formal Languages and Automata Theory,Computer Science - Logic in Computer Science,F.1.1,F.4.3,F.1.3