2026-07-20T12:07:27Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:3017 2024-03-06T10:33:44Z ddc:004 open_access

A speed-up of oblivious multi-head finite automata by cellular automata Borelllo, Alex Richard, Gaetan Terrier, Veronique oblivious multi-head finite automata cellular automata parallel speed-up simulation 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))$. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Alex Borelllo and Gaetan Richard and Veronique Terrier 2011 Is Part Of LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2011.273 urn:nbn:de:0030-drops-30172 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.273 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode