A Simulation of Oblivious Multi-Head One-Way Finite Automata by Real-Time Cellular Automata

Details A Simulation of Oblivious Multi-Head One-Way Finite Automata by Real-Time Cellular Automata A Simulation of Oblivious Multi-Head One-Way Finite Automata by Real-Time Cellular Automata

2010-12-03

arxiv.org/abs/1012.1219v1

Nonlinear Sciences

Cellular Automata and Lattice Gases

Journ\'ees Automates Cellulaires 2010, Turku : Finland (2010)

Scientific paper

In this paper, we present the simulation of a simple, yet significantly powerful, sequential model by cellular automata. The simulated model is called oblivious multi-head one-way finite automata and is characterized by having its heads moving only forward, on a trajectory that only depends on the length of the input. While the original finite automaton works in linear time, its corresponding cellular automaton performs the same task in real time, that is, exactly the length of the input. Although not truly a speed-up, the simulation may be interesting and reminds us of the open question about the equivalence of linear and real times on cellular automata.

Affiliated with

Also associated with

No associations

Rating

A Simulation of Oblivious Multi-Head One-Way Finite Automata by Real-Time Cellular Automata does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Simulation of Oblivious Multi-Head One-Way Finite Automata by Real-Time Cellular Automata, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Simulation of Oblivious Multi-Head One-Way Finite Automata by Real-Time Cellular Automata will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-515721