Church-Rosser controlled rewriting systems and equivalence problems for deterministic context-free languages (Q1120292)
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: Church-Rosser controlled rewriting systems and equivalence problems for deterministic context-free languages |
scientific article; zbMATH DE number 4100628
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Church-Rosser controlled rewriting systems and equivalence problems for deterministic context-free languages |
scientific article; zbMATH DE number 4100628 |
Statements
Church-Rosser controlled rewriting systems and equivalence problems for deterministic context-free languages (English)
0 references
1989
0 references
Controlled rewriting systems having the Church-Rosser property define a class CR of formal languages as congruence classes which strictly contain the family of deterministic context-free languages D. NTS-grammars define a subclass of D and in this work it is shown that the famous equivalence problem for languages from the classes NTS and CR is decidable, thereby generalizing a number of known cases of this equivalence problem for deterministic context-free languages.
0 references
NTS-languages
0 references
Controlled rewriting
0 references
Church-Rosser property
0 references
deterministic context-free languages
0 references
0 references
0 references
0.88304883
0 references
0 references
0 references
0.8717264
0 references
0.8693777
0 references
0.86787534
0 references
