Синтез регулярного выражения языка, порожденного помеченным графом, методом его локальной редукции
Предлагается новый алгоритм анализа языков, порожденных графами с помеченными вершинами и дугами. Он позволяет находить алгебраическое выражение (в терминах соответствующей алгебры) таких языков. Алгоритм основан на локальной редукции графа, т.е. на последовательном исключении его вершин и дуг. Пред...
Збережено в:
| Опубліковано в: : | Штучний інтелект |
|---|---|
| Дата: | 2012 |
| Автори: | , |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут проблем штучного інтелекту МОН України та НАН України
2012
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/57193 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Синтез регулярного выражения языка, порожденного помеченным графом, методом его локальной редукции / Н.В. Ногина, И.С. Грунский // Штучний інтелект. — 2012. — № 3. — С. 348-353. — Бібліогр.: 8 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862635579036925952 |
|---|---|
| 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 | |
| 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 |