Prefix Computations on Iterative Arrays with Sequential Input/Output Mode

Chuzo IWAMOTO  Tomoka YOKOUCHI  Kenichi MORITA  Katsunobu IMAI  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E87-D   No.3   pp.708-712
Publication Date: 2004/03/01
Online ISSN: 
DOI: 
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Cellular Automata)
Category: 
Keyword: 
prefix computation,  iterative arrays,  language recognition,  

Full Text: PDF(312.1KB)>>
Buy this Article




Summary: 
This paper investigates prefix computations on Iterative Arrays (IAs) with sequential input/output mode. We show that, for any language L accepted by a linear-time IA, there is an IA which, given an infinite string a1a2 ai, generates the values of χL(a1),χL(a1a2),L(a1a2 ai), at steps 4,16,,4i2,, respectively. Here, χL*{0,1} is the characteristic function of the language L Σ*, defined as χL(w) = 1 iff w L. We also construct 2i3-time and i4-time prefix algorithms for languages accepted by quadratic-time and cubic-time IAs, respectively.