Синтез регулярного выражения языка, порожденного помеченным графом, методом его локальной редукции
Предлагается новый алгоритм анализа языков, порожденных графами с помеченными вершинами и дугами. Он позволяет находить алгебраическое выражение (в терминах соответствующей алгебры) таких языков. Алгоритм основан на локальной редукции графа, т.е. на последовательном исключении его вершин и дуг. Пред...
Saved in:
| Published in: | Штучний інтелект |
|---|---|
| Date: | 2012 |
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут проблем штучного інтелекту МОН України та НАН України
2012
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/57193 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Синтез регулярного выражения языка, порожденного помеченным графом, методом его локальной редукции / Н.В. Ногина, И.С. Грунский // Штучний інтелект. — 2012. — № 3. — С. 348-353. — Бібліогр.: 8 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859680100487790592 |
|---|---|
| author | Ногина, Н.В. Грунский, И.С. |
| author_facet | Ногина, Н.В. Грунский, И.С. |
| citation_txt | Синтез регулярного выражения языка, порожденного помеченным графом, методом его локальной редукции / Н.В. Ногина, И.С. Грунский // Штучний інтелект. — 2012. — № 3. — С. 348-353. — Бібліогр.: 8 назв. — рос. |
| collection | DSpace DC |
| container_title | Штучний інтелект |
| description | Предлагается новый алгоритм анализа языков, порожденных графами с помеченными вершинами и дугами. Он позволяет находить алгебраическое выражение (в терминах соответствующей алгебры) таких языков. Алгоритм основан на локальной редукции графа, т.е. на последовательном исключении его вершин и дуг. Предложен порядок редукции, при котором исключение вершин проводится от финальной к начальной, а также упрощение графа в процессе редукции, что зачастую позволяет уменьшить объем вычислений.
Запропоновано новий алгоритм аналізу мов, породжених графами з поміченими вершинами і дугами. Він дозволяє знаходити алгебраїчний вираз (в термінах відповідної алгебри) таких мов. Алгоритм засновано на локальній редукції графа, тобто на послідовному виключенні його вершин та дуг. Запропоновано порядок редукції, при якому видалення вершин проводиться від фінальної до початкової, а також спрощення графа в процесі редукції, що часто дозволяє зменшити обсяг обчислень.
New algorithm for analysis of languages generated by graphs with labeled vertices and transitions is proposed. It gives regular expression (in terms of the proper algebra) describing the language. The algorithm is based on a local reduction of the graph, that is the sequential exclusion of vertices and transitions. It is proposed a reduction procedure, in which removal starting at the final vertex to initial, and a simplification of the graph in the process of reduction, which often reduces the amount of computations.
|
| first_indexed | 2025-11-30T18:18:31Z |
| format | Article |
| fulltext |
«Искусственный интеллект» 3’2012348
5Н
УДК 519.713
Н.В. Ногина, И.С. Грунский
Институт информатики и искусственного интеллекта
ГВУЗ «Донецкий национальный технический университет»
Украина, 83050, г. Донецк, пр. Б. Хмельницкого, 84
Синтез регулярного выражения языка,
порожденного помеченным графом,
методом его локальной редукции
N.V. Nogina, I.S. Grunsky
Institute of Informatics and Artificial Intelligence
of Donetsk National Technical University
Ukraine, 83050, c. Donetsk, B. Khmelnitsky ave., 84
Synthesis of Regular Expression for Language Generated
by a Labeled Graph by Means of its Local Reduction
Н.В. Ногіна, І.С. Грунський
Інститут інформатики і штучного інтелекту
ДВНЗ «Донецький національний технічний університет»
Україна, 83050, м. Донецьк, пр. Б. Хмельницького, 84
Синтез регулярного виразу мови, що породжена
поміченим графом, методом його локальної редукції
Предлагается новый алгоритм анализа языков, порожденных графами с помеченными вершинами и
дугами. Он позволяет находить алгебраическое выражение (в терминах соответствующей алгебры)
таких языков. Алгоритм основан на локальной редукции графа, т.е. на последовательном исключении
его вершин и дуг. Предложен порядок редукции, при котором исключение вершин проводится от
финальной к начальной, а также упрощение графа в процессе редукции, что зачастую позволяет
уменьшить объем вычислений.
Ключевые слова: помеченный граф, алгебра языка, регулярное выражение, локальная
редукция графа.
New algorithm for analysis of languages generated by graphs with labeled vertices and transitions is proposed. It
gives regular expression (in terms of the proper algebra) describing the language. The algorithm is based on a local
reduction of the graph, that is the sequential exclusion of vertices and transitions. It is proposed a reduction procedure,
in which removal starting at the final vertex to initial, and a simplification of the graph in the process of reduction,
which often reduces the amount of computations.
Key Words: labeled graphs, algebra of language, regular expression, local reduction of the graph.
Запропоновано новий алгоритм аналізу мов, породжених графами з поміченими вершинами і дугами.
Він дозволяє знаходити алгебраїчний вираз (в термінах відповідної алгебри) таких мов. Алгоритм засновано
на локальній редукції графа, тобто на послідовному виключенні його вершин та дуг. Запропоновано
порядок редукції, при якому видалення вершин проводиться від фінальної до початкової, а також спрощення
графа в процесі редукції, що часто дозволяє зменшити обсяг обчислень.
Ключові слова: помічений граф, алгебра мови, регулярний вираз, локальна редукція графа.
Введение
В настоящее время актуальны задачи, связанные с анализом и синтезом языков,
представимых в помеченных графах. Интерес к изучению таких графов вызван тем,
Синтез регулярного выражения языка, порожденного помеченным графом...
«Штучний інтелект» 3’2012 349
5Н
что существует ряд важных задач, которые естественным образом представляются в
виде помеченных графов. Такие графы интенсивно изучаются при верификации про-
грамм [1] и планировании движения мобильного робота [2].
Свойства языков, представимых графами с отмеченными дугами, изучались
С. Клини. Им предложена широкоизвестная алгебра, описывающая эти языки. В на-
стоящее время известен ряд алгоритмов описания этих языков в алгебре Клини и
построение графов по такому описанию [3]. Свойства языков, представимых графами
с отмеченными вершинами, рассматривались в работах [4-7]. В них предложены алге-
бры, аналогичные алгебре Клини, для описания языков, порожденных такими графами,
и алгоритмы перехода от алгебраических выражений, описывающих языки, к представ-
ляющим их графам и наоборот.
В данной работе рассматривается алгебра, описывающая языки, порожденные
графами с помеченными вершинами и дугами, частным случаем которой является
алгебра, описанная в [4-7]. Рассматривается задача построения алгебраического выра-
жения языков, представимых в таких графах.
Целью данной работы является разработка нового алгоритма построения регу-
лярного выражения по заданному помеченному графу.
Основные определения и обозначения
Помеченным графом назовем восьмерку ),,,,,,,( 0 FqYXEQG , где Q –
конечное множество вершин, E – множество дуг, X – множество отметок вершин,
Y – множество отметок дуг, XQ : – функция разметки вершин, YL : –
функция разметки дуг, 0q – начальная вершина графа, F – множество финальных
вершин. Путем в графе G будем называть конечную последовательность
kk qeeqeql .... 12211 ,
где iq – вершина, а ie – дуга, началом которой является вершина iq , а концом
1iq . Отметка пути l – это последовательность отметок
kk xyyxyxlw ....)( 12211 ,
где )( ii qx , )( ii ey .
Успешным путем в помеченном графе назовем путь из начальной вершины в
финальную. Языком )(GL , порождаемым графом G , назовем множество отметок всех
успешных путей.
Пусть Pre(qi) – множество начальных вершин всех дуг, входящих в qi, Post(qi) –
множество конечных вершин всех дуг, исходящих из qi.
Преходящей вершиной назовем вершину q ≠ q0 , у которой Pre(q) = , а ви-
сячей – q ≠ fin, у которой Post(q) = .
Пусть Z – множество всех непустых слов вида kk xyyxw 111 ... . Рассмотрим
алгебру
,,2 Z ,⊛, Z, , в которой операции на языках L1, L2, L Z+ определены
следующим образом:
1) операция объединения: 21 LL = 21
LwилиLww ;
2) операция сочленения (склеивания) слов: ,если '
11
'
2
'
121 xwwxwwLL
'
22 xww ;
Ногина Н.В., Грунский И.С.
«Искусственный интеллект» 3’2012350
5Н
3) операция итерации (зацикливания): L⊛ =
0i
iL , где L0= LначLкон, причем
Lнач={x| xw’ L, x X}, Lкон= {x| w’x L, x X}; L1=L; Ln+1=Ln ◦L для всеx n≥1 .
Регулярные выражения определим индуктивно:
1) пустое множество является регулярным выражением;
2) x, xyx’ являются регулярными выражениями для всех символов x,x’ X, y Y;
3) если p и q – регулярные выражения, то выражения p◦q, pq, p⊛ также
являются регулярными.
Постановка задачи
В данной работе решается следующая задача. Дан конечный ориентированный
связный помеченный граф. Требуется разработать алгоритм построения регулярного
выражения языка, порождаемого этим графом.
Решение систем линейных уравнений
Очевидно, что по аналогии с работой [5] для любого помеченного графа G,
порождающего язык L(G), можно найти регулярное выражение R, для которого
L(R)=L(G). Для этого необходимо решить систему линейных уравнений вида (1)
nnnnnnn
nn
nn
VLMLMLML
VLMLMLML
VLMLMLML
...
...
...
2211
222221212
112121111
, (1)
где Li – язык, порождаемый i-й вершиной графа, т.е. множество отметок всех
путей из вершины qi в любую финальную; Mij= )()()( jii qeq = xiyixj; Vi= )( iq = xi,
если вершина qi является финальной, и Vi= в противном случае.
В [5] было показано, что линейное уравнение вида BLAL ii имеет един-
ственное решение
ALi ⊛ BB . (2)
Для решения системы линейных уравнений (1) можно использовать метод много-
кратного удаления неизвестных, подобный классическому методу Гаусса. Используя (2),
можно удалить Ln из правой части последнего уравнения в системе (1). Полученное
значение для Ln можно подставить в предпоследнее уравнение и получить выражение
для Ln-1, которое зависит только от L1...Ln-2. Продолжая такие подстановки для всех
оставшихся в системе уравнений, можно получить значения всех Li, которые будут
регулярными выражениями в рассматриваемой алгебре.
Алгоритм построения регулярного выражения
Вход. Граф G с отмеченными вершинами, с начальной и финальными вершинами.
Выход. Регулярное выражение языка, порожденного исходным графом.
Шаг 1. Граф G превращается в граф с отмеченными дугами. Для этого отметки
вершин стираются и в дугах (qi, ei, qj) отметкой ei становится xiyixj, где xk=(qk), где
k=i,j, yi=ρ(ei).
Синтез регулярного выражения языка, порожденного помеченным графом...
«Штучний інтелект» 3’2012 351
5Н
В список вершин вводится фиктивная конечная вершина fin, а в список дуг –
дуга из каждой финальной вершины qi в вершину fin с отметкой вершины qi.
Шаг 2. Удаление преходящих и висячих вершин.
While в графе существует вершина q ≠ q0, у которой Pre(qi)= do
Удаляем вершину qi и все дуги, исходящие из нее;
While в графе существует вершина qi ≠ fin, у которой Post(qi) = do
Удаляем вершину qi и все дуги, входящие в нее;
Шаг 3. If в графе существует хоть одна петля или существуют вершины, не
являющиеся начальными, из которых исходит хоть одна дуга, then goto Шаг 4
else goto Шаг 7;
Шаг 4. Удаление кратных дуг и петель.
1. Удаляем кратные дуги, заменяя их одной дугой с отметкой, равной объеди-
нению отметок исходных дуг.
2. Удаляем все петли по следующему правилу.
Пусть в вершине qi есть петля с отметкой А. Если из этой вершины нет дуги в
другую вершину, то петля удаляется. В противном случае для всех дуг (qi, ei, qj), где
i≠j, с отметкой дуги В, петля удаляется, а отметка В заменяется отметкой А⊛○В В.
На шагах 5 – 6 происходит удаление одной вершины.
Шаг 5.
Выбираем qi Pre(fin);
q := qi;
Шаг 6.
If q q0 then удаляем вершину q и все входящие и выходящие из нее дуги.
Если при этом есть произвольный путь из некоторой вершины qi в вершину qk, через
удаляемую вершину q, где qjPre(q) и qkPost(q), то в граф добавляется дуга, со-
держащая пометку, равную склеиванию пометок удаляемых дуг данного пути;
goto Шаг 2;
else qi равная q0 не исключается;
выбираем qm Pre(q0);
q := qm;
goto Шаг 6;
Шаг 7. Удаляем все вершины q q0 и q fin и все входящие в них дуги.
Получим граф, состоящий из двух вершин: q0 и fin и дуги, между ними с пометкой R,
где R – это искомое регулярное выражение.
Анализ алгоритма
Из описания алгоритма следует, что алгоритм имеет следующую структуру:
шаги 2 – 6 образуют внешний цикл алгоритма, шаги 5 – 6 образуют вложенный цикл
алгоритма. При прохождении один раз внешнего цикла в графе удаляется по крайней
мере одна вершина. Следовательно, внешний цикл выполняется O(n) раз, где n – число
вершин помеченного графа. Таким образом, алгоритм завершает свою работу через
конечное число шагов. При выполнении одного прохода по внешнему циклу на шаге 4
в графе удаляются кратные дуги и петли. Таким образом, перед началом выполнения
шага 5 в графе может быть не более O(n2) дуг. При выполнении шагов 5 – 6 алго-
ритма удаляется одна вершина графа, при этом в графе удаляется не более O(n) дуг,
и может быть добавлено не более O((n-1)2) новых дуг.
Из проведенных рассуждений следует, что если анализ одной дуги графа про-
водится в единицу времени, то алгоритм требует не более O(nm) единиц времени,
где m – количество дуг в исходном графе.
Ногина Н.В., Грунский И.С.
«Искусственный интеллект» 3’2012352
5Н
Докажем правильность получаемого решения, показав, что все операции на гра-
фах, применяемые в данном алгоритме, фактически соответствуют методу решения
систем линейных уравнений рассматриваемой алгебры.
1. Операция удаления вершины соответствует подстановке одного уравнения в
другое:
.qkqj
qkq
qqj
LBAL
LBL
LAL
2. Операция удаления кратных ребер обоснована дистрибутивным законом рас-
сматриваемой алгебры:
qjqjqjqi LBALBLAL )( .
3. Операция удаления петли соответствует решению (2) линейного уравнения с
одним неизвестным данной алгебры.
4. Удаление висячих вершин на Шаге 2 обосновано тем, что язык, порождаемый
такой вершиной, пуст, поскольку из этих вершин вершина fin недостижима.
5. Очевидно, что удаление преходящих вершин и всех исходящих из них дуг на
Шаге 2 возможно без изменения множества успешных путей в помеченном графе,
поскольку данные вершины недостижимы из начальной.
Таким образом, все операции на графах, выполняемые предложенным алгорит-
мом, соответствуют методу решения системы линейных уравнений в данной алгебре.
Следовательно, алгоритм корректен.
Алгоритм основан на локальной редукции графа, т.е. на последовательном исклю-
чении его вершин и дуг. Предложен порядок редукции, при котором исключение
вершин проводится от финальной к начальной. Такой порядок позволяет не обраба-
тывать вершины, из которых fin не достижима, и они удаляются все сразу на шаге 7.
В алгоритме предусмотрено упрощение графа. Оно достигается, во-первых, путем
последовательного удаления всех преходящих и висячих вершин (шаг 2) и, во-вторых,
путем удаления всех петель и кратных дуг (шаг 3) перед каждым удалением вершины
(шаг 5 – 6). Таким образом, это упрощение, по сути, является построением аналога
трима [8, с. 23]. Порядок исключения вершин и приемы упрощения графа являются,
на наш взгляд, весомыми достоинствами предложенного алгоритма.
Выводы
Предложенный алгоритм позволяет находить регулярное выражение языка, по-
рожденного графом с помеченными вершинами и дугами.
В отличие от алгоритмов решения этой задачи, основанных на решении системы
линейных уравнений [4], [5], в данном алгоритме учитывается структура графа, что
зачастую позволяет уменьшить объем вычислений.
Литература
1. Годлевский А.Б. Предикатные преобразователи в контексте символьного моделирования транзицион-
ных систем / А.Б. Годлевский // Кибернетика и системный анализ. – 2010. – № 4. – С. 91-99.
2. Dudek G. Computational principles of mobile robotic / G. Dudek, M. Jenkin. – Cambridge Univ. press, 2000. –
280 p.
3. Хопкрофт Дж. Введение в теорию автоматов, языков и вычислений / Хопкрофт Дж., Мотвани Р.,
Ульман Дж. – [2-е изд.]. – М. : Издательский дом «Вильямс», 2002. – 528 с.
4. Капитонова Ю.В. Математическая теория проектирования вычислительных систем / Ю.В. Капито-
нова, А.А. Летичевский. – М. : Наука, 1988. – 296 с.
Синтез регулярного выражения языка, порожденного помеченным графом...
«Штучний інтелект» 3’2012 353
5Н
5. Грунский И.С. Об алгебре языков, представимых графами с отмеченными вершинами / И.С. Грун-
ский, Е.А. Пряничникова // Труды Ин-та прикл. математики и механики НАН Украины. – 2009. –
Т. 18. – С. 37-46.
6. Grunsky I. Languages Representable by Vertex-labeled Graphs / I. Grunsky, O. Kurganskyy, I. Potapov //
Proc. of the 30th International Symposium on Mathematical Foundations of Computer Science. – 2005. –
V. 3618. – P. 435-446.
7. Grunsky I. On algebra of Languages Representable by Vertex-labeled Graphs / I. Grunsky, I. Potapov, E. Prya-
nichnikova // Theoretical Computer Science. – 2012. – V. 426-427.
8. Eilenberg S. Automata, Languages and Machines. Vol. A / Eilenberg S. – Academic Press, New York and
London, 1974. – 469 p.
Literatura
1. Godlevskij A.B. Kibernetika i sistemnyj analiz. 2010. № 4. S. 91-99.
2. Dudek G. Computational principles of mobile robotic. Cambridge Univ. press. 2000. 280 p.
3. Hopkroft Dzh. Vvedenie v teoriju avtomatov, jazykov i vychislenij. M. : Izdatel’skij dom “Vil’jams”. 2002. 528 s.
4. Kapitonova Ju.V. Matematicheskaja teorija proektirovanija vychislitel’nyh sistem. M. : Nauka. 1988. 296 s.
5. Grunsky I.S. Trudy In-ta prikl. matematiki i mehaniki NAN Ukrainy. 2009. T.18. S. 37-46.
6. Grunsky I. Languages Representable by Vertex-labeled Graphs. Proc. of the 30th International Symposium on
Mathematical Foundations of Computer Science. 2005. V. 3618 P. 435-446.
7. Grunsky I. On algebra of Languages Representable by Vertex-labeled Graphs. Theoretical Computer Science.
2012. V. 426-427.
8. Eilenberg S. Automata, Languages and Machines. Vol A. Academic Press, New York and London. 1974. 469 p.
RESUME
N.V. Nogina, I.S. Grunsky
Synthesis of Regular Expression for Language Generated
by a Labeled Graph by Means of its Local Reduction
In this paper, the authors study languages generated by labeled graphs in the case when
both vertices and transitions are labeled. The case when words of generated language contain
only labels of transitions is considered in the finite automata theory. The corresponding
languages are known as regular or automata languages and intensely investigated. In this
paper, the more complicated case is studied, i.e. when words contain labels of transitions and
vertices. The generated languages can be used in a research of the behavioral properties of
certain models and processes. These graphs are intensively studied in program verification
and motion planning of mobile robots.
The authors consider algebra of languages generated by graphs with labeled vertices and
transitions. The algorithm for analysis of languages generated by such graphs is proposed. The
algorithm is based on the local graph reduction, i.e. on the sequential exclusion of its vertices
and transitions.
An order of reduction in which the removal of vertices is performed from final to
initial one and the simplification of the graph in the reduction process are proposed.
Unlike other algorithms for this problem based on the solving of the system of linear
equations, in this algorithm the graph structure is taken into account that often reduces an
amount of computation.
Статья поступила в редакцию 05.06.2012.
|
| id | nasplib_isofts_kiev_ua-123456789-57193 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1561-5359 |
| language | Russian |
| last_indexed | 2025-11-30T18:18:31Z |
| publishDate | 2012 |
| publisher | Інститут проблем штучного інтелекту МОН України та НАН України |
| record_format | dspace |
| spelling | Ногина, Н.В. Грунский, И.С. 2014-03-04T19:37:24Z 2014-03-04T19:37:24Z 2012 2012 Синтез регулярного выражения языка, порожденного помеченным графом, методом его локальной редукции / Н.В. Ногина, И.С. Грунский // Штучний інтелект. — 2012. — № 3. — С. 348-353. — Бібліогр.: 8 назв. — рос. 1561-5359 https://nasplib.isofts.kiev.ua/handle/123456789/57193 519.713 Предлагается новый алгоритм анализа языков, порожденных графами с помеченными вершинами и дугами. Он позволяет находить алгебраическое выражение (в терминах соответствующей алгебры) таких языков. Алгоритм основан на локальной редукции графа, т.е. на последовательном исключении его вершин и дуг. Предложен порядок редукции, при котором исключение вершин проводится от финальной к начальной, а также упрощение графа в процессе редукции, что зачастую позволяет уменьшить объем вычислений. Запропоновано новий алгоритм аналізу мов, породжених графами з поміченими вершинами і дугами. Він дозволяє знаходити алгебраїчний вираз (в термінах відповідної алгебри) таких мов. Алгоритм засновано на локальній редукції графа, тобто на послідовному виключенні його вершин та дуг. Запропоновано порядок редукції, при якому видалення вершин проводиться від фінальної до початкової, а також спрощення графа в процесі редукції, що часто дозволяє зменшити обсяг обчислень. New algorithm for analysis of languages generated by graphs with labeled vertices and transitions is proposed. It gives regular expression (in terms of the proper algebra) describing the language. The algorithm is based on a local reduction of the graph, that is the sequential exclusion of vertices and transitions. It is proposed a reduction procedure, in which removal starting at the final vertex to initial, and a simplification of the graph in the process of reduction, which often reduces the amount of computations. ru Інститут проблем штучного інтелекту МОН України та НАН України Штучний інтелект Интеллектуальные робототехнические системы Синтез регулярного выражения языка, порожденного помеченным графом, методом его локальной редукции Синтез регулярного виразу мови, що породжена поміченим графом, методом його локальної редукції Synthesis of Regular Expression for Language Generated by a Labeled Graph by Means of its Local Reduction Article published earlier |
| spellingShingle | Синтез регулярного выражения языка, порожденного помеченным графом, методом его локальной редукции Ногина, Н.В. Грунский, И.С. Интеллектуальные робототехнические системы |
| title | Синтез регулярного выражения языка, порожденного помеченным графом, методом его локальной редукции |
| title_alt | Синтез регулярного виразу мови, що породжена поміченим графом, методом його локальної редукції Synthesis of Regular Expression for Language Generated by a Labeled Graph by Means of its Local Reduction |
| title_full | Синтез регулярного выражения языка, порожденного помеченным графом, методом его локальной редукции |
| title_fullStr | Синтез регулярного выражения языка, порожденного помеченным графом, методом его локальной редукции |
| title_full_unstemmed | Синтез регулярного выражения языка, порожденного помеченным графом, методом его локальной редукции |
| title_short | Синтез регулярного выражения языка, порожденного помеченным графом, методом его локальной редукции |
| title_sort | синтез регулярного выражения языка, порожденного помеченным графом, методом его локальной редукции |
| topic | Интеллектуальные робототехнические системы |
| topic_facet | Интеллектуальные робототехнические системы |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/57193 |
| work_keys_str_mv | AT noginanv sintezregulârnogovyraženiââzykaporoždennogopomečennymgrafommetodomegolokalʹnoiredukcii AT grunskiiis sintezregulârnogovyraženiââzykaporoždennogopomečennymgrafommetodomegolokalʹnoiredukcii AT noginanv sintezregulârnogovirazumoviŝoporodženapomíčenimgrafommetodomiogolokalʹnoíredukcíí AT grunskiiis sintezregulârnogovirazumoviŝoporodženapomíčenimgrafommetodomiogolokalʹnoíredukcíí AT noginanv synthesisofregularexpressionforlanguagegeneratedbyalabeledgraphbymeansofitslocalreduction AT grunskiiis synthesisofregularexpressionforlanguagegeneratedbyalabeledgraphbymeansofitslocalreduction |