Please use this identifier to cite or link to this item:
doi:10.22028/D291-24881 | Title: | The first-order theory of lexicographic path orderings is undecidable |
| Author(s): | Comon, Hubert Treinen, Ralf |
| Language: | English |
| Year of Publication: | 1993 |
| OPUS Source: | Kaiserslautern ; Saarbrücken : DFKI, 1993 |
| SWD key words: | Künstliche Intelligenz |
| DDC notations: | 004 Computer science, internet |
| Publikation type: | Report |
| Abstract: | We show, under some assumption on the signature, that the *This formula not viewable on a Text-Browser* fragment of the theory of any lexicographic path ordering is undecidable. This applies to partial and to total precedences. Our result implies in particular that the simplification rule of ordered completion is undecidable. |
| Link to this record: | urn:nbn:de:bsz:291-scidok-36379 hdl:20.500.11880/24937 http://dx.doi.org/10.22028/D291-24881 |
| Series name: | Research report / Deutsches Forschungszentrum für Künstliche Intelligenz [ISSN 0946-008x] |
| Series volume: | 93-42 |
| Date of registration: | 24-Jun-2011 |
| Faculty: | SE - Sonstige Einrichtungen |
| Department: | SE - DFKI Deutsches Forschungszentrum für Künstliche Intelligenz |
| Collections: | SciDok - Der Wissenschaftsserver der Universität des Saarlandes |
Files for this record:
| File | Description | Size | Format | |
|---|---|---|---|---|
| RR_93_42.pdf | 10,25 MB | Adobe PDF | View/Open |
Items in SciDok are protected by copyright, with all rights reserved, unless otherwise indicated.