Prefix Computations on Iterative Arrays with Sequential Input/Output Mode(<Special Section>Cellular Automata)

概要

論文の詳細を見る
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 a_1a_2・・・a_i ・・・, generates the values of X_L(a_1),X_L(a_1a_2),・・・,X_L(a_1a_2 ・・・a_i),・・・ at steps 4, 16,・・・,4i^2,・・・, respectively. Here,X_L : Σ^* → {0,1} is the characteristic function of the language L ⊆ Σ^*, defined as X_L(W) = 1 iff w ∈ L. We also construct 2i^3-time and i^4-time prefix algorithms for languages accepted by quadratic-time and cubic-time IAs, respectively.
社団法人電子情報通信学会の論文
2004-03-01