A decidable word problem without equivalent canonical term rewriting system

DOI10.1080/00207168908803729MaRDI QIDQ3816049zbMATH OpenOpenAlexFDO

Authors

Publication date 1989

Published in International Journal of Computer Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1080/00207168908803729

zbMATH Keywords

efficient algorithmterm rewriting system

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Word problems, etc. in computability and recursion theory (03D40) Word problems (aspects of algebraic structures) (08A50) Abstract data types; algebraic specification (68Q65)

Recommendations

• A finite Thue system with decidable word problem and without equivalent finite canonical system
• On a connection between the word problem and decidability of the equational theory
• A finitely axiomatizable undecidable equational theory with recursively solvable word problems
• scientific article; zbMATH DE number 1186371
• Finite complete rewriting systems and the complexity of word problem
• Deciding the word problem in the union of equational theories.
• scientific article; zbMATH DE number 1482215
• scientific article; zbMATH DE number 4016226
• The satisfiability of word equations: decidable and undecidable theories
• scientific article; zbMATH DE number 1123898

Cites work

• A finite Thue system with decidable word problem and without equivalent finite canonical system
• A-transformation dans les arbres n-aires
• Enumerating, Ranking and Unranking Binary Trees
• scientific article; zbMATH DE number 4014693 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 3416095 (Why is no real title available?)
• Problems of associativity: a simple proof for the lattice property of systems ordered by a semi-associative law
• Word problems

Cited in

(9)

• Almost all one-rule Thue systems have decidable word problems
• A finite Thue system with decidable word problem and without equivalent finite canonical system
• The word problem for Smullyan's lark combinator is decidable
• Rational languages defined with a non-associative concatenation
• On ground word problem of term equation systems
• THE WORD PROBLEM OF ACD-GROUND THEORIES IS UNDECIDABLE
• scientific article; zbMATH DE number 7527483 (Why is no real title available?)
• Solving the Caesar problem without categorical sortals
• Weak associativity and restricted rotation

Describes a project that uses

Uses Software

• REVE

This page was built for publication: A decidable word problem without equivalent canonical term rewriting system

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