Time-bounded controlled bidirectional grammars

Jan Anne Hogendorp

    Research output: Contribution to journalArticleAcademicpeer-review

    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 languageEnglish
    Pages (from-to)93-115
    Number of pages23
    JournalInternational journal of computer mathematics
    Volume35
    Issue number1-4
    DOIs
    Publication statusPublished - 1990

    Fingerprint

    Dive into the research topics of 'Time-bounded controlled bidirectional grammars'. Together they form a unique fingerprint.

    Cite this