Toward a General Rewriting-Based Framework for Reducibility

Colin Riba (1)

1 LIP - Laboratoire de l'Informatique du Parallélisme

Reducibility is a powerful proof method which applies to various properties of typed terms in different type systems. For strong normalization, different vari- ants are known, such as Girard's reducibility candidates, Tait's saturated sets and biorthogonals. They differ by the closure conditions imposed to types interpreta- tions, called here reducibility families. This paper is about the computational and observational properties underlying untyped reducibility. Our starting point is the comparison of reducibility families w.r.t. their ability to handle rewriting, for which their possible stability by union plays an important role. Indeed, usual saturated sets are generally stable by union, but with rewriting it can be difficult to define a uniform notion of saturated sets. On the other hand, rewriting is more naturally taken into account by reducibility candidates, but they are not always stable by union. It seems that for a given rewrite relation, the stability by union of reducibility candidates should imply the ability to naturally define corresponding saturated sets. In this paper, we seek to devise a general framework in which the above claim can be substantiated. In particular, this framework should be as simple as possible, while allowing the formulation of general notions of reducibility candidates and saturated sets. We present a notion of non-interaction which allows to define neutral terms and reducibility candidates in a generic way. This notion can be formulated in a very simple and general framework, based only on a rewrite relation and a set of contexts, called elimination contexts, required to satisfy some simple properties. This provides a convenient level of abstraction to prove fundamental properties of reducibility candidates, to compare them with biorthogonals, and to study their stability by union. Moreover, we propose a general form of saturated sets, issued from the stability by union of reducibility candidates.

Mots clés: Lambda-Calculus; Rewriting; Typing; Termination; Reducibility

Domaines: Logique en informatique [cs.LO]

Colin Riba. Toward a General Rewriting-Based Framework for Reducibility. 2008. ⟨hal-00779623⟩