Deterministic graph grammars

Abstract : 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.
Document type :
Book sections
Complete list of metadatas

https://hal-upec-upem.archives-ouvertes.fr/hal-00867578
Contributor : Didier Caucal <>
Submitted on : Monday, September 30, 2013 - 7:34:32 PM
Last modification on : Friday, July 13, 2018 - 4:00:04 PM
Long-term archiving on : Tuesday, December 31, 2013 - 4:25:15 AM

File

birthday.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00867578, version 1

Citation

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⟩

Share

Metrics

Record views

265

Files downloads

121