Total termination of term rewriting

We investigate proving termination of term rewriting systems by a compositional interpretation of terms in a total well-founded order. This kind of termination is calledtotal termination. Equivalently total termination can be characterized by the existence of an order on ground terms which is total, wellfounded and closed under contexts. For finite signatures, total termination implies simple termination. The converse does not hold. However, total termination generalizes most of the usual techniques for proving termination (including the well-known recursive path order). It turns out that for this kind of termination the only interesting orders below ₀ are built from the natural numbers by lexicographic product and the multiset construction. By examples we show that both constructions are essential. Most of the techniques used are based on ordinal arithmetic.Supported by NWO, the Dutch Organization for Scientific Research, under grant 612-316-041.     

Ordinal mind change complexity of language identification

The approach of ordinal mind change complexity, introduced by Freivalds and Smith, uses (notations for) constructive ordinals to bound the number of mind changes made by a learning machine. This approach provides a measure of the extent to which a learning machine has to keep revising its estimate of the number of mind changes it will make before converging to a correct hypothesis for languages in the class being learned. Recently, this notion, which also yields a measure for the difficulty of learning a class of languages, has been used to analyze the learnability of rich concept classes.

The present paper further investigates the utility of ordinal mind change complexity. It is shown that for identification from both positive and negative data and n 1, the ordinal mind change complexity of the class of languages formed by unions of up to n + 1 pattern languages is only ω ×₀ notn(n) (where notn(n) is a notation for n, ω is a notation for the least limit ordinal and ×₀ represents ordinal multiplication). This result nicely extends an observation of Lange and Zeugmann that pattern languages can be identified from both positive and negative data with 0 mind changes.

Existence of an ordinal mind change bound for a class of learnable languages can be seen as an indication of its learning “tractability”. Conditions are investigated under which a class has an ordinal mind change bound for identification from positive data. It is shown that an indexed family of languages has an ordinal mind change bound if it has finite elasticity and can be identified by a conservative machine. It is also shown that the requirement of conservative identification can be sacrificed for the purely topological requirement ofM-finite thickness. Interaction between identification by monotonic strategies and existence of ordinal mind change bound is also investigated.