General context-free recognition in less
β
Leslie G. Valiant
π
Article
π
1975
π
Elsevier Science
π
English
β 306 KB
An algorithm for general context-free recognition is given that requires less than n 3 time asymptotically for input strings of length n. ## Introduction By a succession of reductions we show that context-free recognition, for n character input strings, can be carried out at least as fast as multi