New compact representations of infinite graphs are investigated. Finite automata are used to represent labelled hyper-graphs which can be also multi-graphs. Our approach consists of a general framework where vertices are represented by a regular prefix-free language and edges are represented by a regular language and a function over tuples. We consider three different functions over tuples: given a tuple the first function returns its first difference, the second one returns its suffix and the last...
New compact representations of infinite graphs are
investigated. Finite automata are used to represent labelled hyper-graphs
which can be also multi-graphs. Our approach consists of a general
framework where vertices are represented by a regular prefix-free language and
edges are represented by a regular language and a function over tuples.
We consider three different functions over tuples:
given a tuple
the first function returns its
first difference, the second one returns its suffix and...
The problem of synchronizing a network
of identical processors that work synchronously
at discrete steps is studied. Processors are arranged as an array of
rows and columns and can exchange each other only one bit
of information.
We give algorithms which
synchronize square arrays of ( × ) processors and give some
general constructions to synchronize arrays of ( × ) processors.
Algorithms are given to synchronize in time
, ,
and 2 a square array of ( × ) processors.
Our approach...
We present several solutions to
the Firing Squad Synchronization Problem on grid networks of
different shapes.
The nodes are finite state processors that
work in unison with other processors and in synchronized discrete steps. The
networks we deal with are: the line, the ring and the square.
For all of these models we consider one- and two-way
communication modes and we also constrain the quantity of information
that adjacent processors can exchange at each step.
We first present synchronization...
Download Results (CSV)