The Power of Programs over Monoids in DA

DOI10.4230/LIPICS.MFCS.2017.2zbMATH Open1440.68088arXiv2101.07495OpenAlexW2773184040MaRDI QIDQ5111216FDOQ5111216

Luc Segoufin, Pierre McKenzie, Nathan Grosshans

Publication date: 26 May 2020

Abstract: The program-over-monoid model of computation originates with Barrington's proof that the model captures the complexity class $mathsfN{C}^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 $mathbfDA$ satisfies tameness and hence that the regular languages recognized by programs over monoids in $mathbfDA$ are precisely those recognizable in the classical sense by morphisms from $mathbfQDA$. Third, we show by contrast that the well studied class of monoids called $mathbfJ$ is not tame. Finally, we exhibit a program-length-based hierarchy within the class of languages recognized by programs over monoids from $mathbfDA$.

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) Other nonclassical models of computation (68Q09) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• Parity, circuits, and the polynomial-time hierarchy
• Non-uniform automata over groups
• Programs over semigroups of dot-depth one
• On varieties of rational languages and variable length codes. II
• Finite monoids and the fine structure of NC ¹
• Categories as algebra: An essential ingredient in the theory of monoids
• A Property of Finite Simple Non-Abelian Groups
• The Birkhoff theorem for finite algebras
• Algebraic Theory of Machines. I. Prime Decomposition Theorem for Finite Semigroups and Machines
• \(NC^ 1\): The automata-theoretic viewpoint
• Some results onC-varieties
• Finite semigroup varieties defined by programs
• Actions, wreath products of \(\mathcal C\)-varieties and concatenation product.
• Two-variable first order logic with modular predicates over words

Cited In (7)

• Title not available (Why is that?)
• On the computational power of programs over \(\mathsf{BA}_2\) monoid
• Locality and Centrality: The Variety ZG
• Extensions to Barrington's M-program model
• Title not available (Why is that?)
• Title not available (Why is that?)
• The regular languages of first-order logic with one alternation

This page was built for publication: The Power of Programs over Monoids in DA

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111216)