Kaoutar El Maghraoui, Gokul Kandiraju, et al.
WOSP/SIPEW 2010
We present polynomial-time algorithms for the uniform word problem and for the generator problem for lattices. The algorithms are derived from novel, prooftheoretic approaches. We prove that both problems are log-space complete for P, but can be solved in deterministic logarithmic space in the case of free lattices. We also show that the more general problem of testing whether a given open sentence is true in all lattices is co-NP complete. © 1988.
Kaoutar El Maghraoui, Gokul Kandiraju, et al.
WOSP/SIPEW 2010
Yigal Hoffner, Simon Field, et al.
EDOC 2004
Elliot Linzer, M. Vetterli
Computing
Charles H. Bennett, Aram W. Harrow, et al.
IEEE Trans. Inf. Theory