Thue systems as rewriting systems

DOI10.1016/S0747-7171(87)80021-4zbMath0638.68091MaRDI QIDQ1099642

Ronald V. Book

Publication date: 1987

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

zbMATH Keywords

surveycomputational complexitydecidabilityterm rewriting systemsThue systemsreplacement systems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Complexity of computation (including implicit computational complexity) (03D15) Thue and Post systems, etc. (03D03)

Related Items

Bottom-up tree pushdown automata: Classification and connection with rewrite systems, Semigroups satisfying x m+n = x n, Trace rewriting systems, SOME EXACT SEQUENCES FOR THE HOMOTOPY (BI-)MODULE OF A MONOID, Applying rewriting methods to special monoids, Weights for total division orderings on strings, Simulation of Turing machines by a left-linear rewrite rule, An equational logic sampler, Restrictions of congruences generated by finite canonical string-rewriting systems, Decidability of confluence and termination of monadic term rewriting systems, Bottom-up tree pushdown automata and rewrite systems, On some algorithmic problems for groups and monoids, Complexity, combinatorial group theory and the language of palutators, Deterministic tree pushdown automata and monadic tree rewriting systems, Time-bounded controlled bidirectional grammars, The problem of deciding confluence on a given congruence class is tractable for finite special string-rewriting systems, Some polynomial-time algorithms for finite monadic Church-Rosser Thue systems, It is decidable whether a monadic thue system is canonical over a regular set, On the descriptive power of special Thue systems, On public-key cryptosystem based on Church-Rosser string-rewriting systems, Some decision problems about controlled rewriting systems, 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, A characterisation of deterministic context-free languages by means of right-congruences, A public key cryptosystem based on Lyndon words, Using groups for investigating rewrite systems, Conjugacy in special monoids, A criterion for proving noetherianity of a relation, The word problem for one-relation monoids: a survey, Undecidability of ground reducibility for word rewriting systems with variables, Word problem in free clumps, A decision algorithm for linear sentences on a PFM, On weakly confluent monadic string-rewriting systems, Simulation of Turing machines by a regular rewrite rule, Some properties of finite special string-rewriting systems, A field guide to equational logic, The pre-NTS property is undecidable for context-free grammars, Structural Monoids Associated to Equational Varieties, Semigroups presented by one relation and satisfying the Church-Rosser property, Contributions of Ronald V. Book to the theory of string-rewriting systems, Synchronization expressions with extended join operation, Cancellativity in finitely presented semigroups, On minimizing the \(\forall\)-\(\neg\) degree of a connective-free formula

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Decidable sentences of Church-Rosser congruences
• The Nielsen reduction and P-complete problems in free groups
• On the complexity of intersection and conjugacy problems in free groups
• Finite complete rewriting systems for the Jantzen monoid and the Greendlinger group
• Finite complete rewriting systems and the complexity of word problem
• Groups, the theory of ends, and context-free languages
• Remarks on an example of Jantzen
• The undecidability of the preperfectness of Thue systems
• Homogeneous Thue systems and the Church-Rosser property
• Sur les monoides à un relateur qui sont des groupes
• Conjugacy in monoids with a special Church-Rosser presentation is decidable
• 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
• Rewriting techniques and applications. (First International Conference), Dijon, France, May 20-22, 1985
• 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 deciding whether a monoid is a free monoid or is a group
• The equivalence and inclusion problems for NTS languages
• NTS languages are deterministic and congruential
• n-level rewriting systems
• Complexity of certain decision problems about congruential languages
• Surfaces and planar discontinuous groups. Revised and expanded transl. from the German by J. Stillwell
• A note on representations of a certain monoid
• 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
• Units of special Church-Rosser monoids
• Infinite regular Thue systems
• Undecidable questions related to Church-Rosser Thue systems
• Cancellation rules and extended word problems
• Calcul de longueurs de chaînes de réécriture dans le monoïde libre
• Une généralisation des ensembles de Dyck
• On theories with a combinatorial definition of 'equivalence'
• Dehn's algorithm for the word problem
• The Knuth-Bendix Completion Procedure and Thue Systems
• Elements of Finite Order for Finite Monadic Church-Rosser Thue Systems
• The word problem for one-relator semigroups
• The complexity of Dehn's algorithm for word problems in groups
• The uniform conjugacy problem for finite church—Rosser thue systems is NP-complete
• On reduced thue systems
• Church–Rosser Thue Systems that Present Free Monoids
• A note on thue systems with a single defining relation
• Groups Presented by Finite Two-Monadic Church-Rosser Thue Systems
• Church-Rosser Thue systems and formal languages
• Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
• Confluent and Other Types of Thue Systems
• Algorithmische Probleme bei Einrelatorgruppen und ihre Komplexität