Infinite regular Thue systems
From MaRDI portal
Publication:1839248
DOI10.1016/0304-3975(83)90060-9zbMath0512.03018OpenAlexW2018146336MaRDI QIDQ1839248
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
Abstract data types; algebraic specification (68Q65) Thue and Post systems, etc. (03D03) Computability and recursion theory on ordinals, admissible sets, etc. (03D60)
Related Items (31)
THE PROPERTY FDT IS UNDECIDABLE FOR FINITELY PRESENTED MONOIDS THAT HAVE POLYNOMIAL-TIME DECIDABLE WORD PROBLEMS ⋮ KNUTH–BENDIX FOR GROUPS WITH INFINITELY MANY RULES ⋮ 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 ⋮ A note on thue systems with a single defining relation ⋮ Pseudo-natural algorithms for finitely generated presentations of monoids and groups ⋮ Decidable sentences of Church-Rosser congruences ⋮ Infinite complete group presentations ⋮ 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 ⋮ Undecidable properties of monoids with word problem solvable in linear time. II: Cross sections and homological and homotopical finiteness conditions. ⋮ 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 ⋮ When is a monoid a group? The Church-Rosser case is tractable ⋮ Church-Rosser systems with respect to formal languages ⋮ A finitely presented monoid which has solvable word problem but has no regular complete presentation ⋮ On weakly confluent monadic string-rewriting systems ⋮ A polynomial algorithm testing partial confluence of basic semi-Thue systems ⋮ Some undecidability results concerning the property of preserving regularity ⋮ Undecidable questions related to Church-Rosser Thue systems ⋮ Some undecidability results for non-monadic Church-Rosser Thue systems ⋮ Insertion languages ⋮ The undecidability of the preperfectness of Thue systems ⋮ Homogeneous Thue systems and the Church-Rosser property ⋮ Regular Gröbner bases ⋮ Complexity results on the conjugacy problem for monoids
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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
- 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
- Deterministic context free languages
This page was built for publication: Infinite regular Thue systems
