English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The aim of this paper is to prove that the system of simple graph grammars (Einfache Graph-Grammatiken) in[1]is complete. A graph grammar is a generalization of a Chomsky-grammar which defines a graph language, i.e。a language composed of a set of directed graphs with labelled nodes and arcs。 A system of graph grammars is said to be complete if it satisfies the following property: For each finite set T of labels, the class of all graph languages over T defined by graph grammars of the system is identical with the class of ail recussively enumerable sets of labelled graphs over T. Where a set of labelled graphs over T is recursively enumerable if the associated set of integers by a Godel numbering from the labelled graphs over T into the integers is recursively enumerable。 Several authors have introduced their system of graph grammars (e・g.[11,[21, [31,[41,[51,[6j,[7])。However they did not refer to the completeness of their systems。 The system of simple graph grammars was introduced in[1]as a subsystem of the system in [2]。In this paper we modify the definition of the system in the following manner: A production of our system is an ordered triple(K,F,K’)which consists of two labelled graphs 瓦A7 and a one・to・one function F from a set of nodes of 瓦to a set of nodes of K'. If iK, F, m is a production, and if K occurs in a labelled graph G, then the production is applicable to G, and the effect of the application is to replace an occurrence of K in G by 瓦へ The function F specifies the embedding of 瓦7into the remainder of removing K from G; if a node n' of K' is the image of a node n of K, thenがis put upon the trace of n in the remainder. This is illustrated by Figure O。 The formal definitions of labelled graphs and several concepts with labelled graphs are given in the first section of this paper. The definition of simple graph grammars is given in the second section. In the third section it is proved that the system of simple graph grammars is complete. The final section gives a generalization of the system of simple graph grammars.

A system of graph grammars which generates all recursively enumerable sets of labelled graphs