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

Borelllo, Alex; Richard, Gaetan; Terrier, Veronique

doi:10.4230/LIPIcs.STACS.2011.273

Document

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

Authors Alex Borelllo, Gaetan Richard, Veronique Terrier

Part of: Volume: 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)
Part of: Series: Leibniz International Proceedings in Informatics (LIPIcs)
Part of: Conference: Symposium on Theoretical Aspects of Computer Science (STACS)
License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
Publication Date: 2011-03-11

PDF

File

PDF

LIPIcs.STACS.2011.273.pdf

Filesize: 1.2 MB
11 pages

Document Identifiers

DOI: 10.4230/LIPIcs.STACS.2011.273
URN: urn:nbn:de:0030-drops-30172

Subject Classification

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

0

Metadata Views

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))$.

Cite As Get 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

Author Details

Alex Borelllo

Gaetan Richard

Veronique Terrier

Questions / Remarks / Feedback

Feedback for Dagstuhl Publishing

Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail

	
		OSZAR »