[next] [tail] [up]

2.1 Motivation

It is often useful when developing knowledge in a new field to start by considering restricted cases and then gradually expand to the general case. Such an approach allows a gradual increase in the complexity of the argumentation. In particular, it is a quite common strategy in the investigation of infinite systems to start by considering finite subsystems. We take a similar approach here by using programs with finite domains of variables, called finite-memory programs or finite-domain programs, first.

However, it should be mentioned that finite-memory programs are also important on their own merit. They are applicable in the design and analysis of some common types of computer programs.

For instance, in compilers (i.e., in programs that translate programs written in high-level languages to equivalent programs written in machine languages) the lexical analyzers are basically designed as finite-memory programs. The main task of a lexical analyzer is to scan the given inputs and locate the symbols that belong to each of the tokens.

Example 2.1.1 Let LEXANL be the finite-memory program in Figure 2.1.1(a).

char := "  "
do
    /* Find the first character of the next token. */
    if char = "  " then
        do
            if eof then accept
            read char
        until char "  "
    /* Determine the class of the token. */
    charClass := class(char)
   write className(charClass)
   /* Determine the remaining characters of the token. */
    do
        write char
        if eof then accept
        oldCharClass := charClass
        read char
        charClass := M(charClass, char)
   until charClass oldCharClass
until false

(a)

(b)

Figure 2.1.1

(a) A lexical analyzer. (b) Tables for the lexical analyzer.

The domain of the variables is assumed to equal {" ", "A", . . . , "Z", "0", . . . , "9", 0, 1, 2}, with " " as initial value. The functions class, className, and M are defined by the tables of Figure 2.1.1(b).

LEXANL is a lexical analyzer that determines the tokens in the given inputs, and classifies them into identifiers and natural numbers. Each identifier is represented by a letter followed by an arbitrary number of letters and digits. Each natural number is represented by one or more digits. Each pair of consecutive tokens, except for a natural number followed by an identifier, must be separated by one or more blanks.

LEXANL can be easily modified to recognize a different class of tokens, by just redefining class, className, and M.

Protocols for communicating processes are also examples of systems that are frequently designed as finite-memory programs. In such systems, each process is represented by a finite-memory program. Each channel from one process to another is abstracted by an implicit queue, that is, by a first-in-first-out memory. At each instance the queue holds those messages that have been sent through the channel but not received yet. Each sending of a message is represented by the writing of the message to the appropriate channel. Each receiving of a message is represented by the reading of the message from the appropriate channel.

In Section 2.6 it is shown that finite-memory programs have some interesting decidable properties. Such decidable properties make the finite-memory programs also attractive as tools for showing the complexity of some seemingly unrelated problems.

Example 2.1.2 Consider the problem K of deciding the existence of solutions over the natural numbers for systems of linear Diophantine equations, that is, for systems of equations of the following form. The a_{i j}'s and b_i's are assumed to be integers.

a_{1 1}x₁ + + a_{1 n}x_n	=	b₁



a_{m 1}x₁ + + a_{m n}x_n	=	b_m

No straightforward algorithm seems to be evident for deciding the problem, though one can easily partially decide the problem by exhaustively searching for an assignment to the variables that satisfies the given system.

For each instance I of K, a finite-memory program P_I can be constructed to accept some input if and only if I has a solution over the natural numbers. Consequently, the problem K is reducible to the emptiness problem for finite-memory programs. The decidability of K is then implied by the decidability of the emptiness problem for finite-memory programs (Theorem 2.6.1).

In fact, the proof of Theorem 2.6.1 implies that a system I has a solution over the natural numbers if and only if the system has a solution in which the values of x₁, . . . , x_n are no greater than some bound that depends only on the a_{i j}'s, b_i's, m and n.

Computer programs that use no auxiliary memory, except for holding the input and output values, are by definition examples of finite-memory programs. However, such programs can deal with domains of high cardinality (i.e., 2^k for computers with k bits per word), and as a result their designs are generally not affected by the finiteness of their domains. Consequently, such programs should not generally be considered as "natural" finite-memory programs.

[next] [front] [up]