# 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.

How to Cite This Entry:
Finitely-determined function. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Finitely-determined_function&oldid=46930
This article was adapted from an original article by Yu.I. Yanov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article