Confluent and Other Types of Thue Systems
From MaRDI portal
Publication:3936184
DOI10.1145/322290.322301zbMath0478.68032OpenAlexW2062170505MaRDI QIDQ3936184
Publication date: 1982
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/322290.322301
word problemsChurch-Rosser systemdeterministic context-free languageThue congruenceconfluent systemspreperfect system
Formal languages and automata (68Q45) Abstract data types; algebraic specification (68Q65) Decidability of theories and sets of sentences (03B25) Word problems, etc. in computability and recursion theory (03D40) Thue and Post systems, etc. (03D03)
Related Items (95)
On sufficient-completeness and related properties of term rewriting systems ⋮ THE PROPERTY FDT IS UNDECIDABLE FOR FINITELY PRESENTED MONOIDS THAT HAVE POLYNOMIAL-TIME DECIDABLE WORD PROBLEMS ⋮ Reductions in tree replacement systems ⋮ Bounded degree graph inference from walks ⋮ The equivalence and inclusion problems for NTS languages ⋮ n-level rewriting systems ⋮ Complexity of certain decision problems about congruential languages ⋮ On the regular equivalence problem for regular Thue systems ⋮ Special monoids and special Thue systems ⋮ Rational strong codes and structure of rational group languages ⋮ Codes modulo finite monadic string-rewriting systems ⋮ Monoids with disjunctive identity and their codes ⋮ Decidability and independence of conjugacy problems in finitely presented monoids ⋮ Decidability of confluence and termination of monadic term rewriting systems ⋮ Efficient rewriting in cograph trace monoids ⋮ A shorter proof that palindromes are not a Church-Rosser language, with extensions to almost-confluent and preperfect Thue systems ⋮ A catalogue of complete group presentations ⋮ On reduced thue systems ⋮ Thue systems as rewriting systems ⋮ Security analysis of word problem-based cryptosystems ⋮ Rewriting systems and word problems in a free partially commutative monoid ⋮ On deciding the confluence of a finite string-rewriting system on a given congruence class ⋮ History and basic features of the critical-pair/completion procedure ⋮ Sufficient-completeness, ground-reducibility and their complexity ⋮ Complexity, combinatorial group theory and the language of palutators ⋮ Inverse monoids: decidability and complexity of algebraic questions. ⋮ Preperfectness is undecidable for Thue systems containing only length- reducing rules and a single commutation rule ⋮ The word problem for free partially commutative groups ⋮ A note on thue systems with a single defining relation ⋮ On the word problem for special monoids ⋮ Decidable sentences of Church-Rosser congruences ⋮ Deterministic tree pushdown automata and monadic tree rewriting systems ⋮ 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 confluence of one-rule trace-rewriting systems ⋮ Growing context-sensitive languages and Church-Rosser languages ⋮ Decision problems for cellular automata and their semigroups ⋮ On public-key cryptosystem based on Church-Rosser string-rewriting systems ⋮ Undecidable properties of monoids with word problem solvable in linear time. II: Cross sections and homological and homotopical finiteness conditions. ⋮ A note on confluent Thue systems ⋮ Confluence of one-rule Thue systems ⋮ The context-splittable normal form for Church-Rosser language systems. ⋮ The Knuth-Bendix algorithm and the conjugacy problem in monoids. ⋮ Finite canonical rewriting systems for congruences generated by concurrency relations ⋮ On the word problem for free products of semigroups and monoids ⋮ Church-Rosser codes ⋮ 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 ⋮ NTS grammars and Church-Rosser systems ⋮ On ground-confluence of term rewriting systems ⋮ Word problems over traces which are solvable in linear time ⋮ Testing for the Church-Rosser property ⋮ Thue congruences and the Church-Rosser property ⋮ On a special monoid with a single defining relation ⋮ A complete rewriting system for a monoid of tree transformation classes ⋮ Monadic Thue systems ⋮ Commutativity in groups presented by finite Church-Rosser Thue systems ⋮ When is a monoid a group? The Church-Rosser case is tractable ⋮ Church-Rosser systems with respect to formal languages ⋮ When is an extension of a specification consistent? Decidable and undecidable cases ⋮ Gilman's conjecture ⋮ Elements of Finite Order for Finite Monadic Church-Rosser Thue Systems ⋮ On weakly confluent monadic string-rewriting systems ⋮ Partially commutative inverse monoids. ⋮ Calcul de longueurs de chaînes de réécriture dans le monoïde libre ⋮ The Church-Rosser languages are the deterministic variants of the growing context-sensitive languages ⋮ Groups Presented by Finite Two-Monadic Church-Rosser Thue Systems ⋮ Using string-rewriting for solving the word problem for finitely presented groups ⋮ DECIDABILITY AND COMPLEXITY IN AUTOMATIC MONOIDS ⋮ Infinite periodic points of endomorphisms over special confluent rewriting systems ⋮ On the Knuth-Bendix completion for concurrent processes ⋮ Word problems over traces which are solvable in linear time ⋮ Contributions of Ronald V. Book to the theory of string-rewriting systems ⋮ Finite complete rewriting systems for the Jantzen monoid and the Greendlinger group ⋮ LOGICAL ASPECTS OF CAYLEY-GRAPHS: THE MONOID CASE ⋮ Reductions and functors from problems to word problems ⋮ Cancellativity in finitely presented semigroups ⋮ A note on special thue systems with a single defining relation ⋮ Infinite regular Thue systems ⋮ Undecidable questions related to Church-Rosser Thue systems ⋮ Finite complete rewriting systems and the complexity of word problem ⋮ Remarks on an example of Jantzen ⋮ Homomorphic images of sentential form languages defined by semi-Thue systems ⋮ An \(O(| T| ^ 3)\) algorithm for testing the Church-Rosser property of Thue systems ⋮ Some undecidability results for non-monadic Church-Rosser Thue systems ⋮ Almost all one-rule Thue systems have decidable word problems ⋮ Insertion languages ⋮ The undecidability of the preperfectness of Thue systems ⋮ Homogeneous Thue systems and the Church-Rosser property ⋮ 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 ⋮ A finite Thue system with decidable word problem and without equivalent finite canonical system ⋮ Pseudo-natural algorithms for the word problem for finitely presented monoids and groups
This page was built for publication: Confluent and Other Types of Thue Systems
