Namespaces
Variants
Actions

Difference between revisions of "Finitely-determined function"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
 
(2 intermediate revisions by 2 users not shown)
Line 1: Line 1:
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 words or superwords.)
+
<!--
 +
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.
 +
-->
  
Suppose that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f0403401.png" /> is an alphabet. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f0403402.png" /> denote the set of all words, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f0403403.png" /> the set of all words or the set of all superwords over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f0403404.png" />. A function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f0403405.png" /> mapping <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f0403406.png" /> into <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f0403407.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f0403408.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f0403409.png" /> are any finite alphabets, is called a determined function if it satisfies the following two conditions:
+
{{TEX|auto}}
 +
{{TEX|done}}
  
1) for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034010.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034011.png" />, the length of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034012.png" /> is equal to the length of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034013.png" />; and
+
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.)
  
2) if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034014.png" /> is a word of length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034015.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034016.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034017.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034018.png" />, then the values <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034019.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034020.png" /> have the same beginnings of length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034021.png" />.
+
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:
  
If a determined function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034022.png" /> is defined on the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034023.png" /> of all superwords over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034024.png" /> then, by conditions 1) and 2), it can be extended to the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034025.png" />: For an arbitrary word <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034026.png" /> of length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034027.png" />, the value <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034028.png" /> coincides with the beginning of length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034029.png" /> of the value <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034030.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034031.png" /> is an arbitrary superword over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034032.png" />. Thus, every determined function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034033.png" /> satisfies the condition:
+
1) for any  $  \alpha $
 +
in  $  A  ^ {0} $,  
 +
the length of f ( \alpha) $
 +
is equal to the length of  $  \alpha $;
 +
and
  
3) for any word <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034034.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034035.png" /> and any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034036.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034037.png" /> one has <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034038.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034039.png" /> is a determined function on the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034040.png" />, uniquely determined by the word <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034041.png" />.
+
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 $.
  
The function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034042.png" /> is called the remainder function for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034043.png" />. Condition 3) implies that every determined function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034044.png" /> defines an equivalence relation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034045.png" /> on the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034046.png" />: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034047.png" /> if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034048.png" />. 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034049.png" />. 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034050.png" /> variables, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034051.png" />, if a collection of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034052.png" /> words of the same length (or superwords) over alphabets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034053.png" />, respectively, is considered as a word (superword) over the alphabet <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034054.png" /> — the Cartesian product of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034055.png" />. Thus, one can consider finitely-determined functions with several outcomes, that is, whose values are sets of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034056.png" /> words or superwords over alphabets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034057.png" />, 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034058.png" /> is closed under superposition. The minimal (in number of states) automaton <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034059.png" /> computing a finitely-determined function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034060.png" /> of weight <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034061.png" /> contains <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034062.png" /> states and can be constructed as follows. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034063.png" /> be arbitrary representatives of the equivalence classes under the relation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034064.png" />. To each class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034065.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034066.png" />, corresponds a state <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034067.png" /> of the automaton <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034068.png" />. The transition function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034069.png" /> and the output function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034070.png" /> are defined by the following conditions: If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034071.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034072.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034073.png" />, the state <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034074.png" /> corresponds to the class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034075.png" />; <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034076.png" />. The initial state is taken as that corresponding to the class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034077.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034078.png" /> is the empty word.
+
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:
  
====References====
+
3) for any word  $  \alpha $
<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 (1956pp. 3–41</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top"> S.V. Yablonskii,   "Introduction to discrete mathematics" , Moscow (1986) (In Russian)</TD></TR></table>
+
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====
 
====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.
 
(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.
+
Instead of "remainder function" one also uses derivative.
  
A rather different notion of finite determinacy of functions occurs in differential topology. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034079.png" /> be a smooth function taking <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034080.png" /> to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034081.png" />. Roughly, a function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034082.png" /> is finitely determined at <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034083.png" /> if up to local diffeomorphisms of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034084.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034085.png" /> it is uniquely determined near 0 by the terms of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034086.png" /> of its Taylor series at <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034087.png" />; it is then said to be <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040340/f04034088.png" />-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.
+
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====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top"> S. Ginsburg,   "The mathematical theory of context-free languages" , McGraw-Hill (1965)</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)</TD></TR></table>
+
<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>

Latest revision as of 19:39, 5 June 2020


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