Document - Nominal cellular automata

2016

Conference article Open Access

Nominal cellular automata

Bolognesi T., Ciancia V.

Computer Science - Formal Languages and Automata Theory FOS: Computer and information sciences Nominal Sets Modes of Computation Computer Science - Logic in Computer Science Nominal Computation Theory Formal Languages and Automata Theory (cs.FL) FOS: Physical sciences Logic in Computer Science (cs.LO) Cellular Automata and Lattice Gases (nlin.CG) Cellular Automata Nonlinear Sciences - Cellular Automata and Lattice Gases

The emerging field of Nominal Computation Theory is concerned with the theory of Nominal Sets and its applications to Computer Science. We investigate here the impact of nominal sets on the definition of Cellular Automata and on their computational capabilities, with a special focus on the emergent behavioural properties of this new model and their significance in the context of computation-oriented interpretations of physical phenomena. A preliminary investigation of the relations between Nominal Cellular Automata and Wolfram's Elementary Cellular Automata is also carried out.

Source: ICE 2016 - 9th Interaction and Concurrency Experience, pp. 24–35, Heraklion, Crete, Greece, 8-9 June 2016

Citations

[1] Mikołaj Bojan´czyk, Bartek Klin & Slawomir Lasota (2011): Automata with Group Actions. In: LICS, IEEE Computer Society, pp. 355-364, doi:10.1109/LICS.2011.48.
[2] Mikołaj Bojan´czyk, Bartek Klin, Slawomir Lasota & Szymon Torun´czyk (2013): Turing Machines with Atoms. In: LICS, IEEE Computer Society, pp. 183-192, doi:10.1109/LICS.2013.24.
[3] Matthew Cook (2004): Universality in Elementary Cellular Automata. Complex Systems 15(1), pp. 1-40.
[4] Murdoch Gabbay & Andrew M. Pitts (1999): A New Approach to Abstract Syntax Involving Binders. In: LICS, IEEE Computer Society, pp. 214-224, doi:10.1109/LICS.1999.782617.
[5] Murdoch James Gabbay & Vincenzo Ciancia (2011): Freshness and Name-Restriction in Sets of Traces with Names. In: FOSSACS, LNCS 6604, Springer, pp. 365-380, doi:10.1007/978-3-642-19805-2 25.
[6] Andrew Ilachinski (2001): Cellular Automata - A Discrete Universe. World Scientific, doi:10.1142/4702.
[7] Dexter Kozen, Konstantinos Mamouras, Daniela Petrisan & Alexandra Silva (2015): Nominal Kleene Coalgebra. In: ICALP, LNCS 9135, Springer, pp. 286-298, doi:10.1007/978-3-662-47666-6 23.
[8] Ugo Montanari & Marco Pistore (2000): pi-Calculus, Structured Coalgebras, and Minimal HD-Automata. In: MFCS, LNCS 1893, pp. 569-578, doi:10.1007/3-540-44612-5 52.
[9] Stephen Wolfram (1984): Cellular Automata as Models of Complexity. doi:10.1038/311419a0.
[10] Stephen Wolfram (2002): A New Kind of Science. Wolfram Media, Inc.
[11] K. Zuse (1970): Calculating space. Technical Report, Proj, MAC, MIT, Cambridge, Mass. Technical Translation AZT-70-164-GEMIT. Original title: ”Rechnender Raum”.
Nature 311(4), pp. 419-424,

Metrics

Back to previous page

Cite as

BibTeX entry

@inproceedings{oai:it.cnr:prodotti:357987,
	title = {Nominal cellular automata},
	author = {Bolognesi T. and Ciancia V.},
	doi = {10.4204/eptcs.223.2 and 10.48550/arxiv.1608.03320},
	booktitle = {ICE 2016 - 9th Interaction and Concurrency Experience, pp. 24–35, Heraklion, Crete, Greece, 8-9 June 2016},
	year = {2016}
}