Extending Semilattices Is Hard

Author

George Markowsky, Missouri University of Science and TechnologyFollow

Abstract

We show that the semilattice extension problem raised by Arbib and Manes in [2] is NP-hard, implying that no simple solution is likely to be forthcoming.

Recommended Citation

G. Markowsky, "Extending Semilattices Is Hard," Algebra Universalis, vol. 17, no. 1, pp. 406 - 407, Springer Verlag, Dec 1983.

The definitive version is available at https://doi.org/10.1007/BF01194547

Department(s)

Computer Science

International Standard Serial Number (ISSN)

0002-5240

Document Type

Article - Journal

Document Version

Citation

File Type

text

Language(s)

English

Rights

© 1983 Springer Verlag, All rights reserved.

Publication Date

01 Dec 1983