View source for Finitely-determined function

<!--
f0403401.png
$#A+1 = 88 n = 0
$#C+1 = 88 : ~/encyclopedia/old_files/data/F040/F.0400340 Finitely\AAhdetermined function
Automatically converted into TeX, above some diagnostics.
Please remove this comment and the {{TEX|auto}} line below,
if TeX found to be correct.
-->

{{TEX|auto}}
{{TEX|done}}

A lexical function characterizing the behaviour of a finite automaton (cf. [[Automaton, finite|Automaton, finite]]). (A function is called ''lexical'' if its domain of definition and range of values are sets of [[word]]s or [[superword]]s.)

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|Automaton, finite]]; [[Automata, methods of specification of|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====
<table><TR><TD valign="top">[1]</TD> <TD valign="top"> S.C. Kleene, "Representation of events in nerve nets and finite automata" , ''Automata studies'' , '''34''' , Princeton Univ. Press (1956) pp. 3–41 {{MR|0077478}} {{ZBL|}} </TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top"> S.V. Yablonskii, "Introduction to discrete mathematics" , Moscow (1986) (In Russian) {{MR|0911107}} {{ZBL|}} </TD></TR></table>

====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|Germ]]) of functions and mappings. Cf. [[Singularities of differentiable mappings|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====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top"> S. Ginsburg, "The mathematical theory of context-free languages" , McGraw-Hill (1965) {{MR|0211815}} {{ZBL|0195.02301}} {{ZBL|0184.28401}} </TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top"> J.E. Hopcroft, J.D. Ulman, "Introduction to automata theory, languages and computation" , Addison-Wesley (1979) {{MR|0645539}} {{ZBL|0426.68001}} </TD></TR></table>