Confluent NCE graph grammar: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
 
Строка 1: Строка 1:
'''Confluent NCE graph grammar''' --- конфлуентная графовая
'''Confluent NCE graph grammar''' — ''[[конфлуентная графовая грамматика типа NCE]].''
грамматика типа NCE.  


An ''NCE graph grammar'' <math>{\mathcal G}</math> is '''confluent''' (C-NCE) if
An ''[[NCE graph grammar]]'' <math>\mathcal {G}</math> is '''confluent''' (C-NCE) if
for every graph <math>G</math> derivable (see '' Derivation'') from the axiom of
for every [[graph, undirected graph, nonoriented graph|graph]] <math>\,G</math> derivable (see '' [[Derivation]]'') from the axiom of <math>\mathcal {G}</math>, all nonterminal [[node|nodes]] <math>\,u, v</math> in <math>\,G</math>, and all productions <math>\,(\phi(u),H,D), \; (\phi(v),J,F)</math> in <math>{\mathcal G}</math> we have:
<math>{\mathcal G}</math>, all nonterminal nodes <math>u, v</math> in <math>G</math>, and all productions
<math>(\phi(u),H,D), \; (\phi(v),J,F)</math> in <math>{\mathcal G}</math> we have:


<math>G[u/_{D} H][v/_{F} J] = G[v/_{F} J][u/_{D} H].</math>
<math>\,G[u/_{D} H][v/_{F} J] = G[v/_{F} J][u/_{D} H].</math>


In the confluent graph grammar, the order in which the productions are
In the confluent graph grammar, the order in which the productions are applied is irrelevant for the resulting graph.
applied is irrelevant for the
 
resulting graph.
==Литература==
 
* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.

Текущая версия от 10:48, 24 октября 2018

Confluent NCE graph grammarконфлуентная графовая грамматика типа NCE.

An NCE graph grammar [math]\displaystyle{ \mathcal {G} }[/math] is confluent (C-NCE) if for every graph [math]\displaystyle{ \,G }[/math] derivable (see Derivation) from the axiom of [math]\displaystyle{ \mathcal {G} }[/math], all nonterminal nodes [math]\displaystyle{ \,u, v }[/math] in [math]\displaystyle{ \,G }[/math], and all productions [math]\displaystyle{ \,(\phi(u),H,D), \; (\phi(v),J,F) }[/math] in [math]\displaystyle{ {\mathcal G} }[/math] we have:

[math]\displaystyle{ \,G[u/_{D} H][v/_{F} J] = G[v/_{F} J][u/_{D} H]. }[/math]

In the confluent graph grammar, the order in which the productions are applied is irrelevant for the resulting graph.

Литература

  • Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.