AUTOMATON PROGRAMS AND REGULAR FUNCTIONAL EXPRESSIONS-ON AN EXTENSION OF DERIVATIVES
Teruyasu Nishizawa · Bulletin of informatics and cybernetics · 1984
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 function of $ W $ to $ W $ and $ D(f) $ devote the domain of $ f $. When it holds that $ f(x) = f(y) $ implies $ p(x) equiv p(y) $ for all $ x, y $ in $ W $, $ P $ has a derivative a $ partial_fP $ by $ f $ which is defined by $ (partial_f P)(x) leftrightarrow (exists y in D(f)) { p(y) wedge f(y) = x } $. We can construct an automaton program computing a predicate by taking these extended derivatives of the predicate if it has a finite derivative-closure.