PUMA
Istituto di Scienza e Tecnologie dell'Informazione     
Bolognesi T. A pseudo-random network mobile automaton with linear growth. Technical report, 2008.
 
 
Abstract
(English)
Based on the mobile automaton computational paradigm, a (fully deterministic) algorithm is introduced that grows planar graphs while exhibiting surprisingly uniform pseudo-random dynamics. The graph growth rate, as a function of the automaton steps, is O(n), and nicely combines with the O(Sqrt[n]) of a previously introduced algorithm of ours: these two rates are also achieved by two most elementary visit-and-grow procedures with regular dynamics, of which our automata can be viewed as randomized versions. Applications of mobile automata to fundamental physics and quantum gravity have been recently suggested, but other application areas are envisaged as well.
Subject Digital physics
Network mobile automaton
Trivalent graph
Pseudo-randomness
two-dimensional Turing machine
F.1.1 Models of Computation


Icona documento 1) Download Document PDF


Icona documento Open access Icona documento Restricted Icona documento Private

 


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional