The undecidability of self-embedding for term rewriting systems (Q1061484): Difference between revisions

From MaRDI portal
Added link to MaRDI item.
RedirectionBot (talk | contribs)
Removed claim: author (P16): Item:Q1238600
Property / author
 
Property / author: David Alan Plaisted / rank
Normal rank
 

Revision as of 21:15, 22 February 2024

scientific article
Language Label Description Also known as
English
The undecidability of self-embedding for term rewriting systems
scientific article

    Statements

    The undecidability of self-embedding for term rewriting systems (English)
    0 references
    1985
    0 references
    The self-embedding property of term rewriting systems is closely related to the uniform termination property, since a nonself-embedding term rewriting system is uniform terminating. The self-embedding property is shown to be undecidable and partially decidable. It follows that the nonself-embedding property is not partially decidable. This is true even for globally finite term rewriting systems. The same construction gives an easy alternate proof that uniform termination is undecidable in general and also for globally finite term rewriting systems. Also, the looping property is shown to be undecidable in the same way.
    0 references
    termination
    0 references
    looping property
    0 references

    Identifiers