Decision problems for finite special string-rewriting systems that are confluent on some congruence class

DOI10.1007/BF01178585zbMath0699.20047OpenAlexW2076828696MaRDI QIDQ912986

Louxin Zhang, Friedrich Otto

Publication date: 1991

Published in: Acta Informatica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01178585

zbMATH Keywords

algorithmsdecision problemsgeneralized word problemword problempower probleminclusion problemregular setscongruence classdivisibility problemsfinite, special string-rewriting systemsfiniteness problemgroup problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Free semigroups, generators and relations, word problems (20M05) Automata and formal grammars in connection with logical questions (03D05) Algebraic theory of languages and automata (68Q70) Semigroups in automata theory, linguistics, etc. (20M35) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Thue and Post systems, etc. (03D03)

Related Items

Applying rewriting methods to special monoids ⋮ Codes modulo finite monadic string-rewriting systems ⋮ On the word problem for special monoids ⋮ The problem of deciding confluence on a given congruence class is tractable for finite special string-rewriting systems ⋮ On the descriptive power of special Thue systems ⋮ The word problem for one-relation monoids: a survey ⋮ Completing a finite special string-rewriting system on the congruence class of the empty word ⋮ On weakly confluent monadic string-rewriting systems ⋮ Some properties of finite special string-rewriting systems ⋮ COMPLETE REWRITING SYSTEMS FOR CODIFIED SUBMONOIDS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Using string-rewriting for solving the word problem for finitely presented groups
• Decidable sentences of Church-Rosser congruences
• Conjugacy in monoids with a special Church-Rosser presentation is decidable
• About the descriptive power of certain classes of finite string-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
• A note on a special one-rule semi-Thue system
• 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
• On deciding whether a monoid is a free monoid or is a group
• Special monoids and special Thue systems
• The problems of cyclic equality and conjugacy for finite complete rewriting systems
• Systems of reductions
• Thue systems as rewriting systems
• On deciding the confluence of a finite string-rewriting system on a given congruence class
• Elements of finite order for finite weight-reducing and confluent Thue 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
• Testing for the Church-Rosser property
• Thue congruences and the Church-Rosser property
• When is a monoid a group? The Church-Rosser case is tractable
• Conjugacy in special monoids
• On the equivalence, containment, and covering problems for the regular and context-free languages
• Presentations of groups and monoids
• Cancellativity in finitely presented semigroups
• On theories with a combinatorial definition of 'equivalence'
• Elements of Finite Order for Finite Monadic Church-Rosser Thue Systems
• Confluent and Other Types of Thue Systems
• Fast Pattern Matching in Strings