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 is an alphabet. Let
denote the set of all words, and
the set of all words or the set of all superwords over
. A function
mapping
into
, where
and
are any finite alphabets, is called a determined function if it satisfies the following two conditions:
1) for any in
, the length of
is equal to the length of
; and
2) if is a word of length
and
,
, where
, then the values
and
have the same beginnings of length
.
If a determined function is defined on the set
of all superwords over
then, by conditions 1) and 2), it can be extended to the set
: For an arbitrary word
of length
, the value
coincides with the beginning of length
of the value
, where
is an arbitrary superword over
. Thus, every determined function
satisfies the condition:
3) for any word in
and any
in
one has
, where
is a determined function on the set
, uniquely determined by the word
.
The function is called the remainder function for
. Condition 3) implies that every determined function
defines an equivalence relation
on the set
:
if and only if
. 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
. 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
variables, where
, if a collection of
words of the same length (or superwords) over alphabets
, respectively, is considered as a word (superword) over the alphabet
— the Cartesian product of
. Thus, one can consider finitely-determined functions with several outcomes, that is, whose values are sets of
words or superwords over alphabets
, 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
is closed under superposition. The minimal (in number of states) automaton
computing a finitely-determined function
of weight
contains
states and can be constructed as follows. Let
be arbitrary representatives of the equivalence classes under the relation
. To each class
,
, corresponds a state
of the automaton
. The transition function
and the output function
are defined by the following conditions: If
and
, then
, the state
corresponds to the class
;
. The initial state is taken as that corresponding to the class
, where
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 be a smooth function taking
to
. Roughly, a function
is finitely determined at
if up to local diffeomorphisms of
and
it is uniquely determined near 0 by the terms of order
of its Taylor series at
; it is then said to be
-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 |
Finitely-determined function. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Finitely-determined_function&oldid=46930