FAST RECOGNITION OF DETERMINISTIC CFLS WITH A SMALLER NUMBER OF PROCESSORS

Authors
MONIEN B RYTTER W SCHAPERS L
Citation
B. Monien et al., FAST RECOGNITION OF DETERMINISTIC CFLS WITH A SMALLER NUMBER OF PROCESSORS, Theoretical computer science, 116(2), 1993, pp. 421-429
Citations number
10
Categorie Soggetti
Computer Sciences","Computer Applications & Cybernetics",Mathematics
Journal title
Theoretical computer science → ACNP
ISSN journal
03043975
Volume
116
Issue
2
Year of publication
1993
Pages
421 - 429
Database
ISI
SICI code
0304-3975(1993)116:2<421:FRODCW>2.0.ZU;2-9
Abstract
The number of processors needed to recognize deterministic cfl's in lo garithmic time on a CREW PRAM is reduced to n2+epsilon for arbitrarily small 0 < epsilon < 1. A simplified version of the Klein-Reif algorit hm is also presented.