A portfolio of classification problems by one-dimensional cellular automata, over cyclic binary configurations and parallel update
Montalva-Medel
M
author
de Oliveira
P
P
B
author
Goles
E
author
2018
English
Decision problems addressed by cellular automata have been historically expressed either as determining whether initial configurations would belong to a given language, or as classifying the initial configurations according to a property in them. Unlike traditional approaches in language recognition, classification problems have typically relied upon cyclic configurations and fully paralell (two-way) update of the cells, which render the action of the cellular automaton relatively less controllable and difficult to analyse. Although the notion of cyclic languages have been studied in the wider realm of formal languages, only recently a more systematic attempt has come into play in respect to cellular automata with fully parallel update. With the goal of contributing to this effort, we propose a unified definition of classification problem for one-dimensional, binary cellular automata, from which various known problems are couched in and novel ones are defined, and analyse the solvability of the new problems. Such a unified perspective aims at increasing existing knowledge about classification problems by cellular automata over cyclic configurations and parallel update.
One-dimensional cellular automata
Classification problem
Decision problem
Language recognition
Density
Parity
Emergent computation
WOS:000441986000016
exported from refbase (show.php?record=908), last updated on Thu, 22 Nov 2018 13:26:34 -0300
text
files/863_Montalva-Medel_etal2018.pdf
10.1007/s11047-017-9650-1
Montalva-Medel_etal2018
Natural Computing
Nat. Comput.
2018
Springer
continuing
periodical
academic journal
17
3
663
671
1567-7818