Geometric problems on two-dimensional array processors
type: Item
instance of: scholarly article
title: Geometric problems on two-dimensional array processors
zbMATH Open document ID: 0647.68039
DOI: 10.1007/BF01602097
author: Mi Lu
author: Peter J. Varman
published in: Circuits, Systems, and Signal Processing
publication date: 1988-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68W99
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68N99
Mathematics Subject Classification ID: 62-04
zbMATH DE Number: 4056998
zbMATH Keywords: Parallel algorithms
zbMATH Keywords: geometric problems
zbMATH Keywords: two array processor models
zbMATH Keywords: mesh-connected computer
zbMATH Keywords: two-dimensional systolic array
zbMATH Keywords: regular languages
zbMATH Keywords: non-regular languages
MaRDI profile type: Publication
cites work: An efficient algorithm for determining the convex hull of a finite planar set
cites work: Mesh computer algorithms for computational geometry
cites work: A Self-Routing Benes Network and Parallel Permutation Algorithms
cites work: Optimal Three-Layer Channel Routing
cites work: Sorting on a mesh-connected parallel computer
description: scientific article; zbMATH DE number 4056998