African Journal of
Mathematics and Computer Science Research

  • Abbreviation: Afr. J. Math. Comput. Sci. Res.
  • Language: English
  • ISSN: 2006-9731
  • DOI: 10.5897/AJMCSR
  • Start Year: 2008
  • Published Articles: 254

Review

An overview of term rewriting systems

Dasharath Singh1, Ali Maianguwa Shuaibu2* and Adeku Musa Ibrahim1
  1Department of Mathematics, Ahmadu Bello University, Zaria-Nigeria. 2Department of Mathematics, Statistics and Computer Science, Kaduna Polytechnic, Kaduna, Nigeria.
Email: [email protected]

  •  Accepted: 19 March 2012
  •  Published: 31 July 2012

Abstract

 

It is well-known that termination of finite term of rewriting systems is generally undecidable. NoItwithstanding, a remarkable result is that, rewriting systems are Turing complete. A number of methods have been developed to establish termination for certain term of rewriting systems, particularly occurring in practical situations. In this paper, we present an overview of the existing methods used for termination proofs. We also outline areas of applications of term rewriting systems along with recent developments in regard to automated termination proofs.

 

Key words: Confluence, rewriting, term, termination, turing complete.