Church-Rosser systems with respect to formal languages

DOI10.1007/BF01074918zbMath0651.68101OpenAlexW1982879402MaRDI QIDQ3796797

Volodymyr Oleshchuk, Anatoly V. Anisimov

Publication date: 1987

Published in: Cybernetics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01074918

zbMATH Keywords

decidabilityrewriting systemsThue systemsChurch-Rosser propertyequivalence problems

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Free semigroups, generators and relations, word problems (20M05) Undecidability and degrees of sets of sentences (03D35) Word problems, etc. in computability and recursion theory (03D40) Thue and Post systems, etc. (03D03) Word problems (aspects of algebraic structures) (08A50)

Cites Work

• Unnamed Item
• Decidable sentences of Church-Rosser congruences
• Testing for the Church-Rosser property
• Monadic Thue systems
• Infinite regular Thue systems
• On theories with a combinatorial definition of 'equivalence'
• Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
• Confluent and Other Types of Thue Systems
• Testing for the Church-Rosser Property
• Recursive Unsolvability of a problem of Thue
• Tree-Manipulating Systems and Church-Rosser Theorems

This page was built for publication: Church-Rosser systems with respect to formal languages