Generalizing Context-Sensitivity in Term Rewriting

01.02.2008 - 31.01.2011
Research funding project
Generalizing Context-Sensitivity in Term Rewriting Term rewriting is a foundational formalism that is used in many areas of theoretical and practical computer science. The basic idea behind term rewriting is to replace equals by equals in given (symbolical) objects (in our case terms) until a final (or normal) form is reached which represents the result of the computation. Operationally, the formalism of term rewriting does not prescribe how these replacements are performed. Thus, in general such "rewrite derivations" are highly non-deterministic. Yet, especially in practical fields like equational programming and executable specifications it is important to have means to guide the rewriting process and thus to reduce the non-determinism in the computations, in order to otain an improved efficiency and/or to get the desired results. One major approach to achieve this goal is context-sensitivity. Here the structure of the terms being rewritten determines which next computation steps are actually possible, depending on the context of the subterm to be replaced. In essence this mechanism works by specifying (globally) for each function symbol, which of its arguments are accessible for replacements and which are forbidden. Approaches based on this concept of context-sensitvity have been extensively studied in the past 15 years, with considerable success. However, the expressive power of such traditional context-sensitive approaches remains quite limited. What we propose is to generalize the underlying concept of context-sensitivity in various ways, in order to obtain increased expressiveness and improved theoretical and practical results while retaining practical feasibility. One particular new idea that will be investigated are so-called "forbidden patterns" which should be left invariant during rewriting. We plan to evaluate the developed approach by implementing the new formalism and comparing it with other known approaches in terms of theoretical properties, expressiveness, practical applicability, efficiency and manageability.

People

Project leader

Project personnel

Institute

Grant funds

  • Österr. Akademie der Wissenschaften (National) Austrian Academy of Sciences

Research focus

  • Computational Intelligence: 100%

Keywords

GermanEnglish
Termersetzungterm rewriting
Kontextsensitivitätcontext-sensitivity

Publications