Skip to main navigation Skip to search Skip to main content

Some classes of term rewriting systems inferable from positive data

  • M. R.K. Krishna Rao*
  • *Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

2 Scopus citations

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 languageEnglish
Pages (from-to)129-149
Number of pages21
JournalTheoretical Computer Science
Volume397
Issue number1-3
DOIs
StatePublished - 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