http://pco.iis.nsk.su/grapp/index.php?title=%D0%A1%D0%B8%D0%BB%D1%8C%D0%BD%D0%BE_%D0%B0%D1%86%D0%B8%D0%BA%D0%BB%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B0%D1%8F_%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0&feed=atom&action=history Сильно ациклическая грамматика - История изменений 2024-03-28T13:39:11Z История изменений этой страницы в вики MediaWiki 1.39.3 http://pco.iis.nsk.su/grapp/index.php?title=%D0%A1%D0%B8%D0%BB%D1%8C%D0%BD%D0%BE_%D0%B0%D1%86%D0%B8%D0%BA%D0%BB%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B0%D1%8F_%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0&diff=9578&oldid=prev KEV в 05:39, 2 сентября 2011 2011-09-02T05:39:39Z <p></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="ru"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Предыдущая версия</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Версия от 12:39, 2 сентября 2011</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1">Строка 1:</td> <td colspan="2" class="diff-lineno">Строка 1:</td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>&#039;&#039;&#039;Сильно ациклическая грамматика&#039;&#039;&#039; (&#039;&#039;[[Strongly non-circular grammar]]&#039;&#039;) <del style="font-weight: bold; text-decoration: none;">- </del></div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>&#039;&#039;&#039;Сильно ациклическая грамматика&#039;&#039;&#039; (&#039;&#039;[[Strongly non-circular grammar]]&#039;&#039;) <ins style="font-weight: bold; text-decoration: none;">— </ins></div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[атрибутная грамматика]], для которой существует такое семейство</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[атрибутная грамматика]], для которой существует такое семейство</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>частичных порядков &lt;math&gt;\{ R(X):X\in N\}&lt;/math&gt;<del style="font-weight: bold; text-decoration: none;">, </del>что справедливы</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>частичных порядков &lt;math&gt;\{ R(X):X\in N\}<ins style="font-weight: bold; text-decoration: none;">,</ins>&lt;/math&gt; что справедливы</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>следующие два условия:</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>следующие два условия:</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>1) (&#039;&#039;ацикличность&#039;&#039;) для любой продукции &lt;math&gt;p\in P&lt;/math&gt; является</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>1) (&#039;&#039;ацикличность&#039;&#039;) для любой продукции &lt;math&gt;p\in P&lt;/math&gt; является ациклическим</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>ациклическим</div></td><td colspan="2" class="diff-side-added"></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>&lt;math&gt;R(X_1)\cup\ldots\cup R(X_{n&lt;p&gt;})\cup D(p),&lt;/math&gt;</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">::</ins>&lt;math&gt;R(X_1)\cup\ldots\cup R(X_{n&lt;p&gt;})\cup D(p),&lt;/math&gt;</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>где &lt;math&gt;D(p)&lt;/math&gt; <del style="font-weight: bold; text-decoration: none;">--- </del>&#039;&#039;[[граф локальной зависимости]]&#039;&#039;;</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>где &lt;math&gt;<ins style="font-weight: bold; text-decoration: none;">\,</ins>D(p)&lt;/math&gt; <ins style="font-weight: bold; text-decoration: none;">— </ins>&#039;&#039;[[граф локальной зависимости]]&#039;&#039;;</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>2) (&#039;&#039;замкнутость&#039;&#039;) для любой продукции &lt;math&gt;p\in P&lt;/math&gt; <del style="font-weight: bold; text-decoration: none;">--- </del>ограничение</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>2) (&#039;&#039;замкнутость&#039;&#039;) для любой продукции &lt;math&gt;p\in P&lt;/math&gt; <ins style="font-weight: bold; text-decoration: none;">— </ins>ограничение</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>отношения &lt;math&gt;[R(X_1)\cup\ldots\cup R(X_{n&lt;p&gt;})\cup D(p)]^+&lt;/math&gt; на</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>отношения &lt;math&gt;[R(X_1)\cup\ldots\cup R(X_{n&lt;p&gt;})\cup D(p)]^+&lt;/math&gt; на</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>&lt;math&gt;A(X_0)&lt;/math&gt; является подмножеством &lt;math&gt;R(X_0)&lt;/math&gt;<del style="font-weight: bold; text-decoration: none;">, </del>т.е.</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>&lt;math&gt;<ins style="font-weight: bold; text-decoration: none;">\,</ins>A(X_0)&lt;/math&gt; является подмножеством &lt;math&gt;<ins style="font-weight: bold; text-decoration: none;">\,</ins>R(X_0)<ins style="font-weight: bold; text-decoration: none;">,</ins>&lt;/math&gt; т.е.</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>&lt;math&gt;[R(X_1)\cup\ldots\cup R(X_{n&lt;p&gt;})\cup D(p)]_{X_0}^+\subseteq R(X_0).&lt;/math&gt;</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">::</ins>&lt;math&gt;[R(X_1)\cup\ldots\cup R(X_{n&lt;p&gt;})\cup D(p)]_{X_0}^+\subseteq R(X_0).&lt;/math&gt;</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Существует полиномиальный алгоритм для вычисления семейства</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Существует полиномиальный алгоритм для вычисления семейства</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>минимальных &lt;math&gt;R(X)&lt;/math&gt; для</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>минимальных &lt;math&gt;<ins style="font-weight: bold; text-decoration: none;">\,</ins>R(X)&lt;/math&gt; для</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>&#039;&#039;&#039;<del style="font-weight: bold; text-decoration: none;">С.а.г.</del>&#039;&#039;&#039;</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>&#039;&#039;&#039;<ins style="font-weight: bold; text-decoration: none;">сильно ациклической грамматики</ins>&#039;&#039;&#039;<ins style="font-weight: bold; text-decoration: none;">.</ins></div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Наиболее интересной характеристикой грамматики,</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Наиболее интересной характеристикой грамматики,</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>принадлежащей к классу</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>принадлежащей к классу</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>&#039;&#039;&#039;<del style="font-weight: bold; text-decoration: none;">С.а.г.</del>&#039;&#039;&#039;, является то, что реальные</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>&#039;&#039;&#039;<ins style="font-weight: bold; text-decoration: none;">сильно ациклической грамматики</ins>&#039;&#039;&#039;, является то, что реальные</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>зависимости между  [[наследуемый атрибут|наследуемыми]] и [[синтезируемый атрибут|синтезируемыми атрибутами]],</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>зависимости между  [[наследуемый атрибут|наследуемыми]] и [[синтезируемый атрибут|синтезируемыми атрибутами]],</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>индуцированные &lt;math&gt;R(t)&lt;/math&gt; в [[дерево|дереве]] &lt;math&gt;t&lt;/math&gt; с [[корень|корнем]] &lt;math&gt;X&lt;/math&gt;, покрываются</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>индуцированные &lt;math&gt;<ins style="font-weight: bold; text-decoration: none;">\,</ins>R(t)&lt;/math&gt; в [[дерево|дереве]] &lt;math&gt;<ins style="font-weight: bold; text-decoration: none;">\,</ins>t&lt;/math&gt; с [[корень|корнем]] &lt;math&gt;<ins style="font-weight: bold; text-decoration: none;">\,</ins>X&lt;/math&gt;, покрываются</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>&lt;math&gt;R(X)&lt;/math&gt;. Поэтому</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>&lt;math&gt;<ins style="font-weight: bold; text-decoration: none;">\,</ins>R(X)&lt;/math&gt;. Поэтому</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>атрибутная грамматика эквивалентна множеству</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>атрибутная грамматика эквивалентна множеству</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>функций, рекурсивно определенных над структурой дерева &lt;math&gt;t&lt;/math&gt;.</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>функций, рекурсивно определенных над структурой дерева &lt;math&gt;<ins style="font-weight: bold; text-decoration: none;">\,</ins>t&lt;/math&gt;.</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Одно из преимуществ вычислителя &#039;&#039;&#039;<del style="font-weight: bold; text-decoration: none;">С.а.г.</del>&#039;&#039;&#039; <del style="font-weight: bold; text-decoration: none;">--- </del>то, что он</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>Одно из преимуществ вычислителя &#039;&#039;&#039;<ins style="font-weight: bold; text-decoration: none;">сильно ациклической грамматики</ins>&#039;&#039;&#039; <ins style="font-weight: bold; text-decoration: none;">— </ins>то, что он</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>нисходящий. Однако он может вычислять лишние наследуемые</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>нисходящий. Однако он может вычислять лишние наследуемые</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>атрибуты, и его временная сложность является</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>атрибуты, и его временная сложность является</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>экспоненциальной от размера &lt;math&gt;W(t)&lt;/math&gt;, если не поддерживается</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>экспоненциальной от размера &lt;math&gt;<ins style="font-weight: bold; text-decoration: none;">\,</ins>W(t)&lt;/math&gt;, если не поддерживается</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>информация о вычисленных переменных (та же ситуация, что и</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>информация о вычисленных переменных (та же ситуация, что и</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>для &lt;math&gt;S&lt;/math&gt;-грамматик). Некоторые экспериментальные исследования</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>для &lt;math&gt;<ins style="font-weight: bold; text-decoration: none;">\,</ins>S&lt;/math&gt;-грамматик). Некоторые экспериментальные исследования</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>&#039;&#039;&#039;<del style="font-weight: bold; text-decoration: none;">С.а.г.</del>&#039;&#039;&#039; и &lt;math&gt;l&lt;/math&gt;-упорядоченных грамматик показали их</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>&#039;&#039;&#039;<ins style="font-weight: bold; text-decoration: none;">сильно ациклической грамматики</ins>&#039;&#039;&#039; и &lt;math&gt;<ins style="font-weight: bold; text-decoration: none;">\,</ins>l&lt;/math&gt;-упорядоченных грамматик показали их</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>сравнимость на практике.</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>сравнимость на практике.</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Другие названия <del style="font-weight: bold; text-decoration: none;">--- </del>&#039;&#039;[[Абсолютно ациклическая грамматика]], [[ANC-Грамматика|&lt;math&gt;ANC&lt;/math&gt;-грамматика]], [[SNC-Грамматика|&lt;math&gt;SNC&lt;/math&gt;-грамматика]]&#039;&#039;.</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>Другие названия <ins style="font-weight: bold; text-decoration: none;">— </ins>&#039;&#039;[[Абсолютно ациклическая грамматика]], [[ANC-Грамматика|&lt;math&gt;ANC&lt;/math&gt;-грамматика]], [[SNC-Грамматика|&lt;math&gt;SNC&lt;/math&gt;-грамматика]]&#039;&#039;.</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==См. также ==</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==См. также ==</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>&#039;&#039; [[l-Упорядоченные грамматики|&lt;math&gt;l&lt;/math&gt;-Упорядоченные грамматики]], [[Чисто синтезированные грамматики]].&#039;&#039;</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">* </ins>&#039;&#039;[[l-Упорядоченные грамматики|&lt;math&gt;l&lt;/math&gt;-Упорядоченные грамматики]],<ins style="font-weight: bold; text-decoration: none;">&#039;&#039;</ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">* &#039;&#039;</ins>[[Чисто синтезированные грамматики]].&#039;&#039;</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==Литература==</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==Литература==</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">[</del>Евстигнеев-<del style="font-weight: bold; text-decoration: none;">Касьянов/98]</del></div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">* </ins>Евстигнеев <ins style="font-weight: bold; text-decoration: none;">В.А., Касьянов В.Н. Теория графов: алгоритмы обработки бесконтурных графов. — Новосибирск: Наука. Сиб. отд</ins>-<ins style="font-weight: bold; text-decoration: none;">ние, 1998.</ins></div></td></tr> </table> KEV http://pco.iis.nsk.su/grapp/index.php?title=%D0%A1%D0%B8%D0%BB%D1%8C%D0%BD%D0%BE_%D0%B0%D1%86%D0%B8%D0%BA%D0%BB%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B0%D1%8F_%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0&diff=4626&oldid=prev KEV в 12:11, 29 января 2010 2010-01-29T12:11:23Z <p></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="ru"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Предыдущая версия</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Версия от 19:11, 29 января 2010</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1">Строка 1:</td> <td colspan="2" class="diff-lineno">Строка 1:</td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>&#039;&#039;&#039;Сильно ациклическая грамматика&#039;&#039;&#039; (&#039;&#039;Strongly non-circular grammar&#039;&#039;) -  </div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>&#039;&#039;&#039;Сильно ациклическая грамматика&#039;&#039;&#039; (&#039;&#039;<ins style="font-weight: bold; text-decoration: none;">[[</ins>Strongly non-circular grammar<ins style="font-weight: bold; text-decoration: none;">]]</ins>&#039;&#039;) -  </div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>атрибутная грамматика, для которой существует такое семейство</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">[[</ins>атрибутная грамматика<ins style="font-weight: bold; text-decoration: none;">]]</ins>, для которой существует такое семейство</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>частичных порядков &lt;math&gt;\{ R(X):X\in N\}&lt;/math&gt;, что справедливы</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>частичных порядков &lt;math&gt;\{ R(X):X\in N\}&lt;/math&gt;, что справедливы</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>следующие два условия:</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>следующие два условия:</div></td></tr> <tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l9">Строка 9:</td> <td colspan="2" class="diff-lineno">Строка 9:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>&lt;math&gt;R(X_1)\cup\ldots\cup R(X_{n&lt;p&gt;})\cup D(p),&lt;/math&gt;</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>&lt;math&gt;R(X_1)\cup\ldots\cup R(X_{n&lt;p&gt;})\cup D(p),&lt;/math&gt;</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>где &lt;math&gt;D(p)&lt;/math&gt; --- &#039;&#039;граф локальной зависимости&#039;&#039;;</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>где &lt;math&gt;D(p)&lt;/math&gt; --- &#039;&#039;<ins style="font-weight: bold; text-decoration: none;">[[</ins>граф локальной зависимости<ins style="font-weight: bold; text-decoration: none;">]]</ins>&#039;&#039;;</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>2) (&#039;&#039;замкнутость&#039;&#039;) для любой продукции &lt;math&gt;p\in P&lt;/math&gt; --- ограничение</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>2) (&#039;&#039;замкнутость&#039;&#039;) для любой продукции &lt;math&gt;p\in P&lt;/math&gt; --- ограничение</div></td></tr> <tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l23">Строка 23:</td> <td colspan="2" class="diff-lineno">Строка 23:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>принадлежащей к классу</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>принадлежащей к классу</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>&#039;&#039;&#039;С.а.г.&#039;&#039;&#039;, является то, что реальные</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>&#039;&#039;&#039;С.а.г.&#039;&#039;&#039;, является то, что реальные</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>зависимости между наследуемыми и синтезируемыми атрибутами,</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>зависимости между <ins style="font-weight: bold; text-decoration: none;">  [[наследуемый атрибут|</ins>наследуемыми<ins style="font-weight: bold; text-decoration: none;">]] </ins>и <ins style="font-weight: bold; text-decoration: none;">[[синтезируемый атрибут|</ins>синтезируемыми атрибутами<ins style="font-weight: bold; text-decoration: none;">]]</ins>,</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>индуцированные &lt;math&gt;R(t)&lt;/math&gt; в дереве &lt;math&gt;t&lt;/math&gt; с корнем &lt;math&gt;X&lt;/math&gt;, покрываются</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>индуцированные &lt;math&gt;R(t)&lt;/math&gt; в <ins style="font-weight: bold; text-decoration: none;">[[дерево|</ins>дереве<ins style="font-weight: bold; text-decoration: none;">]] </ins>&lt;math&gt;t&lt;/math&gt; с <ins style="font-weight: bold; text-decoration: none;">[[корень|</ins>корнем<ins style="font-weight: bold; text-decoration: none;">]] </ins>&lt;math&gt;X&lt;/math&gt;, покрываются</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>&lt;math&gt;R(X)&lt;/math&gt;. Поэтому</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>&lt;math&gt;R(X)&lt;/math&gt;. Поэтому</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>атрибутная грамматика эквивалентна множеству</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>атрибутная грамматика эквивалентна множеству</div></td></tr> <tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l38">Строка 38:</td> <td colspan="2" class="diff-lineno">Строка 38:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>сравнимость на практике.</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>сравнимость на практике.</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Другие названия --- &#039;&#039;Абсолютно ациклическая грамматика, &lt;math&gt;ANC&lt;/math&gt;-грамматика, &lt;math&gt;SNC&lt;/math&gt;-грамматика&#039;&#039;.</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>Другие названия --- &#039;&#039;<ins style="font-weight: bold; text-decoration: none;">[[</ins>Абсолютно ациклическая грамматика<ins style="font-weight: bold; text-decoration: none;">]]</ins>, <ins style="font-weight: bold; text-decoration: none;">[[ANC-Грамматика|</ins>&lt;math&gt;ANC&lt;/math&gt;-грамматика<ins style="font-weight: bold; text-decoration: none;">]]</ins>, <ins style="font-weight: bold; text-decoration: none;">[[SNC-Грамматика|</ins>&lt;math&gt;SNC&lt;/math&gt;-грамматика<ins style="font-weight: bold; text-decoration: none;">]]</ins>&#039;&#039;.</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>См. также &#039;&#039; &lt;math&gt;l&lt;/math&gt;-Упорядоченные грамматики, Чисто синтезированные грамматики.&#039;&#039;</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">==</ins>См. также <ins style="font-weight: bold; text-decoration: none;">==</ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>&#039;&#039; <ins style="font-weight: bold; text-decoration: none;">[[l-Упорядоченные грамматики|</ins>&lt;math&gt;l&lt;/math&gt;-Упорядоченные грамматики<ins style="font-weight: bold; text-decoration: none;">]]</ins>, <ins style="font-weight: bold; text-decoration: none;">[[</ins>Чисто синтезированные грамматики<ins style="font-weight: bold; text-decoration: none;">]]</ins>.&#039;&#039;</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==Литература==</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==Литература==</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[Евстигнеев-Касьянов/98]</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[Евстигнеев-Касьянов/98]</div></td></tr> </table> KEV http://pco.iis.nsk.su/grapp/index.php?title=%D0%A1%D0%B8%D0%BB%D1%8C%D0%BD%D0%BE_%D0%B0%D1%86%D0%B8%D0%BA%D0%BB%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B0%D1%8F_%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0&diff=4493&oldid=prev Glk: Создана новая страница размером '''Сильно ациклическая грамматика''' (''Strongly non-circular grammar'') - атрибутная грамма... 2010-01-26T10:15:20Z <p>Создана новая страница размером &#039;&#039;&#039;Сильно ациклическая грамматика&#039;&#039;&#039; (&#039;&#039;Strongly non-circular grammar&#039;&#039;) - атрибутная грамма...</p> <p><b>Новая страница</b></p><div>&#039;&#039;&#039;Сильно ациклическая грамматика&#039;&#039;&#039; (&#039;&#039;Strongly non-circular grammar&#039;&#039;) - <br /> атрибутная грамматика, для которой существует такое семейство<br /> частичных порядков &lt;math&gt;\{ R(X):X\in N\}&lt;/math&gt;, что справедливы<br /> следующие два условия:<br /> <br /> 1) (&#039;&#039;ацикличность&#039;&#039;) для любой продукции &lt;math&gt;p\in P&lt;/math&gt; является<br /> ациклическим<br /> <br /> &lt;math&gt;R(X_1)\cup\ldots\cup R(X_{n&lt;p&gt;})\cup D(p),&lt;/math&gt;<br /> <br /> где &lt;math&gt;D(p)&lt;/math&gt; --- &#039;&#039;граф локальной зависимости&#039;&#039;;<br /> <br /> 2) (&#039;&#039;замкнутость&#039;&#039;) для любой продукции &lt;math&gt;p\in P&lt;/math&gt; --- ограничение<br /> отношения &lt;math&gt;[R(X_1)\cup\ldots\cup R(X_{n&lt;p&gt;})\cup D(p)]^+&lt;/math&gt; на<br /> &lt;math&gt;A(X_0)&lt;/math&gt; является подмножеством &lt;math&gt;R(X_0)&lt;/math&gt;, т.е.<br /> <br /> &lt;math&gt;[R(X_1)\cup\ldots\cup R(X_{n&lt;p&gt;})\cup D(p)]_{X_0}^+\subseteq R(X_0).&lt;/math&gt;<br /> <br /> Существует полиномиальный алгоритм для вычисления семейства<br /> минимальных &lt;math&gt;R(X)&lt;/math&gt; для<br /> &#039;&#039;&#039;С.а.г.&#039;&#039;&#039;<br /> Наиболее интересной характеристикой грамматики,<br /> принадлежащей к классу<br /> &#039;&#039;&#039;С.а.г.&#039;&#039;&#039;, является то, что реальные<br /> зависимости между наследуемыми и синтезируемыми атрибутами,<br /> индуцированные &lt;math&gt;R(t)&lt;/math&gt; в дереве &lt;math&gt;t&lt;/math&gt; с корнем &lt;math&gt;X&lt;/math&gt;, покрываются<br /> &lt;math&gt;R(X)&lt;/math&gt;. Поэтому<br /> атрибутная грамматика эквивалентна множеству<br /> функций, рекурсивно определенных над структурой дерева &lt;math&gt;t&lt;/math&gt;.<br /> <br /> Одно из преимуществ вычислителя &#039;&#039;&#039;С.а.г.&#039;&#039;&#039; --- то, что он<br /> нисходящий. Однако он может вычислять лишние наследуемые<br /> атрибуты, и его временная сложность является<br /> экспоненциальной от размера &lt;math&gt;W(t)&lt;/math&gt;, если не поддерживается<br /> информация о вычисленных переменных (та же ситуация, что и<br /> для &lt;math&gt;S&lt;/math&gt;-грамматик). Некоторые экспериментальные исследования<br /> &#039;&#039;&#039;С.а.г.&#039;&#039;&#039; и &lt;math&gt;l&lt;/math&gt;-упорядоченных грамматик показали их<br /> сравнимость на практике.<br /> <br /> Другие названия --- &#039;&#039;Абсолютно ациклическая грамматика, &lt;math&gt;ANC&lt;/math&gt;-грамматика, &lt;math&gt;SNC&lt;/math&gt;-грамматика&#039;&#039;.<br /> <br /> См. также &#039;&#039; &lt;math&gt;l&lt;/math&gt;-Упорядоченные грамматики, Чисто синтезированные грамматики.&#039;&#039;<br /> ==Литература==<br /> [Евстигнеев-Касьянов/98]</div> Glk