[next] [prev] [prev-tail] [tail] [up]  

Chapter 3  RECURSIVE FINITE-DOMAIN PROGRAMS

Recursion is an important programming tool that deserves an investigation on its own merits. However, it takes on additional importance here by providing an intermediate class of programs -- between the restricted class of finite-memory programs and the general class of programs. This intermediate class is obtained by introducing recursion into finite-domain programs.

The first section of this chapter considers the notion of recursion in programs. The second section shows that recursive finite-domain programs are characterized by finite-state transducers that are augmented by pushdown memory. A grammatical characterization for the recursive finite-domain programs is provided in the third section. The fourth section considers the limitations of recursive finite-domain programs. And the fifth and sixth sections consider closure and decidable properties of recursive finite-domain programs, respectively.

   3.1 Recursion
   3.2 Pushdown Transducers
   3.3 Context-Free Languages
   3.4 Limitations of Recursive Finite-Domain Programs
   3.5 Closure Properties for Recursive Finite-Domain Programs
   3.6 Decidable Properties for Recursive Finite-Domain Programs
   Exercises
   Bibliographic Notes

[next] [prev] [prev-tail] [front] [up]