The Power of Programs over Monoids in DA

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

zbMATH Keywords

DAlower boundsprograms over monoids

Mathematics Subject Classification ID

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 ¹
• 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