A DEPENDENCE TERM REWRITING SYSTEM AND ITS APPLICATIONS IN PROGRAMMING LANGUAGES

Term rewriting system is a simple and powerful computing model and it has important applications in many fields. However, it cant satisfy certain requirements well in some applications. In order to solve these problems, a new kind of computing model, called dependence term rewriting system, and its applications in programming language are introduced in the paper. Intuitively, the dependence term rewriting system is a kind of term rewriting system in which there exists dependence relation by function symbol between rewriting rules. This computing model has good properties （e.g., confluence and termination） and powerful expressibility, and by using it certain non termination problems can be solved and more parallelism can be exploited.