Характеризация языков, представимых в графах c отмеченными вершинами

Для языков, представимых графами с отмеченными вершинами, доказывается теорема, аналогичная теореме Майхилла-Нерода для языков, распознаваемых конечными автоматами. На основе доказательства теоремы показано, что любому языку, порождаемому графом с отмеченными вершинами, соответствует единственный с...

Ausführliche Beschreibung

Gespeichert in:
Bibliographische Detailangaben
Veröffentlicht in:Труды Института прикладной математики и механики
Datum:2009
1. Verfasser: Пряничникова, Е.А.
Format: Artikel
Sprache:Russian
Veröffentlicht: Інститут прикладної математики і механіки НАН України 2009
Online Zugang:https://nasplib.isofts.kiev.ua/handle/123456789/123916
Tags: Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:Характеризация языков, представимых в графах c отмеченными вершинами / Е.А. Пряничникова // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2009. — Т. 19. — С. 200-208. — Бібліогр.: 5 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id nasplib_isofts_kiev_ua-123456789-123916
record_format dspace
spelling Пряничникова, Е.А.
2017-09-13T09:51:12Z
2017-09-13T09:51:12Z
2009
Характеризация языков, представимых в графах c отмеченными вершинами / Е.А. Пряничникова // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2009. — Т. 19. — С. 200-208. — Бібліогр.: 5 назв. — рос.
1683-4720
https://nasplib.isofts.kiev.ua/handle/123456789/123916
519.6
Для языков, представимых графами с отмеченными вершинами, доказывается теорема, аналогичная теореме Майхилла-Нерода для языков, распознаваемых конечными автоматами. На основе доказательства теоремы показано, что любому языку, порождаемому графом с отмеченными вершинами, соответствует единственный с точностью до изоморфизма полный детерминированный граф с минимальным числом вершин и единственная система леволинейных уравнений с минимальным числом уравнений, из решений которой может быть получено регулярное выражение, описывающее этот язык.
Автор выражает благодарность И.С. Грунскому за постановку задачи и полезные замечания.
ru
Інститут прикладної математики і механіки НАН України
Труды Института прикладной математики и механики
Характеризация языков, представимых в графах c отмеченными вершинами
Article
published earlier
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
title Характеризация языков, представимых в графах c отмеченными вершинами
spellingShingle Характеризация языков, представимых в графах c отмеченными вершинами
Пряничникова, Е.А.
title_short Характеризация языков, представимых в графах c отмеченными вершинами
title_full Характеризация языков, представимых в графах c отмеченными вершинами
title_fullStr Характеризация языков, представимых в графах c отмеченными вершинами
title_full_unstemmed Характеризация языков, представимых в графах c отмеченными вершинами
title_sort характеризация языков, представимых в графах c отмеченными вершинами
author Пряничникова, Е.А.
author_facet Пряничникова, Е.А.
publishDate 2009
language Russian
container_title Труды Института прикладной математики и механики
publisher Інститут прикладної математики і механіки НАН України
format Article
description Для языков, представимых графами с отмеченными вершинами, доказывается теорема, аналогичная теореме Майхилла-Нерода для языков, распознаваемых конечными автоматами. На основе доказательства теоремы показано, что любому языку, порождаемому графом с отмеченными вершинами, соответствует единственный с точностью до изоморфизма полный детерминированный граф с минимальным числом вершин и единственная система леволинейных уравнений с минимальным числом уравнений, из решений которой может быть получено регулярное выражение, описывающее этот язык.
issn 1683-4720
url https://nasplib.isofts.kiev.ua/handle/123456789/123916
citation_txt Характеризация языков, представимых в графах c отмеченными вершинами / Е.А. Пряничникова // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2009. — Т. 19. — С. 200-208. — Бібліогр.: 5 назв. — рос.
work_keys_str_mv AT prâničnikovaea harakterizaciââzykovpredstavimyhvgrafahcotmečennymiveršinami
first_indexed 2025-12-07T18:02:20Z
last_indexed 2025-12-07T18:02:20Z
_version_ 1850873521792614403