Decidable sentences of Church-Rosser congruences
From MaRDI portal
Publication:593775
DOI10.1016/0304-3975(83)90005-1zbMath0525.68015MaRDI QIDQ593775
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
monoid; decision procedure; Church-Rosser property; linear terms; monadic system; positive sentences; Thue system
68Q65: Abstract data types; algebraic specification
03B25: Decidability of theories and sets of sentences
20M35: Semigroups in automata theory, linguistics, etc.
03D03: Thue and Post systems, etc.
Related Items
DECISION AND SEPARABILITY PROBLEMS FOR BAUMSLAG–SOLITAR SEMIGROUPS, Solvability of word equations modulo finite special and confluent string-rewriting systems is undecidable in general, A decision algorithm for linear sentences on a PFM, On weakly confluent monadic string-rewriting systems, Conjugacy in monoids with a special Church-Rosser presentation is decidable, 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, Some undecidability results for non-monadic Church-Rosser Thue systems, 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, Thue systems as 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, Equational unification, word unification, and 2nd-order equational unification, When is an extension of a specification consistent? Decidable and undecidable cases, Completing a finite special string-rewriting system on the congruence class of the empty word, Contributions of Ronald V. Book to the theory of string-rewriting systems, Computing presentations for subgroups of polycyclic groups and of context-free groups, Codes modulo finite monadic string-rewriting systems, Cancellativity in finitely presented semigroups, On the rational subsets of the free group, Cancellation rules and extended word problems, Unnamed Item, Commutativity in groups presented by finite Church-Rosser Thue systems, Church-Rosser systems with respect to formal languages, Elements of Finite Order for Finite Monadic Church-Rosser Thue Systems, The problem of deciding confluence on a given congruence class is tractable for finite special string-rewriting systems
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
