Testing for a Semilattice Term
| Autor: | Matthew Valeriote, James B. Nation, Ralph Freese |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Pure mathematics
Algebra and Number Theory Series (mathematics) Computational complexity theory 010102 general mathematics Contrast (statistics) Semilattice 0102 computer and information sciences Term (logic) Decision problem 01 natural sciences Computational Theory and Mathematics 010201 computation theory & mathematics ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION Idempotence Geometry and Topology 0101 mathematics Algebra over a field Mathematics |
| Zdroj: | Order. 36:65-76 |
| ISSN: | 1572-9273 0167-8094 |
| Popis: | This paper investigates the computational complexity of deciding if a given finite algebra is an expansion of a semilattice. In general this problem is known to be EXP-TIME complete, and we show that even for idempotent algebras, this problem remains hard. This result is in contrast to a series of results that show that similar decision problems turn out to be tractable. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink