- Titel
- On the Complexity of Boolean Unification
- Zitierfähige Url:
- https://nbn-resolving.org/urn:nbn:de:bsz:14-qucosa2-788114
- Schriftenreihe
- LTCS-Report
- Bandnummer
- 97-03
- Erstveröffentlichung
- 1997
- DOI
- https://doi.org/10.25368/2022.74
- Abstract (EN)
- Unification modulo the theory of Boolean algebras has been investigated by several autors. Nevertheless, the exact complexity of the decision problem for unification with constants and general unification was not known. In this research note, we show that the decision problem is complete for unification with constants and PSPACE-complete for general unification. In contrast, the decision problem for elementary unification (where the terms to be unified contain only symbols of the signature of Boolean algebras) is 'only' NP-complete.
- Freie Schlagwörter (DE)
- Boolesche Algebra, PSPACE-komplett, Vereinheitlichung
- Freie Schlagwörter (EN)
- Boolean algebras, PSPACE-complete, unification
- Klassifikation (DDC)
- 004
- Klassifikation (RVK)
- ST 136
- Publizierende Institution
- Aachen University of Technology, Aachen
- Version / Begutachtungsstatus
- angenommene Version / Postprint / Autorenversion
- URN Qucosa
- urn:nbn:de:bsz:14-qucosa2-788114
- Veröffentlichungsdatum Qucosa
- 19.05.2022
- Dokumenttyp
- Bericht
- Sprache des Dokumentes
- Englisch
- Lizenz / Rechtehinweis
CC BY 4.0