Deterministic graph grammars - Archive ouverte HAL Accéder directement au contenu
Chapitre D'ouvrage Année : 2008

Deterministic graph grammars

Didier Caucal

Résumé

Context-free grammars are one of the most classical and fundamental notions in computer science textbooks, in both theoretical and applied settings. As characterizations of the well-known class of context-free languages, they are a very prominent tool in the field of language theory. Since context-free grammars are powerful enough to express most programming languages, they also play an important role in compilation, where they form the basis of many efficient parsing algorithms. A similar notion can be adapted to the more general setting of grammars generating graphs instead of words. In this case, grammar rules no longer express the replacement of a non-terminal letter by a string of terminal and non-terminal letters, but that of a non-terminal arc (or more generally hyperarc) by a finite graph (or hypergraph) possibly containing new nonterminals, thus generating larger and larger graphs. In this paper, we are concerned with the specific setting where the considered sets of grammar rules are deterministic, meaning that there is only one production rule for every non-terminal hyperarc.
Fichier principal
Vignette du fichier
birthday.pdf (662.17 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-00867578 , version 1 (30-09-2013)

Identifiants

  • HAL Id : hal-00867578 , version 1

Citer

Didier Caucal. Deterministic graph grammars. Jörg Flum, Erich Grädel, Thomas Wilke. Logic and Automata - History and Perspectives, Amsterdam University Press, pp.169-250, 2008, Texts in Logic and Games, 9789053565766. ⟨hal-00867578⟩
181 Consultations
117 Téléchargements

Partager

Gmail Facebook X LinkedIn More