Innermost-Reachability and Innermost-Joinability Are Decidable for Shallow Term Rewrite Systems

摘要

Reachability and joinability are central properties of term rewriting. Unfortunately they are undecidable in general, and even for some restricted classes of term rewrite systems, like shallow term rewrite systems (where variables are only allowed to occur at depth 0 or 1 in the terms of the rules). Innermost rewriting is one of the most studied and used strategies for rewriting, since it corresponds to the "call by value" computation of programming languages. Henceforth, it is meaningful to study whether reachability and joinability are indeed decidable for a significant class of term rewrite systems with the use of the innermost strategy. In this paper we show that reachability and joinability are decidable for shallow term rewrite systems assuming that the innermost strategy is used. All of these results are obtained via the definition of the concept of weak normal form, and a construction of a finite representation of all weak normal forms reachable from every constant. For the particular left-linear shallow case and assuming that the maximum arity of the signature is a constant, these results are obtained with polynomial time complexity.