Thue trees (Q1861534)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Thue trees |
scientific article |
Statements
Thue trees (English)
0 references
9 March 2003
0 references
A new technique is introduced to prove undecidability results. This technique is based on the notion of a Thue tree. Also, examples are given how to apply this method to term rewriting, the Horn implication problem, and data dependencies. The strategy of proving undecidability results adapted in this paper is to reduce the problem of existence of a finite Thue tree to the problem under consideration.
0 references
undecidability
0 references
Thue systems
0 references
Horn clause implication
0 references
one-step rewriting
0 references
