Geometric problems on two-dimensional array processors (Q1104746): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
| Property / cites work | |||
| Property / cites work: An efficient algorithm for determining the convex hull of a finite planar set / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Mesh computer algorithms for computational geometry / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: A Self-Routing Benes Network and Parallel Permutation Algorithms / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Optimal Three-Layer Channel Routing / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Sorting on a mesh-connected parallel computer / rank | |||
Normal rank | |||
Latest revision as of 17:49, 18 June 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
