Algebraic Structures with Hard Equivalence and Minimization Problems

DOI10.1145/1634.1639MaRDI QIDQ3765245zbMATH OpenOpenAlexFDO

Authors Peter A. Bloniarz, H. B. III Hunt, Daniel J. Rosenkrantz

Publication date 1984

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1634.1639

zbMATH Keywords

algebraic structuresminimization of algebraic expressionsrewriting systems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30)

Recommendations

• scientific article; zbMATH DE number 3960994
• Strongly-local reductions and the complexity/efficient approximability of algebra and optimization on abstract algebraic structures
• On the Computational Complexity of Algebra on Lattices
• scientific article; zbMATH DE number 4114007
• Computational complexity of some problems involving congruences on algebras

Cited in

(17)

• The word and generator problems for lattices
• Solution of Rota's problem on the order of series-parallel networks
• A linear time equivalence test for read-twice DNF formulas
• Complexity of some language fragments of fuzzy logics
• Computers and universal algebra: Some directions
• Minimization and equivalence in multi-valued logical models of regulatory networks
• Nonfinitely based ai-semirings with finitely based semigroup reducts
• The finite embeddability property for residuated groupoids.
• Complexity and approximability of quantified and stochastic constraint satisfaction problems
• Strongly-local reductions and the complexity/efficient approximability of algebra and optimization on abstract algebraic structures
• On the Computational Complexity of Algebra on Lattices
• Logics and algebras for multiple players
• On the complexity of dataflow analysis of logic programs
• Partition semantics for relations
• The complexity of equivalence for commutative rings
• Optimizing the region algebra is PSPACE-complete
• Extending semilattices is hard

This page was built for publication: Algebraic Structures with Hard Equivalence and Minimization Problems

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