Abstract
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 programs11We use 'programs' and 'systems' interchangeably as trss are very similar to functional programs. In fact, the trss considered in this paper follow the so called constructor discipline and are essentially functional programs. 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.
| Original language | English |
|---|---|
| Pages (from-to) | 129-149 |
| Number of pages | 21 |
| Journal | Theoretical Computer Science |
| Volume | 397 |
| Issue number | 1-3 |
| DOIs | |
| State | Published - 20 May 2008 |
ASJC Scopus subject areas
- Theoretical Computer Science
- General Computer Science
Fingerprint
Dive into the research topics of 'Some classes of term rewriting systems inferable from positive data'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver