recentpopularlog in

computer-science

« earlier   
[1208.2764] Linear functional classes over cellular automata
Cellular automata are a discrete dynamical system which models massively parallel computation. Much attention is devoted to computations with small time complexity for which the parallelism may provide further possibilities. In this paper, we investigate the ability of cellular automata related to functional computation. We introduce several functional classes of low time complexity which contain "natural" problems. We examine their inclusion relationships and emphasize that several questions arising from this functional framework are related to current ones coming from the recognition context. We also provide a negative result which explicits limits on the information transmission whose consequences go beyond the functional point of view.
cellular-automata  formal-languages  rather-interesting  computer-science  computability  to-understand 
yesterday by Vaguery
[1610.00331] Comparing 1D and 2D Real Time on Cellular Automata
We study the influence of the dimension of cellular automata (CA) for real time language recognition of one-dimensional languages with parallel input. Specifically, we focus on the question of determining whether every language that can be recognized in real time on a 2-dimensional CA working on the Moore neighborhood can also be recognized in real time by a 1-dimensional CA working on the standard two-way neighborhood.
We show that 2-dimensional CA in real time can perform a linear number of simulations of a 1-dimensional real time CA. If the two classes are equal then the number of simulated instances can be polynomial.
cellular-automata  rather-interesting  alternative-computational-models  distributed-processing  computer-science  universality  representation  feature-construction  engineering-design  to-write-about 
yesterday by Vaguery
[1208.2771] A Universal Semi-totalistic Cellular Automaton on Kite and Dart Penrose Tilings
In this paper we investigate certain properties of semi-totalistic cellular automata (CA) on the well known quasi-periodic kite and dart two dimensional tiling of the plane presented by Roger Penrose. We show that, despite the irregularity of the underlying grid, it is possible to devise a semi-totalistic CA capable of simulating any boolean circuit on this aperiodic tiling.
cellular-automata  tiling  computer-science  universality  rather-interesting  to-write-about  to-simulate 
yesterday by Vaguery
ossu/computer-science: Path to a free self-taught education in Computer Science!
computer-science - :mortar_board: Path to a free self-taught education in Computer Science!
computer-science 
4 days ago by yeltsin
GitHub - ossu/computer-science: Path to a free self-taught education in Computer Science!
computer-science - :mortar_board: Path to a free self-taught education in Computer Science!
computer-science 
4 days ago by yeltsin

Copy this bookmark:





to read