The power of programs over monoids in DA

DOI10.4230/LIPICS.MFCS.2017.2MaRDI QIDQ5111216zbMATH OpenOpenAlexFDO

Authors Nathan Grosshans, Pierre McKenzie, Luc Segoufin

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

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$.

Recommendations

• The power of programs over monoids in \textbf{J}
• scientific article; zbMATH DE number 1916674
• Programs over aperiodic monoids
• Extensions to Barrington's M-program model
• \(NC^ 1\): The automata-theoretic viewpoint

Cites work

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

Cited in

(10)

• Programs over aperiodic monoids
• scientific article; zbMATH DE number 7577578 (Why is no real title available?)
• On the computational power of programs over \(\mathsf{BA}_2\) monoid
• Locality and Centrality: The Variety ZG
• Extensions to Barrington's M-program model
• scientific article; zbMATH DE number 7350780 (Why is no real title available?)
• scientific article; zbMATH DE number 17309 (Why is no real title available?)
• The regular languages of first-order logic with one alternation
• The power of programs over monoids in \textbf{J}
• scientific article; zbMATH DE number 1916674 (Why is no real title available?)

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)