# 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

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.