TY - BOOK

T1 - Regularly Controlled Bidirectional Extended Linear Basic Grammars (Revised and extended version)

AU - Hogendorp, Jan Anne

N1 - The number of pages refers to the original paper version; the recently produced PDF-file is more compact.

PY - 1989

Y1 - 1989

N2 - We study the concept of bidirectional application of productions -- i.e., using a production of a grammar as a reduction too -- with respect to regularly controlled extended linear basic (macro) grammars [3], provided with a restricted mode of derivation. So this new grammatical model is in essence equal to the regularly controlled bidirectional context-free grammar of [15] in which the underlying context-free grammar is replaced by an extended linear basic grammar. We establish closure properties of the corresponding family of languages; viz. for the outside-in or OI mode we obtain a full substitution-closed AFL, and for the inside-out or IO mode we obtain a full QAFL closed under deterministic substitution. The notion of bidirectionality gives rise to a dramatic increase of generating power; even under minor assumptions the OI [IO] instance of such grammars generate all OI-macro [IO-macro, respectively] languages. Furthermore, in case of free application of productions and reductions we obtain a generating capacity equal to the one of phrase-structure grammars.
[3] P.R.J. Asveld & J. Engelfriet, Extended linear macro grammars, iteration grammars, and register programs, Acta Informatica 11 (1979) 259-285.
[15] J.A. Hogendorp, Controlled bidirectional grammars, Internat. J. of Computer Mathematics 27 (1989) 159-180.

AB - We study the concept of bidirectional application of productions -- i.e., using a production of a grammar as a reduction too -- with respect to regularly controlled extended linear basic (macro) grammars [3], provided with a restricted mode of derivation. So this new grammatical model is in essence equal to the regularly controlled bidirectional context-free grammar of [15] in which the underlying context-free grammar is replaced by an extended linear basic grammar. We establish closure properties of the corresponding family of languages; viz. for the outside-in or OI mode we obtain a full substitution-closed AFL, and for the inside-out or IO mode we obtain a full QAFL closed under deterministic substitution. The notion of bidirectionality gives rise to a dramatic increase of generating power; even under minor assumptions the OI [IO] instance of such grammars generate all OI-macro [IO-macro, respectively] languages. Furthermore, in case of free application of productions and reductions we obtain a generating capacity equal to the one of phrase-structure grammars.
[3] P.R.J. Asveld & J. Engelfriet, Extended linear macro grammars, iteration grammars, and register programs, Acta Informatica 11 (1979) 259-285.
[15] J.A. Hogendorp, Controlled bidirectional grammars, Internat. J. of Computer Mathematics 27 (1989) 159-180.

KW - IR-64295

KW - HMI-SLT: Speech and Language Technology

KW - EWI-10899

M3 - Report

T3 - Memoranda Informatica

BT - Regularly Controlled Bidirectional Extended Linear Basic Grammars (Revised and extended version)

PB - University of Twente, Department of Computer Science

CY - Enschede

ER -