AUTOMATON PROGRAMS AND REGULAR FUNCTIONAL EXPRESSIONS-ON AN EXTENSION OF DERIVATIVES

A method for constructing a finite automaton by taking derivatives of a regular set is a method for synthesizing a recursive program. We extend the method to synthesize more general programs than finite automata by extending the notion of derivatives. The programs synthesizable by this method are called automaton programs and the predicates computable by these programs are characterized by regular functional expressions. Let P be a one-place predicate over a set W, f be a partial func tion of W to W and D(f) devote the domain of f. When it holds that f (x)=f (y) implies p(x)mp (y) for all x, y in W, P has a deriva tive a fP by f which is defined by