Page 1

Displaying 1 – 14 of 14

Showing per page

A Compositional Approach to Synchronize Two Dimensional Networks of Processors

Salvatore La Torre, Margherita Napoli, Mimmo Parente (2010)

RAIRO - Theoretical Informatics and Applications

The problem of synchronizing a network of identical processors that work synchronously at discrete steps is studied. Processors are arranged as an array of m rows and n columns and can exchange each other only one bit of information. We give algorithms which synchronize square arrays of (n × n) processors and give some general constructions to synchronize arrays of (m × n) processors. Algorithms are given to synchronize in time n2, n log n , n n and 2n a square array of (n × n) processors. Our approach...

Amenable groups and cellular automata

Tullio G. Ceccherini-Silberstein, Antonio Machi, Fabio Scarabotti (1999)

Annales de l'institut Fourier

We show that the theorems of Moore and Myhill hold for cellular automata whose universes are Cayley graphs of amenable finitely generated groups. This extends the analogous result of A. Machi and F. Mignosi “Garden of Eden configurations for cellular automata on Cayley graphs of groups” for groups of sub-exponential growth.

An intrinsically non minimal-time Minsky-like 6-states solution to the Firing Squad synchronization problem

Jean-Baptiste Yunès (2008)

RAIRO - Theoretical Informatics and Applications

Here is presented a 6-states non minimal-time solution which is intrinsically Minsky-like and solves the three following problems: unrestricted version on a line, with one initiator at each end of a line and the problem on a ring. We also give a complete proof of correctness of our solution, which was never done in a publication for Minsky's solutions.

Arbology: Trees and pushdown automata

Bořivoj Melichar, Jan Janoušek, Tomas Flouri (2012)

Kybernetika

We present a unified and systematic approach to basic principles of Arbology, a new algorithmic discipline focusing on algorithms on trees. Stringology, a highly developed algorithmic discipline in the area of string processing, can use finite automata as its basic model of computation. For various kinds of linear notations of ranked and unranked ordered trees it holds that subtrees of a tree in a linear notation are substrings of the tree in the linear notation. Arbology uses pushdown automata...

Currently displaying 1 – 14 of 14

Page 1