LATPub142: Unterschied zwischen den Versionen
Aus International Center for Computational Logic
Marcel Lippmann (Diskussion | Beiträge) KKeine Bearbeitungszusammenfassung |
Marcel Lippmann (Diskussion | Beiträge) KKeine Bearbeitungszusammenfassung |
||
| (2 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt) | |||
| Zeile 1: | Zeile 1: | ||
{{Publikation Erster Autor | {{Publikation Erster Autor | ||
|ErsterAutorVorname= | |ErsterAutorVorname=Franz | ||
|ErsterAutorNachname=Baader | |ErsterAutorNachname=Baader | ||
|FurtherAuthors= | |FurtherAuthors= | ||
| Zeile 6: | Zeile 6: | ||
{{Article | {{Article | ||
|Referiert=1 | |Referiert=1 | ||
|Title=On the Complexity of | |Title=On the Complexity of Boolean Unification | ||
|Year=1998 | |Year=1998 | ||
|Month= | |Month= | ||
| Zeile 12: | Zeile 12: | ||
|Note= | |Note= | ||
|Number=4 | |Number=4 | ||
|Pages=215 | |Pages=215-220 | ||
|Publisher= | |Publisher= | ||
|Volume=67 | |Volume=67 | ||
| Zeile 18: | Zeile 18: | ||
}} | }} | ||
{{Publikation Details | {{Publikation Details | ||
|Abstract=Unification modulo the theory of Boolean algebras has been investigated | |Abstract=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 $Pi^p_2$-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. | ||
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 | |||
$ | |||
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. | |||
|ISBN= | |ISBN= | ||
|ISSN= | |ISSN= | ||
| Zeile 46: | Zeile 36: | ||
year = {1998}, | year = {1998}, | ||
} | } | ||
}} | }} | ||
Aktuelle Version vom 25. März 2015, 16:34 Uhr
On the Complexity of Boolean Unification
Franz BaaderFranz Baader
Franz Baader
On the Complexity of Boolean Unification
Information Processing Letters, 67(4):215-220, 1998
On the Complexity of Boolean Unification
Information Processing Letters, 67(4):215-220, 1998
- KurzfassungAbstract
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 $Pi^p_2$-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. - Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory
@article{ Baader-IPL-98,
author = {F. {Baader}},
journal = {Information Processing Letters},
number = {4},
pages = {215--220},
title = {On the Complexity of {B}oolean Unification},
volume = {67},
year = {1998},
}
