Geometric problems on two-dimensional array processors (Q1104746)

Parallel algorithms for solving geometric problems on two array processor models - the mesh-connected computer (MCC) and a two-dimensional systolic array - are presenteg n) space. Theorem 3. If an \(\omega\)-language is not recognizable by a FDA then it cannot be recognized by a 2-way TM in o(log log n) space. Furthermore, theorems 1-3 show that there are complexity gaps between regular and non-regular languages. It is proved that for probabilistic TM there is no complexity gap between regular and non-regular languages.