scientific article; zbMATH DE number 7577578

MaRDI QIDQ5101347

Luc Segoufin, Pierre McKenzie, Nathan Grosshans

Publication date: 30 August 2022

Full work available at URL: https://arxiv.org/abs/2101.07495

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

lower boundtamenessprograms over monoids\(\mathbf{DA}\)

Mathematics Subject Classification ID

Logic in computer science (03B70) Computer science (68-XX)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• The power of programs over monoids in \textbf{J}
• \(\Sigma_ 1^ 1\)-formulae on finite structures
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• The Birkhoff theorem for finite algebras
• Regular languages in \(NC\)
• Finite semigroup varieties defined by programs
• Languages defined with modular counting quantifiers
• 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
• An Algebraic Point of View on the Crane Beach Property
• Finite monoids and the fine structure of NC ¹
• Some results onC-varieties
• A SYNTACTICAL PROOF OF LOCALITY OF DA
• The Power of Programs over Monoids in DA
• A Property of Finite Simple Non-Abelian Groups

This page was built for publication: