1-1hit |
Chuzo IWAMOTO Tomoka YOKOUCHI Kenichi MORITA Katsunobu IMAI
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