Thue systems as rewriting systems (Q1099642)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 4041317
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Thue systems as rewriting systems |
scientific article; zbMATH DE number 4041317 |
Statements
Thue systems as rewriting systems (English)
0 references
1987
0 references
The paper is a survey of recent results on Thue systems that have been obtained in the last ten years. The emphasis is on Thue systems with the Church-Rosser property and the main effort is expended in outlining the properties of such systems and the monoids they present. Of special concern are the results that describe the inherent computational complexity of problems that arise in this area. The language of monoids (and groups) is used to describe some of these properties. This survey would be of interest for computer scientists as well as for logicians interested in computability theory.
0 references
replacement systems
0 references
term rewriting systems
0 references
decidability
0 references
survey
0 references
Thue systems
0 references
computational complexity
0 references
0 references
0 references
0 references
0.8315839171409607
0 references
0.830000102519989
0 references
0.8261566758155823
0 references
