Some classes of term rewriting systems inferable from positive data

In this paper, we study the inferability of term rewriting systems (trss, for short) from positive examples alone. Two classes of trss inferable from positive data are presented, namely, simple flat trss and linear-bounded trss. These classes of trss are rich enough to include many divide-and-conquer programs1 like addition, doubling, logarithm, tree-count, list-count, split, append, reverse, etc. The classes of simple flat trss and linear-bounded trss are incomparable, i.e., there are functions that can be computed by simple flat trss but not by linear-bounded trss and vice versa.