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

Материал из WikiGrapp
Перейти к навигации Перейти к поиску
(Новая страница: «'''Confluent NCE graph grammar''' --- конфлуентная графовая грамматика типа NCE. An ''NCE graph grammar'' <math>{\mathcal G}</mat…»)
 
Нет описания правки
 
(не показана 1 промежуточная версия 1 участника)
Строка 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 applied is irrelevant for the resulting graph.
 
==Литература==
 
* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.

Текущая версия от 13:45, 14 ноября 2014

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.