Infinite regular Thue systems

DOI10.1016/0304-3975(83)90060-9MaRDI QIDQ1839248zbMATH OpenOpenAlexFDO

Authors Colm P. O'Dunlaing

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)90060-9

zbMATH Keywords

Church-Rosser propertyconfluenceThue systems

Mathematics Subject Classification ID

Thue and Post systems, etc. (03D03) Computability and recursion theory on ordinals, admissible sets, etc. (03D60) Abstract data types; algebraic specification (68Q65)

Cites work

• Confluent and Other Types of Thue Systems
• Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
• Deterministic context free languages
• scientific article; zbMATH DE number 3131080 (Why is no real title available?)
• scientific article; zbMATH DE number 3850463 (Why is no real title available?)
• scientific article; zbMATH DE number 3817043 (Why is no real title available?)
• scientific article; zbMATH DE number 3598658 (Why is no real title available?)
• Monadic Thue systems
• On a special monoid with a single defining relation
• Testing for the Church-Rosser property
• Thue congruences and the Church-Rosser property
• Une généralisation des ensembles de Dyck

Cited in

(31)

• Some undecidability results for non-monadic Church-Rosser Thue systems
• Complexity results on the conjugacy problem for monoids
• The equivalence and inclusion problems for NTS languages
• Complexity of certain decision problems about congruential languages
• On the regular equivalence problem for regular Thue systems
• The problems of cyclic equality and conjugacy for finite complete rewriting systems
• Thue systems as rewriting systems
• On deciding the confluence of a finite string-rewriting system on a given congruence class
• Pseudo-natural algorithms for finitely generated presentations of monoids and groups
• An efficient algorithm to decide whether a monoid presented by a regular Church-Rosser Thue system is a group
• A polynomial algorithm testing partial confluence of basic semi-Thue systems
• When is a monoid a group? The Church-Rosser case is tractable
• Some undecidability results concerning the property of preserving regularity
• Undecidable properties of monoids with word problem solvable in linear time. II: Cross sections and homological and homotopical finiteness conditions.
• Regular Gröbner bases
• Undecidable questions related to Church-Rosser Thue systems
• Infinite complete group presentations
• A note on thue systems with a single defining relation
• Church-Rosser systems with respect to formal languages
• THE PROPERTY FDT IS UNDECIDABLE FOR FINITELY PRESENTED MONOIDS THAT HAVE POLYNOMIAL-TIME DECIDABLE WORD PROBLEMS
• KNUTH–BENDIX FOR GROUPS WITH INFINITELY MANY RULES
• A polynomial algorithm testing partial confluence of basic semi-Thue systems
• Decidable sentences of Church-Rosser congruences
• A finitely presented monoid which has solvable word problem but has no regular complete presentation
• On weakly confluent monadic string-rewriting systems
• Insertion languages
• The undecidability of the preperfectness of Thue systems
• Homogeneous Thue systems and the Church-Rosser property
• Some decision problems about controlled rewriting systems
• About the descriptive power of certain classes of finite string-rewriting systems
• A characterisation of deterministic context-free languages by means of right-congruences

This page was built for publication: Infinite regular Thue systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1839248)