[next] [prev] [prev-tail] [tail] [up]
Finite-memory programs are probably one of the simplest classes of programs for which
our study would be meaningful. The first section of this chapter motivates the investigation
of this class. The second section introduces the mathematical systems of finite-state
transducers, and shows that they model the computations of finite-memory programs.
The third section provides grammatical characterizations for the languages that
finite-memory programs accept, and the fourth section considers the limitations of
those programs. The fifth section discusses the importance of closure properties
in the design of programs, and their applicability for finite-memory programs.
And the last section considers properties that are decidable for finite-memory
programs.
2.1 Motivation
2.2 Finite-State Transducers
2.3 Finite-State Automata and Regular Languages
2.4 Limitations of Finite-Memory Programs
2.5 Closure Properties for Finite-Memory Programs
2.6 Decidable Properties for Finite-Memory Programs
Exercises
Bibliographic Notes
[next] [prev] [prev-tail] [front] [up]