Simple LPO constraint solving methods
In: Information Processing Letters, Jg. 47 (1993-08-01), S. 65-69
Online
unknown
Zugriff:
We present simple techniques for deciding the satisfiability of lexicographic path ordering constraints under two different semantics: solutions built over the given signature and solutions in extended signatures. For both cases we give the first NP algorithms, which is optimal as we prove the problems to be NP-complete. We discuss the efficient applicability of the techniques in practice, where, as far as we know, their simply exponential bound improves upon the existing methods, and describe some optimizations.
Titel: |
Simple LPO constraint solving methods
|
---|---|
Autor/in / Beteiligte Person: | Nieuwenhuis, Robert |
Link: | |
Zeitschrift: | Information Processing Letters, Jg. 47 (1993-08-01), S. 65-69 |
Veröffentlichung: | Elsevier BV, 1993 |
Medientyp: | unknown |
ISSN: | 0020-0190 (print) |
DOI: | 10.1016/0020-0190(93)90226-y |
Schlagwort: |
|
Sonstiges: |
|