On the Computational Complexity of Algebra on Lattices

DOI10.1137/0216011zbMath0642.06005OpenAlexW2032278512MaRDI QIDQ3783337

Peter A. Bloniarz, Daniel J. Rosenkrantz, Harry B. III Hunt

Publication date: 1987

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0216011

zbMATH Keywords

distributive latticespolynomial timefinite latticefree latticeformula minimizationco-NP hardconstant-free expressions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Logical aspects of lattices and related structures (03G10) Free lattices, projective lattices, word problems (06B25) Distributive lattices (06D99)

Related Items (9)

From distributive \(\ell\)-monoids to \(\ell\)-groups, and back again ⋮ Proof theory for lattice-ordered groups ⋮ Computers and universal algebra: Some directions ⋮ The word and generator problems for lattices ⋮ Generic expression hardness results for primitive positive formula comparison ⋮ Resolution-based decision procedures for the universal theory of some classes of distributive lattices with operators ⋮ Partition semantics for relations ⋮ Free lattice algorithms ⋮ On the complexity of equational decision problems for finite height complemented and orthocomplemented modular lattices

This page was built for publication: On the Computational Complexity of Algebra on Lattices