Синтез регулярного выражения языка, порожденного помеченным графом, методом его локальной редукции
Предлагается новый алгоритм анализа языков, порожденных графами с помеченными вершинами и дугами. Он позволяет находить алгебраическое выражение (в терминах соответствующей алгебры) таких языков. Алгоритм основан на локальной редукции графа, т.е. на последовательном исключении его вершин и дуг. Пред...
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| id |
nasplib_isofts_kiev_ua-123456789-57193 |
|---|---|
| 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 |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Синтез регулярного выражения языка, порожденного помеченным графом, методом его локальной редукции |
| spellingShingle |
Синтез регулярного выражения языка, порожденного помеченным графом, методом его локальной редукции Ногина, Н.В. Грунский, И.С. Интеллектуальные робототехнические системы |
| title_short |
Синтез регулярного выражения языка, порожденного помеченным графом, методом его локальной редукции |
| title_full |
Синтез регулярного выражения языка, порожденного помеченным графом, методом его локальной редукции |
| title_fullStr |
Синтез регулярного выражения языка, порожденного помеченным графом, методом его локальной редукции |
| title_full_unstemmed |
Синтез регулярного выражения языка, порожденного помеченным графом, методом его локальной редукции |
| title_sort |
синтез регулярного выражения языка, порожденного помеченным графом, методом его локальной редукции |
| author |
Ногина, Н.В. Грунский, И.С. |
| author_facet |
Ногина, Н.В. Грунский, И.С. |
| topic |
Интеллектуальные робототехнические системы |
| topic_facet |
Интеллектуальные робототехнические системы |
| publishDate |
2012 |
| language |
Russian |
| container_title |
Штучний інтелект |
| publisher |
Інститут проблем штучного інтелекту МОН України та НАН України |
| format |
Article |
| title_alt |
Синтез регулярного виразу мови, що породжена поміченим графом, методом його локальної редукції Synthesis of Regular Expression for Language Generated by a Labeled Graph by Means of its Local Reduction |
| 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.
|
| issn |
1561-5359 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/57193 |
| citation_txt |
Синтез регулярного выражения языка, порожденного помеченным графом, методом его локальной редукции / Н.В. Ногина, И.С. Грунский // Штучний інтелект. — 2012. — № 3. — С. 348-353. — Бібліогр.: 8 назв. — рос. |
| 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 |
| first_indexed |
2025-11-30T18:18:31Z |
| last_indexed |
2025-11-30T18:18:31Z |
| _version_ |
1850858318915960832 |