Finitely-determined function

A lexical function characterizing the behaviour of a finite automaton (cf. Automaton, finite). (A function is called lexical if its domain of definition and range of values are sets of words or superwords.)

Suppose that $ A $ is an alphabet. Let $ A ^ {*} $ denote the set of all words, and $ A ^ {0} $ the set of all words or the set of all superwords over $ A $. A function $ f $ mapping $ A ^ {0} $ into $ B ^ {0} $, where $ A $ and $ B $ are any finite alphabets, is called a determined function if it satisfies the following two conditions:

1) for any $ \alpha $ in $ A ^ {0} $, the length of $ f ( \alpha) $ is equal to the length of $ \alpha $; and

2) if $ \alpha $ is a word of length $ l $ and $ \alpha _ {1} = \alpha \alpha ^ \prime $, $ \alpha _ {2} = \alpha \alpha ^ {\prime\prime} $, where $ \alpha ^ \prime , \alpha ^ {\prime\prime} \in A ^ {0} $, then the values $ f ( \alpha _ {1} ) $ and $ f ( \alpha _ {2} ) $ have the same beginnings of length $ l $.

If a determined function $ f $ is defined on the set $ A ^ \infty $ of all superwords over $ A $ then, by conditions 1) and 2), it can be extended to the set $ A ^ {*} $: For an arbitrary word $ \alpha $ of length $ l $, the value $ f ( \alpha ) $ coincides with the beginning of length $ l $ of the value $ f ( \alpha \beta ) $, where $ \beta $ is an arbitrary superword over $ A $. Thus, every determined function $ f $ satisfies the condition:

3) for any word $ \alpha $ in $ A ^ {*} $ and any $ \beta $ in $ A ^ {0} $ one has $ f ( \alpha \beta ) = f ( \alpha ) f _ \alpha ( \beta ) $, where $ f _ \alpha $ is a determined function on the set $ A ^ {0} $, uniquely determined by the word $ \alpha $.

The function $ f _ \alpha $ is called the remainder function for $ f $. Condition 3) implies that every determined function $ f $ defines an equivalence relation $ R $ on the set $ A ^ {*} $: $ \alpha R \beta $ if and only if $ f _ \alpha = f _ \beta $. The rank of this relation, or, which comes to the same thing, the maximum number of pairwise-distinct remainder functions, is called the weight of the determined function $ f $. If the weight of a determined function is finite, then the function is called a finitely-determined function. This concept can also be extended to functions of $ m $ variables, where $ m \geq 2 $, if a collection of $ m $ words of the same length (or superwords) over alphabets $ A _ {1} \dots A _ {m} $, respectively, is considered as a word (superword) over the alphabet $ A _ {1} \times \dots \times A _ {m} $— the Cartesian product of $ A _ {1} \dots A _ {m} $. Thus, one can consider finitely-determined functions with several outcomes, that is, whose values are sets of $ k $ words or superwords over alphabets $ B _ {1} \dots B _ {k} $, respectively. The class of all finitely-determined functions coincides with the class of functions computable by finite automata. Hence the same means may be used to represent finitely-determined functions as are used to represent finite automata, e.g. canonical equations (see Automaton, finite; Automata, methods of specification of). This implies, in particular, that the class of finitely-determined functions with coincident alphabets $ A _ {1} = \dots = A _ {m} = B $ is closed under superposition. The minimal (in number of states) automaton $ \mathfrak A ( A, S, B, \phi , \psi , s _ {1} ) $ computing a finitely-determined function $ f $ of weight $ n $ contains $ n $ states and can be constructed as follows. Let $ \alpha _ {1} \dots \alpha _ {n} $ be arbitrary representatives of the equivalence classes under the relation $ R $. To each class $ R ( \alpha _ {i} ) $, $ i = 1 \dots n $, corresponds a state $ s _ {i} $ of the automaton $ \mathfrak A $. The transition function $ \phi $ and the output function $ \psi $ are defined by the following conditions: If $ a \in A $ and $ 1 \leq i \leq n $, then $ \phi ( s _ {i} , a) = s _ {j} $, the state $ s _ {j} $ corresponds to the class $ R ( \alpha _ {i} a) $; $ \psi ( s _ {i} , a) = f _ {\alpha _ {i} } ( a) $. The initial state is taken as that corresponding to the class $ R ( \Lambda ) $, where $ \Lambda $ is the empty word.

References

[1]	S.C. Kleene, "Representation of events in nerve nets and finite automata" , Automata studies , 34 , Princeton Univ. Press (1956) pp. 3–41 MR0077478
[2]	S.V. Yablonskii, "Introduction to discrete mathematics" , Moscow (1986) (In Russian) MR0911107

Comments

(Finitely-) determined functions are also called (finite) sequential machine mappings or Mealy mappings. They are a special case of gsm-mappings, for which condition 1) above is not required.

Instead of "remainder function" one also uses derivative.

A rather different notion of finite determinacy of functions occurs in differential topology. Let $ f : \mathbf R ^ {n} \rightarrow \mathbf R $ be a smooth function taking $ 0 \in \mathbf R ^ {n} $ to $ 0 \in \mathbf R $. Roughly, a function $ f $ is finitely determined at $ 0 $ if up to local diffeomorphisms of $ ( \mathbf R ^ {n} , 0 ) $ and $ ( \mathbf R , 0 ) $ it is uniquely determined near 0 by the terms of order $ \leq k $ of its Taylor series at $ 0 \in \mathbf R ^ {n} $; it is then said to be $ k $- determined. The precise notions involve germs (cf. Germ) of functions and mappings. Cf. Singularities of differentiable mappings for more details (in a more general setting) and for related notions such as stable germs of differentiable mappings, singularities of finite type, etc.

References

[a1]	S. Ginsburg, "The mathematical theory of context-free languages" , McGraw-Hill (1965) MR0211815 Zbl 0195.02301 Zbl 0184.28401
[a2]	J.E. Hopcroft, J.D. Ulman, "Introduction to automata theory, languages and computation" , Addison-Wesley (1979) MR0645539 Zbl 0426.68001