Constructive universal algebra: An introduction

DOI10.1016/0304-3975(87)90057-0MaRDI QIDQ579289zbMATH OpenOpenAlexFDO

Authors Edouard G. Belaga

Publication date 1987

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(87)90057-0

zbMATH Keywords

complexity of algebraic operationspartial universal algebra

Mathematics Subject Classification ID

Operations and polynomials in algebraic structures, primal algebras (08A40) Partial algebras (08A55) Analysis of algorithms and problem complexity (68Q25)

Review text

The author surveys his approach to the question of complexity of algebraic operations. Having a partial universal algebra (A,\(\Omega)\) and a partial algebraic operation f of (A,\(\Omega)\), a lower bound for the complexity of an optimal expression of f by \(\Omega\)-operations is presented.

Recommendations

• Computers and universal algebra: Some directions
• Algebraic complexity theory. I: An introduction
• scientific article; zbMATH DE number 3880117
• scientific article; zbMATH DE number 1304317
• Complexity of Some Problems Concerning Varieties and Quasi-Varieties of Algebras

Cites work

• Boolean functions whose monotone complexity is of size \(n^ 2\) / log n
• Dimension, superposition of functions and separation of points, in compact metric spaces
• scientific article; zbMATH DE number 3887074 (Why is no real title available?)
• scientific article; zbMATH DE number 3896264 (Why is no real title available?)
• scientific article; zbMATH DE number 3913670 (Why is no real title available?)
• scientific article; zbMATH DE number 3934403 (Why is no real title available?)
• scientific article; zbMATH DE number 3988701 (Why is no real title available?)
• scientific article; zbMATH DE number 4078799 (Why is no real title available?)
• scientific article; zbMATH DE number 3758268 (Why is no real title available?)
• scientific article; zbMATH DE number 3607492 (Why is no real title available?)
• scientific article; zbMATH DE number 3639689 (Why is no real title available?)
• Lower Bounds on Synchronous Combinational Complexity

Cited in

(7)

• Bilinear mincing rank
• A course in constructive algebra
• Algebraic dependences and reducibilities of constructivizations in universal domains
• scientific article; zbMATH DE number 3887074 (Why is no real title available?)
• scientific article; zbMATH DE number 7217919 (Why is no real title available?)
• scientific article; zbMATH DE number 3880117 (Why is no real title available?)
• scientific article; zbMATH DE number 5298331 (Why is no real title available?)

This page was built for publication: Constructive universal algebra: An introduction

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