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

From MaRDI portal
Added link to MaRDI item.
ReferenceBot (talk | contribs)
Changed an Item
 
(4 intermediate revisions by 3 users not shown)
Property / author
 
Property / author: David Alan Plaisted / rank
Normal rank
 
Property / author
 
Property / author: David Alan Plaisted / rank
 
Normal rank
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank
Property / full work available at URL
 
Property / full work available at URL: https://doi.org/10.1016/0020-0190(85)90063-8 / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W2001610338 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Orderings for term-rewriting systems / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3862379 / rank
 
Normal rank

Latest revision as of 17:30, 14 June 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