Translating Controlled Graph Grammars to Ordinary Graph Grammars | Zendy

Alex Bertei | Zendy; Luciana Foss | Zendy; Simone André da Costa Cavalheiro | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Translating Controlled Graph Grammars to Ordinary Graph Grammars

Author(s) -

Alex Bertei,

Luciana Foss,

Simone André da Costa Cavalheiro

Publication year - 2016

Publication title -

electronic notes in theoretical computer science

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.242

H-Index - 60

ISSN - 1571-0661

DOI - 10.1016/j.entcs.2016.09.004

Subject(s) - computer science , l attributed grammar , context sensitive grammar , graph rewriting , programming language , tree adjoining grammar , null graph , theoretical computer science , rule based machine translation , adaptive grammar , graph property , context free grammar , graph , voltage graph , natural language processing , line graph , artificial intelligence , mildly context sensitive grammar formalism , phrase structure rules , generative grammar

Graph Grammar (GG) is an appropriate formal language for specifying complex systems. In a GG the system states are represented by graphs and the changes between the states are described by rules. The use of GGs is interesting as there are several techniques for the specification and verification of systems that are described in this language. Besides this, GGs have a graphical representation which is quite intuitive, making the language easy to understand even for non-theorists. Controlled graph grammars (CGGs) are GGs that allow defining a sequence of rule applications, considering an auxiliary control structure, allowing one to control the intrinsic non-determinism of this formalism. However, for this type of grammar there are no tools for verification of properties. Therefore, the aim of this paper is to translate the controlled graph grammars into ordinary graph grammars, transferring the flow control from an auxiliary structure to the state. Hence, the main contribution of this paper is to permit the use of Rodin theorem prover to carry out the verification of properties for CGG specifications. This is possible through a mechanism where a controlled graph grammar is translated into a regular graph grammar using dependencies and conflicts between rules

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research