Undecidable properties of flat term rewrite systems (Q734041)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Undecidable properties of flat term rewrite systems |
scientific article; zbMATH DE number 5617928
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Undecidable properties of flat term rewrite systems |
scientific article; zbMATH DE number 5617928 |
Statements
Undecidable properties of flat term rewrite systems (English)
0 references
19 October 2009
0 references
Reachability, joinability, termination or strong normalization, confluence, weak normalization, and unique normalization are some fundamental properties of term rewrite systems (TRS) that are known to be undecidable in general. Their decidablity has been investigated for some particular classes. In this paper, the authors give new simple proofs for the undecidability of reachability, joinability, and confluence for flat TRS. They also give proofs for the undecidability of weak and unique normalizations for flat TRS.
0 references
term rewriting
0 references
syntactic restrictions
0 references
undecidability
0 references
0 references
0.9186991
0 references
0.8944309
0 references
0.8823967
0 references
0.8787419
0 references
0.8704542
0 references
0.8682181
0 references
