Algorithm, local
An algorithm which specifies the attributes of elements of a structured set and uses, at each step, only information about neighbourhoods of the element. Problems of the existence or non-existence of effective algorithms for various discrete optimization problems are naturally formulated in terms of local algorithms.
Let there be given a family of sets, and let there be assigned to each pair
, where
, a set
such that: 1)
; 2)
; and 3) if
,
and
, then
. The set
will then be denoted as a neighbourhood of
in
. Examples of neighbourhoods are conjunction neighbourhoods in a contracted normal form (cf. Boolean functions, minimization of).
Let be a finite undirected graph,
, where
is the set of vertices of
, and let
be the set of edges of
. A neighbourhood
of an edge
of the graph
consists of all vertices of the edges incident with the edge
, and also of all edges whose vertices are included in the neighbourhood
. Let
be a defined neighbourhood; the neighbourhood
then consists of all vertices of the edges incident with the vertices of the neighbourhood
and all edges, the vertices of which belong to the neighbourhood
. The neighbourhoods
of an arbitrary vertex
of the graph
are introduced in a similar manner.
Let a system of two-place predicates , which is subdivided into two non-intersecting subsets
and
, be defined on pairs
,
. The elements of the first subset are called the main predicates, while those of the second are called the auxiliary predicates. A vector
is called an information vector if
,
. A vector
is called permissible for
in
if for all
the equality
is satisfied. The set
of all information vectors permissible for
in
is called the information set of
in
.
Let and
,
. The set
is called permissible for
. The class
of all sets
permissible for
is called the information class of the set
over the system of predicates
. Clearly, a neighbourhood
defines a neighbourhood
.
Introduce a system of functions such that
![]() |
The functions will be defined over all pairs
such that
,
, and satisfies the following conditions: 1)
if
; and 2) the set
, which is obtained from
by replacing the element
by
, is permissible for
, i.e.
. For the sake of brevity, the pairs
are denoted by
.
A partial order is introduced on some of the above sets: 1) on the set one takes
,
; 2) on the set
of information vectors of length
one takes
if
,
; 3) on the set of elements with marks one takes
if
; 4) on the set
one takes
if, first,
and
belong to the same information class
and, secondly, if
follows from
and
; 5) on the set of neighbourhoods of the form
one takes
, where
and
if and only if
and if it follows from
and
that
.
Let and
be elements of one of the sets 1)–5). If
and
, then the elements
and
are called equi-informative, which is denoted by
. A function
is called monotone if it follows from
that, for
,
![]() |
The determination of a local algorithm also necessitates the introduction of an ordering algorithm . Let
be an arbitrary set of elements with information vectors, and let
. Consider the set
of all pairs
such that
,
,
. The algorithm
orders the set
. The local algortihm
is completely defined by the system of predicates
, by the subdivision of this system into main predicates
and auxiliary predicates
, by the system of monotone functions
,
, and by the algorithm
.
Let ,
. The first step of the local algorithm may be described as follows. Algorithm
is applied to the set
, where
; for the first pair
of the ordered sequence one computes
and the element
is then replaced by
; if
, then one takes the second pair, etc.; if for all elements
the equality
is true, then the local algorithm
is terminated after reviewing all the pairs from
. Otherwise, after replacement of the vector
by the new vector
, algorithm
is terminated if there are no more elements with at least one symbol
in the first
places of the information vectors; if there are such elements, the first step of the local algorithm terminates. Let the number of steps of the local algorithm
which have been performed be
. The
-st step is carried out exactly as the first step, except that instead of the set
one now considers the set
into which the set
has been converted after the first
steps of the local algorithm
. Owing to the monotone nature of the functions
,
, the local algorithm
will be terminated after a finite number of steps.
The starting theorems for local algorithms are the uniqueness theorem and the theorem on the existence of a best algorithm. The first theorem states that the result of the calculation of the main predicates is independent of the algorithm (the order in which the elements of the set
are taken). The second theorem stipulates the existence, under very general conditions, of a best local algorithm, i.e. of a local algorithm which uses a given system of neighbourhoods to compute given main predicates with fixed auxiliary predicates, whenever this is done by any other local algorithm with an identical system of neighbourhoods, and main and auxiliary predicates.
The problem of finding a best local algorithm in explicit form has been solved for algorithms of synthesis of minimal coverings. Let there be given a tuple , where
is a set,
is the complexity of
,
,
,
. The complexity of the tuple
is
. The problem is how to construct a covering of
by sets from a number of
with minimum complexity. A system of neighbourhoods
for each
is introduced in a manner similar to the introduction of a system of neighbourhoods for conjunctions. A best local algorithm is constructed for a system of neighbourhoods
at fixed predicates: the set of auxiliary predicates is empty; the main predicates are considered to be the predicates
(
is not included in any minimal covering of
) and
(
is included in all the minimal coverings of
). Best local algorithms have also been constructed to calculate simple properties of edges of a graph. Various local algorithms have been proposed to solve problems of minimization of Boolean functions, of discrete linear programming, etc.
Computability of best local algorithms in a class of local algorithms is an important problem in the theory of local algorithms. If a system of imbedded neighbourhoods is given on the pairs
,
,
, and if the local algorithm operates with respect to the system
of neighbourhoods where
, then one says that the local algorithm has index
. It is natural to consider the number of predicates
in the definition of a local algorithm as the quantity of memory of the local algorithm. Let there be given a set
of predicates
. It is considered that all the predicates participating in the definition of the local algorithm belong to
. Let
be the result of applying the local algorithm
to
,
,
. One says that the predicate
is not
-computable if for any local algorithm of index
with memory quantity
for the main predicate
and for the auxiliary predicates
from
there exists a set
such that in
the predicate
will not be computable for all elements.
Let be the set of all Boolean functions (cf. Boolean function) in the variables
and let
be the predicate ( "the conjunction A is included in at least one minimal disjunctive normal form" ). With natural limitations imposed on the class of predicates
it was found that the predicate
is not
-computable if
. It is interesting to note that the predicate
( "the conjunction A is included in at least one dead-end disjunctive normal form of f" ) (cf. Boolean functions, normal forms of) is
-computable, but is not
-computable. Similar results were obtained for predicates describing the entry of an edge into a shortest path between given vertices of a graph.
See also the references to Boolean functions, minimization of.
References
[1a] | Yu.I. Zhuravlev, "Local algorithms for the calculation of information Part I" Cybernetics , 1 : 1 (1965) pp. 10–16 Kibernetika (Kiev) , 1 : 1 (1965) pp. 12–19 |
[1b] | Yu.I. Zhuravlev, "Local algorithms for the calculation of information Part II" Cybernetics , 2 : 2 (1966) pp. 1–8 Kibernetika (Kiev) , 2 : 2 (1966) pp. 1–11 |
[2] | I.V. Khutoryanskaya, "Aspects of the theory of local algorithms on graphs" Cybernetics , 7 : 1 (1971) pp. 37–44 Kibernetika (Kiev) : 1 (1971) pp. 29–33 |
[3] | Yu.I. Zhuravlev, "Set-theoretical methods in the algebra of logic" Problemy Kibernet. , 8 (1962) pp. 5–44 (In Russian) |
Comments
As a specific area (or in this form), the subject seems not to have been studied in the Western literature. It may be related to the study of Systolic Array algorithms [a1], Chapt. 8.
References
[a1] | C. Mead, L. Conway, "Introduction to VLSI systems" , Addison-Wesley (1980) pp. 263–330 |
Algorithm, local. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Algorithm,_local&oldid=14811