Geometric problems on two-dimensional array processors (Q1104746): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claim: author (P16): Item:Q818671 |
||
Property / author | |||
Property / author: Peter J. Varman / rank | |||
Revision as of 02:05, 21 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Geometric problems on two-dimensional array processors |
scientific article |
Statements
Geometric problems on two-dimensional array processors (English)
0 references
1988
0 references
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.
0 references
Parallel algorithms
0 references
geometric problems
0 references
two array processor models
0 references
mesh-connected computer
0 references
two-dimensional systolic array
0 references
regular languages
0 references
non-regular languages
0 references