A speed-up of oblivious multi-head finite automata by cellular automata

Authors Alex Borelllo, Gaetan Richard, Veronique Terrier



PDF
Thumbnail PDF

File

LIPIcs.STACS.2011.273.pdf
  • Filesize: 1.2 MB
  • 11 pages

Document Identifiers

Author Details

Alex Borelllo
Gaetan Richard
Veronique Terrier

Cite AsGet BibTex

Alex Borelllo, Gaetan Richard, and Veronique Terrier. A speed-up of oblivious multi-head finite automata by cellular automata. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 273-283, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)
https://doi.org/10.4230/LIPIcs.STACS.2011.273

Abstract

In this paper, we present a parallel speed-up of a simple, yet significantly powerful, sequential model by cellular automata. The simulated model is called oblivious multi-head finite automata and is characterized by the fact that the trajectory of the heads only depends on the length of the input word. While the original $k$-head finite automaton works in time $O(n^k)$, its corresponding cellular automaton performs the same task in time $O(n^(k-1)log(n))$ and space $O(n^(k - 1))$.
Keywords
  • oblivious multi-head finite automata
  • cellular automata
  • parallel speed-up
  • simulation

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail