The Power of Programs over Monoids in DA
From MaRDI portal
Publication:5111216
DOI10.4230/LIPIcs.MFCS.2017.2zbMath1440.68088arXiv2101.07495OpenAlexW2773184040MaRDI QIDQ5111216
Luc Segoufin, Pierre McKenzie, Nathan Grosshans
Publication date: 26 May 2020
Full work available at URL: https://arxiv.org/abs/2101.07495
Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Other nonclassical models of computation (68Q09)
Related Items (4)
Unnamed Item ⋮ Locality and Centrality: The Variety ZG ⋮ On the computational power of programs over \(\mathsf{BA}_2\) monoid ⋮ Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Categories as algebra: An essential ingredient in the theory of monoids
- \(NC^ 1\): The automata-theoretic viewpoint
- Non-uniform automata over groups
- On varieties of rational languages and variable length codes. II
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- The Birkhoff theorem for finite algebras
- Finite semigroup varieties defined by programs
- Programs over semigroups of dot-depth one
- Actions, wreath products of \(\mathcal C\)-varieties and concatenation product.
- Two-variable first order logic with modular predicates over words
- Parity, circuits, and the polynomial-time hierarchy
- Finite monoids and the fine structure of NC 1
- Some results onC-varieties
- A Property of Finite Simple Non-Abelian Groups
- Algebraic Theory of Machines. I. Prime Decomposition Theorem for Finite Semigroups and Machines
This page was built for publication: The Power of Programs over Monoids in DA