Church-Rosser controlled rewriting systems and equivalence problems for deterministic context-free languages (Q1120292): Difference between revisions

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.