Name
Abstract | ||
|---|---|---|
We investigate the complexity of images generated by a class of parallel context-free image grammars. We show that the sequential time complexity of the recognition of n x n images generated by parallel context-free grammars is O(M(n)), where M(n) is the time to multiply two boolean n x n matrices. Using a parallel random access machine the recognition can be done in O(log2(n)) time with n6 processors. Hence the complexity is essentially the same as the complexity of the recognition of ordinary context-free languages. |
Year | DOI | Venue |
|---|---|---|
1991 | 10.1016/0020-0190(91)90063-N | Inf. Process. Lett. |
Keywords | Field | DocType |
PARALLEL ALGORITHMS, IMAGES, CONTEXT-FREE GRAMMARS | Rule-based machine translation,Discrete mathematics,Sequential time,Combinatorics,Context-free grammar,Algorithm complexity,Parallel random-access machine,Parallel algorithm,Computer science,Matrix (mathematics),Time complexity | Journal |
Volume | Issue | ISSN |
38 | 5 | 0020-0190 |
Citations | PageRank | References |
2 | 0.36 | 2 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| wojciech rytter | 1 | 130 | 17.13 |
| A. Saoudi | 2 | 2 | 0.36 |