"Extending Semilattices Is Hard" by George Markowsky

Selected Works of George Markowsky

Follow Contact

Article

Extending Semilattices Is Hard

Algebra Universalis

George Markowsky, Missouri University of Science and Technology

Link

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.

Department(s)

Computer Science

Document Type

Article - Journal

Document Version

Citation

File Type

text

Language(s)

English

Rights

Publication Date

12-1-1983

Publication Date

01 Dec 1983

Disciplines

Computer Sciences

Citation Information

George Markowsky. "Extending Semilattices Is Hard" Algebra Universalis Vol. 17 Iss. 1 (1983) p. 406 - 407 ISSN: 0002-5240
Available at: http://works.bepress.com/george-markowsky/28/