## Abstract

An optimal parallel recognition/parsing algorithm is presented for languages generated by tree adjoining grammars (TAGs), a grammatical system for natural language. TAGs are strictly more powerful than context-free grammars (CFGs), e.g., they can generate {a″b″c″|n≥0}, which is not context-free. However, serial parsing of TAGs is also slower, having time complexity O(n^{6}) for inputs of length n (as opposed to O(n^{3}) for CFGs). The parallel algorithm achieves optimal speedup: it runs in linear time on a five-dimensional array of n^{5} processors. Moreover, the processors are finite-state; i.e., their function and size depends only on the underlying grammar and not on the length of the input.

Original language | English (US) |
---|---|

Pages (from-to) | 1-31 |

Number of pages | 31 |

Journal | SIAM Journal on Computing |

Volume | 19 |

Issue number | 1 |

DOIs | |

State | Published - 1990 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- Computer Science(all)
- Mathematics(all)