Document - A pseudo-random network mobile automaton with linear growth

2009

Journal article Restricted

A pseudo-random network mobile automaton with linear growth

Bolognesi T.

Digital physics F.1.1 Models of Computation Information Systems Pseudorandom numbers Pseudo-randomness two-dimensional Turing machine 37B15 Cellular automata Signal Processing Computer Science Applications Trivalent graph Theoretical Computer Science Network mobile automaton Graph algorithms

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.

Source: Information processing letters (Print) 109 (2009): 668–674. doi:10.1016/j.ipl.2009.02.023

Publisher: Elsevier Science, Amsterdam , Paesi Bassi

Metrics

Back to previous page

Cite as

BibTeX entry

@article{oai:it.cnr:prodotti:44244,
	title = {A pseudo-random network mobile automaton with linear growth},
	author = {Bolognesi T.},
	publisher = {Elsevier Science, Amsterdam , Paesi Bassi},
	doi = {10.1016/j.ipl.2009.02.023},
	journal = {Information processing letters (Print)},
	volume = {109},
	pages = {668–674},
	year = {2009}
}