Affordable Access

The structure of index sets and reduced indexed grammars

Publication Date
  • Law


The structure of index sets and reduced indexed grammars INFORMATIQUE THÉORIQUE ET APPLICATIONS R. PARCHMANN J. DUSKE The structure of index sets and reduced indexed grammars Informatique théorique et applications, tome 24, no 1 (1990), p. 89- 104. <> © AFCET, 1990, tous droits réservés. L’accès aux archives de la revue « Informatique théorique et applications » im- plique l’accord avec les conditions générales d’utilisation (http://www.numdam. org/legal.php). Toute utilisation commerciale ou impression systématique est constitutive d’une infraction pénale. Toute copie ou impression de ce fichier doit contenir la présente mention de copyright. Article numérisé dans le cadre du programme Numérisation de documents anciens mathématiques Informatique théorique et Applications/Theoretical Informaties and Applications (vol. 24, n° 1, 1990, p. 89 à 104) THE STRUCTURE OF INDEX SETS AND REDUCED INDEXED GRAMMARS (*) by R. PARCHMANN (*) and J. DUSKE (*) Communicated by J. BERSTEL Abstract. - The set of index words attached to a variable in dérivations of indexed grammars is investigated. Using the regularity of these sets it is possible to transform an mdexed grammar in a reducedfrom and to describe the structure ofleft sentential forms of an indexed grammar. Résumé. - On étudie Vensemble des mots d'index d'une variable dans les dérivations d'une grammaire d'index. La rationalité de ces ensembles peut être utilisée pour transformer une gram- maire d'index en forme réduite, et pour décrire la structure des mots apparaissant dans les dérivations gauches d'une grammaire d'index. 1. INTRODUCTION In this paper we will further investigate indexed grammars and languages introduced by Aho [1] as an extension of context-free grammars and lan- guages. This family of languages has many properties of the context-free languages and it is interesting to note how many of them can be carried over and which propert

There are no comments yet on this publication. Be the first to share your thoughts.


Seen <100 times

More articles like this

Self-embedding indexed grammars

on Theoretical Computer Science Jan 01, 1986


on Canadian Urological Associatio... April 2008
More articles like this..