Decidable sentences of Church-Rosser congruences

DOI10.1016/0304-3975(83)90005-1zbMath0525.68015OpenAlexW1988565881MaRDI QIDQ593775

Ronald V. Book

Publication date: 1983

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(83)90005-1

zbMATH Keywords

monoiddecision procedureChurch-Rosser propertylinear termsmonadic systempositive sentencesThue system

Mathematics Subject Classification ID

Abstract data types; algebraic specification (68Q65) Decidability of theories and sets of sentences (03B25) Semigroups in automata theory, linguistics, etc. (20M35) Thue and Post systems, etc. (03D03)

Related Items

Computing presentations for subgroups of polycyclic groups and of context-free groups ⋮ DECISION AND SEPARABILITY PROBLEMS FOR BAUMSLAG–SOLITAR SEMIGROUPS ⋮ Codes modulo finite monadic string-rewriting systems ⋮ Thue systems as rewriting systems ⋮ Unnamed Item ⋮ The problem of deciding confluence on a given congruence class is tractable for finite special string-rewriting systems ⋮ An efficient algorithm to decide whether a monoid presented by a regular Church-Rosser Thue system is a group ⋮ Some polynomial-time algorithms for finite monadic Church-Rosser Thue systems ⋮ On the rational subsets of the free group ⋮ Equational unification, word unification, and 2nd-order equational unification ⋮ Deciding the NTS property of context-free grammars ⋮ About the descriptive power of certain classes of finite string-rewriting systems ⋮ Decision problems for finite special string-rewriting systems that are confluent on some congruence class ⋮ Commutativity in groups presented by finite Church-Rosser Thue systems ⋮ Church-Rosser systems with respect to formal languages ⋮ When is an extension of a specification consistent? Decidable and undecidable cases ⋮ Solvability of word equations modulo finite special and confluent string-rewriting systems is undecidable in general ⋮ Completing a finite special string-rewriting system on the congruence class of the empty word ⋮ Elements of Finite Order for Finite Monadic Church-Rosser Thue Systems ⋮ A decision algorithm for linear sentences on a PFM ⋮ On weakly confluent monadic string-rewriting systems ⋮ Cancellation rules and extended word problems ⋮ Contributions of Ronald V. Book to the theory of string-rewriting systems ⋮ Cancellativity in finitely presented semigroups ⋮ Some undecidability results for non-monadic Church-Rosser Thue systems ⋮ Conjugacy in monoids with a special Church-Rosser presentation is decidable ⋮ On two problems related to cancellativity ⋮ Complexity results on the conjugacy problem for monoids ⋮ Pseudo-natural algorithms for the word problem for finitely presented monoids and groups ⋮ On deciding whether a monoid is a free monoid or is a group

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computing in systems described by equations
• Testing for the Church-Rosser property
• Monadic Thue systems
• When is a monoid a group? The Church-Rosser case is tractable
• On the equivalence, containment, and covering problems for the regular and context-free languages
• Infinite regular Thue systems
• Une généralisation des ensembles de Dyck
• Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
• Confluent and Other Types of Thue Systems
• Tree-Manipulating Systems and Church-Rosser Theorems