Istituto di Scienza e Tecnologie dell'Informazione     
Bolognesi T. A pseudo-random network mobile automation with linear growth. In: Information Processing Letters, vol. 109 (13) pp. 668 - 674. Elsevier, 2009.
Based on the mobile automaton model, an algorithm is introduced that grows planar, tri-valent graphs by exhibiting a peculiar, twofold dynamics. In a first phase, graph growth appears to be pseudo-random and O(n); then it settles to a very regular behavior and O(Sqrt(n)) rate. A pseudo-random O(Sqrt(n)) mobile automaton is already known; the new automaton provides now a finite, but surprisingly long, pseudo-random, linear growth process. Applications of mobile automata to fundamental physics and quantum gravity have been recently suggested.
URL: http://www.sciencedirect.com/science?_ob=PublicationURL&_tockey=%23TOC%235645%232009%23998909986%231024726%23FLP%23&_cdi=5645&_pubType=J&_auth=y&_acct=C000061181&_version=1&_urlVersion=0&_userid=3967543&md5=3c91b9810348700a571f78050d58c742
DOI: 10.1016/j.ipl.2009.02.023
Subject Graph algorithms
Pseudorandom numbers
Cellular automata
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