Parallel parsing on a one-way linear array of finite-state machines (Q1183569)

An one-way linear iterative array (OLIA) for inputs of length \(n\) consists of \(n\) finite state machines which operate synchronously and which communicate linearly: the state and the output of a machine (excepting the leftmost) at time \(t\) depends on its state and the state of its left neighbor at time \(t-1\). The inputs and the outputs of an OLIA are serial. The paper shows that the following three problems can be solved in linear time on an OLIA: --- parsing of discrete two-tape nondeterministic finite state transductions, --- parsing of linear context-free languages (as a consequence of the former), --- parsing of languages accepted by nondeterministic one-counter automata. We remark the way chosen for the presentation: firstly, it is shown how an OLIA can be simulated efficiently by sequential machine and then all algorithms are presented in terms of sequential machines. This gives clearness and legibility to the text.