On the Computational Complexity of Algebra on Lattices
From MaRDI portal
Publication:3783337
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
distributive latticespolynomial timefinite latticefree latticeformula minimizationco-NP hardconstant-free expressions
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