Confluent and Other Types of Thue Systems
From MaRDI portal
Cited in
(96)- Infinite periodic points of endomorphisms over special confluent rewriting 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
- 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
- On sufficient-completeness and related properties of term rewriting systems
- Reductions in tree replacement systems
- 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
- Monoids with disjunctive identity and their codes
- A catalogue of complete group presentations
- Thue systems as rewriting systems
- 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
- Complexity, combinatorial group theory and the language of palutators
- Preperfectness is undecidable for Thue systems containing only length- reducing rules and a single commutation rule
- The word problem for free partially commutative groups
- Deterministic tree pushdown automata and monadic tree 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
- NTS grammars and Church-Rosser systems
- Testing for the Church-Rosser property
- Thue congruences and the Church-Rosser property
- On a special monoid with a single defining relation
- Monadic Thue systems
- When is a monoid a group? The Church-Rosser case is tractable
- When is an extension of a specification consistent? Decidable and undecidable cases
- On the Knuth-Bendix completion for concurrent processes
- Contributions of Ronald V. Book to the theory of string-rewriting systems
- Bounded degree graph inference from walks
- Codes modulo finite monadic string-rewriting systems
- Growing context-sensitive languages and Church-Rosser languages
- Undecidable properties of monoids with word problem solvable in linear time. II: Cross sections and homological and homotopical finiteness conditions.
- The context-splittable normal form for Church-Rosser language systems.
- Reductions and functors from problems to word problems
- Decidability and independence of conjugacy problems in finitely presented monoids
- The Church-Rosser languages are the deterministic variants of the growing context-sensitive languages
- Cancellativity in finitely presented semigroups
- Infinite regular Thue systems
- Undecidable questions related to Church-Rosser Thue systems
- Gilman's conjecture
- On the word problem for special monoids
- Calcul de longueurs de chaînes de réécriture dans le monoïde libre
- Sufficient-completeness, ground-reducibility and their complexity
- Inverse monoids: decidability and complexity of algebraic questions.
- On the word problem for free products of semigroups and monoids
- Elements of Finite Order for Finite Monadic Church-Rosser Thue Systems
- On reduced thue systems
- A note on thue systems with a single defining relation
- Groups Presented by Finite Two-Monadic Church-Rosser Thue Systems
- Finite canonical rewriting systems for congruences generated by concurrency relations
- Commutativity in groups presented by finite Church-Rosser Thue systems
- Church-Rosser systems with respect to formal languages
- The problem of deciding confluence on a given congruence class is tractable for finite special string-rewriting systems
- Church-Rosser codes
- A note on special thue systems with a single defining relation
- THE PROPERTY FDT IS UNDECIDABLE FOR FINITELY PRESENTED MONOIDS THAT HAVE POLYNOMIAL-TIME DECIDABLE WORD PROBLEMS
- On confluence of one-rule trace-rewriting systems
- Decidability of confluence and termination of monadic term rewriting systems
- Efficient rewriting in cograph trace monoids
- Word problems over traces which are solvable in linear time
- Decision problems for cellular automata and their semigroups
- DECIDABILITY AND COMPLEXITY IN AUTOMATIC MONOIDS
- LOGICAL ASPECTS OF CAYLEY-GRAPHS: THE MONOID CASE
- Using string-rewriting for solving the word problem for finitely presented groups
- Decidable sentences of Church-Rosser congruences
- On public-key cryptosystem based on Church-Rosser string-rewriting systems
- A note on confluent Thue systems
- Confluence of one-rule Thue systems
- The Knuth-Bendix algorithm and the conjugacy problem in monoids.
- Some results on equational unification
- On weakly confluent monadic string-rewriting systems
- Finite complete rewriting systems for the Jantzen monoid and the Greendlinger group
- 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
- 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
- A shorter proof that palindromes are not a Church-Rosser language, with extensions to almost-confluent and preperfect Thue systems
- Security analysis of word problem-based cryptosystems
- 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
- On ground-confluence of term rewriting systems
- Word problems over traces which are solvable in linear time
- A complete rewriting system for a monoid of tree transformation classes
- Partially commutative inverse monoids.
This page was built for publication: Confluent and Other Types of Thue Systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3936184)
