### Abstract

We study regularly controlled bidirectional (RCB) grammars from the viewpoint of time-bounded grammars. RCB-grammars are context-free grammars of which the rules can be used in a productive and in a reductive fashion, while the application of these rules is controlled by a regular language. Several modes of derivation can be distinguished for this kind of grammar. A time-bound on such a grammar is a measure of its derivational complexity. For some families of time bounds and for some modes of derivation we establish closure properties and a normal form theorem. In addition parsing algorithms are given for some modes of derivation. We conclude with considering generalizations with respect to the family of control languages and the family of bounding functions.

Original language | Undefined |
---|---|

Place of Publication | Enschede |

Publisher | University of Twente, Department of Computer Science |

Number of pages | 26 |

Publication status | Published - 1988 |

### Publication series

Name | Memoranda Informatica |
---|---|

Publisher | University of Twente, Department of Computer Science |

No. | INF-88-53 |

ISSN (Print) | 0923-1714 |

### Keywords

- EWI-10889
- IR-64291
- HMI-SLT: Speech and Language Technology

## Cite this

Hogendorp, J. A. (1988).

*Time-Bounded Controlled Bidirectional Grammars*. (Memoranda Informatica; No. INF-88-53). Enschede: University of Twente, Department of Computer Science.