Сильно ациклическая грамматика: различия между версиями

'''Сильно ациклическая грамматика''' (''[[Strongly non-circular grammar]]'') -

частичных порядков <math>\{ R(X):X\in N\}</math>, что справедливы

1) (''ацикличность'') для любой продукции <math>p\in P</math> является

ациклическим

<math>R(X_1)\cup\ldots\cup R(X_{n<p>})\cup D(p),</math>

где <math>D(p)</math> --- ''[[граф локальной зависимости]]'';

2) (''замкнутость'') для любой продукции <math>p\in P</math> --- ограничение

<math>A(X_0)</math> является подмножеством <math>R(X_0)</math>, т.е.

<math>[R(X_1)\cup\ldots\cup R(X_{n<p>})\cup D(p)]_{X_0}^+\subseteq R(X_0).</math>

минимальных <math>R(X)</math> для

'''С.а.г.'''

'''С.а.г.''', является то, что реальные

индуцированные <math>R(t)</math> в [[дерево|дереве]] <math>t</math> с [[корень|корнем]] <math>X</math>, покрываются

<math>R(X)</math>. Поэтому

функций, рекурсивно определенных над структурой дерева <math>t</math>.

Одно из преимуществ вычислителя '''С.а.г.''' --- то, что он

экспоненциальной от размера <math>W(t)</math>, если не поддерживается

для <math>S</math>-грамматик). Некоторые экспериментальные исследования

'''С.а.г.''' и <math>l</math>-упорядоченных грамматик показали их

Другие названия --- ''[[Абсолютно ациклическая грамматика]], [[ANC-Грамматика|<math>ANC</math>-грамматика]], [[SNC-Грамматика|<math>SNC</math>-грамматика]]''.

'' [[l-Упорядоченные грамматики|<math>l</math>-Упорядоченные грамматики]], [[Чисто синтезированные грамматики]].''

[Евстигнеев-Касьянов/98]