Search

• < Previous
• 1
• 2
• Next >

Tameness and the power of programs over monoids in DA

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&nbsp;[&hellip;]