View source for Finitely-determined function

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 <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:

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

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" />.

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:

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" />.

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.

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

====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>