Финитные представления в алгебраических системах
Вводятся понятия представления, фрагмента и кофрагмента для некоторых специальных алгебраических систем. В терминах специализированных "бэровских" метрик дан критерий финитности представлений. Исследованы алгебраические свойства и условия существования представлений для алгебраических сист...
Gespeichert in:
| Datum: | 2011 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут прикладної математики і механіки НАН України
2011
|
| Schriftenreihe: | Труды Института прикладной математики и механики |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/124050 |
| 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: | Финитные представления в алгебраических системах / И.С. Грунский, И.И. Максименко // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2011. — Т. 23. — С. 63-72. — Бібліогр.: 6 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-124050 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1240502017-09-20T03:03:00Z Финитные представления в алгебраических системах Грунский, И.С. Максименко, И.И. Вводятся понятия представления, фрагмента и кофрагмента для некоторых специальных алгебраических систем. В терминах специализированных "бэровских" метрик дан критерий финитности представлений. Исследованы алгебраические свойства и условия существования представлений для алгебраических систем двух видов. Введено поняття зображення, фрагмента та кофрагмента для деяких спецiальних алгебраїчних систем. У термiнах спецiалiзованих "беровських" метрик надано критерiй фiнiтностi зображень. Дослiджено алгебра чнi властивостi та умови iснування зображень для алгебраїчних систем двох видiв. 2011 Article Финитные представления в алгебраических системах / И.С. Грунский, И.И. Максименко // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2011. — Т. 23. — С. 63-72. — Бібліогр.: 6 назв. — рос. 1683-4720 http://dspace.nbuv.gov.ua/handle/123456789/124050 519.7 ru Труды Института прикладной математики и механики Інститут прикладної математики і механіки НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| description |
Вводятся понятия представления, фрагмента и кофрагмента для некоторых специальных алгебраических систем. В терминах специализированных "бэровских" метрик дан критерий финитности представлений. Исследованы алгебраические свойства и условия существования представлений для алгебраических систем двух видов. |
| format |
Article |
| author |
Грунский, И.С. Максименко, И.И. |
| spellingShingle |
Грунский, И.С. Максименко, И.И. Финитные представления в алгебраических системах Труды Института прикладной математики и механики |
| author_facet |
Грунский, И.С. Максименко, И.И. |
| author_sort |
Грунский, И.С. |
| title |
Финитные представления в алгебраических системах |
| title_short |
Финитные представления в алгебраических системах |
| title_full |
Финитные представления в алгебраических системах |
| title_fullStr |
Финитные представления в алгебраических системах |
| title_full_unstemmed |
Финитные представления в алгебраических системах |
| title_sort |
финитные представления в алгебраических системах |
| publisher |
Інститут прикладної математики і механіки НАН України |
| publishDate |
2011 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/124050 |
| citation_txt |
Финитные представления в алгебраических системах / И.С. Грунский, И.И. Максименко // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2011. — Т. 23. — С. 63-72. — Бібліогр.: 6 назв. — рос. |
| series |
Труды Института прикладной математики и механики |
| work_keys_str_mv |
AT grunskijis finitnyepredstavleniâvalgebraičeskihsistemah AT maksimenkoii finitnyepredstavleniâvalgebraičeskihsistemah |
| first_indexed |
2025-07-09T00:46:10Z |
| last_indexed |
2025-07-09T00:46:10Z |
| _version_ |
1837128192686555136 |
| fulltext |
ISSN 1683-4720 Труды ИПММ НАН Украины. 2011. Том 23
УДК 519.7
c©2011. И.С. Грунский, И.И. Максименко
ФИНИТНЫЕПРЕДСТАВЛЕНИЯВАЛГЕБРАИЧЕСКИХСИСТЕМАХ
Вводятся понятия представления, фрагмента и кофрагмента для некоторых специальных алгебра-
ических систем. В терминах специализированных "бэровских" метрик дан критерий финитности
представлений. Исследованы алгебраические свойства и условия существования представлений для
алгебраических систем двух видов.
Ключевые слова: неструктурированный объект, представление, фрагмент, кофрагмент, алгеб-
раическая система.
1. Введение.Одной из важнейших проблем теории дискретных систем является
идентификация объекта (автомата, отмеченного графа, языка) из некоторого клас-
са объектов [1, 2]. В работах [1, 3] был введен и обоснован подход к исследованию
контрольных и распознающих экспериментов в классах автоматов Мили на основе
их представления специальными окрестностями в метрических пространствах авто-
матов, распространенный в [4, 5] на произвольные неструктурированные множества
дескрипторов.
Целью настоящей статьи является применение синтеза вышеописанных подходов
к исследованию алгебраических систем двух специальных видов.
Статья состоит из введения, трех разделов и заключения.
В первом разделе даны основные понятия алгебраических систем специального
вида.
Во втором разделе исследована представимость систем первого вида, доказано
необходимое условие существования финитных представлений.
В третьем разделе изучен второй вид алгебраических систем. Исследована алгеб-
раическая структура данных систем. Получен метрический критерий существова-
ния финитных представлений и описана алгебраическая структура представлений.
2. Основные понятия и определения. Рассмотрим алгебраическую систему
вида (A,≤,n), где A – счетное множество объектов, ≤ – предпорядок и задана
функция сложности вида n : A → N+ ∪ {∞}.
Вне зависимости от задания функции сложности для любых объектов A,B ∈ A
из соотношения A ≤ B вытекает n(A) ≤ n(B).
Полагаем, что A = Af∪Ain, где Af = {A ∈ A|n(A) < ∞} – множество финитных
объектов и Ain = {A ∈ A|n(A) = ∞} – множество инфинитных объектов.
Два объекта A и B эквивалентны (A ∼= B), если одновременно A ≤ B и B ≤ A.
Обозначим через ∼= A класс эквивалентности {B ∈ A|B ∼= A}. Будем писать A 6≤ B
и A 6∼= B, если не выполнены соотношения A ≤ B и A ∼= B, соответственно, и A < B,
если A ≤ B и A 6∼= B.
Сопоставим каждой алгебраической системе (A,≤, n) фактор-систему следую-
щего вида (A/ ∼=,≤, n), полагая что для любых F,G ⊆ A выполнено соотношение
63
И.С. Грунский, И.И. Максименко
F ≤ G точно тогда, когда для всякого A ∈ F и B ∈ G имеет место A ≤ B и
n(F ) = sup{n(A)|A ∈ F} – сложность множества объектов F . Систему назовем
факторизованной, если она совпадает со своей фактор-системой.
Каждому объекту A поставим в соответствие множества фрагментов Fr(A) =
{B ∈ A|B ≤ A} и кофрагментов CoFr(A) = {B ∈ A|B 6≤ A}. Обозначим суже-
ния данных множеств на объекты сложности не выше N как FrN (A) = {B ∈
Fr(A)|n(A) ≤ N} и CoFrN (A) = {B ∈ CoFr(A)|n(A) ≤ N}.
В некоторых случаях будем рассматривать разбиение CoFr(A) объекта A на
непересекающиеся множества кофрагментов {CoFrτ (A)}τ , элементы которых назо-
вем кофрагментами τ -го сорта. Разбиение назовем однородным по кофрагментам,
если оно совпадает с самим CoFr(A). Система является однородной по кофрагмен-
там, если разбиения по всем объектам однородны.
Нетрудно видеть, что для любого A выполнено Fr(A)∪CoFr(A) = A и Fr(A)∩
CoFr(A) = ∅.
Введем функции Fr : 2A → 2A и CoFr : 2A → 2A, полагая Fr(F ) =
⋃
A∈F Fr(A)
и CoFr(F ) =
⋃
A∈F CoFr(A) для любого множества объектов F .
Объект C назовем разделяющим для A и B ( C ∈ S(A,B) ), если выполнено
(C ≤ A и C 6≤ B) или (C 6≤ A и C ≤ B).
На множестве объектов зададим "расстояние" между объектами β аналогично
"бэровской" метрике [3], полагая β(A,B) = 0, если A ∼= B и β(A,B) = 1/r, где
r = inf{n(C)|C ∈ S(A,B)} в противном случае. Заметим, что объекты A и B могут
быть неэквивалентными, но при этом β(A,B) = 0. Введем множество предельных
объектов для F ⊆ A как LimF = {B ∈ A|inf{β(B,C)|C ∈ F,C 6∼= B} = 0}.
Системa (A,≤,n) является финитно разделимой, если для любых двух неэкви-
валентных объектов существует разделяющий их финитный объект.
Кортеж объектов (A;B1, ..., Br) ∈ Fr(A0) × CoFrr(A0) назовем представлением
ранга r для произвольных A0 ∈ A и F ⊆ A, если для любого C ∈ F из включе-
ния (A; B1, ..., Br) ∈ Fr(C) × CoFrr(C) вытекает C ∼= A0. Представление является
простым, если r=1 и конечным, если величина r конечна.
Прямым представлением назовем кортеж без кофрагментов, а косвенным – кор-
теж без фрагмента.
Системa (A,≤, n) является сильно непредставимой, если для всякого объекта
A ∈ A нет представления относительно A и A.
Систему (A,≤, n) назовем линейно упорядоченной, если A – линейно упорядо-
чено. Система (A,≤, n) всюду плотна, если для любых объектов A,B из A < B
вытекает существование такого объекта C, что A < C < B.
Отметим, что для всякого объекта A линейно упорядоченного множества A вы-
полнено равенство CoFr(A) = {B ∈ A|A < B}.
Введем алгебраические системы объектов вида (A,≤,∇,4, n), где ≤ – предпоря-
док, ∇,4 – идемпотентные, коммутативные и ассоциативные всюду определенные
бинарные операции, n : A → N+ ∪ {∞} – неубывающая функция сложности, и
справедливы следующие аксиомы:
1. для любых двух объектов A и B выполнены соотношения A ≤ A∇B и A4B ≤
64
Финитные представления в алгебраических системах
A;
2. для любых объектов A1, A2, B ∈ A из A1 ∈ Fr(B), A2 ∈ Fr(B) следует
A1∇A2 ∈ Fr(B);
3. для любых объектов A1, A2, B ∈ A из A1 ∈ CoFrτ (B), A2 ∈ CoFrτ (B) выте-
кает A14A2 ∈ CoFrτ (B) для любого τ ;
4. для любых двух объектов A,B ∈ A полагаем, что n(A∇B) = max(n(A), n(B))
и n(A4B) = min(n(A), n(B)).
Назовем алгебраическую систему (A,≤,∇,4, n) локально замкнутой, если для
всякого A ∈ A множества Fr(A) и CoFr(A) замкнуты относительно применения
счетного числа операций ∇ и 4, соответственно.
Для удобства записи дополним носитель системы специальными объектами 0 и
1, для которых выполнены соотношения 0∇A = A и 14A = A для любого A.
Введем операцию ¯ над кортежами объектов из A следующим образом:
(A1; B1, ..., Br)¯ (A2; C1, ..., Cr) = (A1∇A2; B14C1, ..., Br4Cr).
3. Представимость алгебраических систем вида (A,≤,n). Следующая лем-
ма сводит предпорядок в (A,≤, n) к теоретико-множественному включению в мно-
жестве Fr(A) и носит вспомогательный характер:
Лемма 1. Справедливы утверждения:
1. Для любых объектов A и B равносильны условия:
1.1. A ≤ B;
1.2. Fr(A) ⊆ Fr(B);
1.3. CoFr(B) ⊆ CoFr(A);
2. Для любых объектов A и B равносильны условия:
2.1. A ∼= B;
2.2. Fr(A) = Fr(B);
2.3. CoFr(A) = CoFr(B);
3. Для любых объектов A и B равносильны условия:
3.1. A < B;
3.2. Fr(A) ⊂ Fr(B);
3.3. CoFr(B) ⊂ CoFr(A).
Доказательство.
1. Покажем, что условия 1.1 и 1.2 равносильны. Пусть A ≤ B и C ∈ Fr(A).
В этом случае C ≤ A и по свойству транзитивности получаем C ≤ B. Но тогда
C ∈ Fr(B) и выполнено включение Fr(A) ⊆ Fr(B).
Обратно, пусть Fr(A) ⊆ Fr(B). По определению предпорядка A ∈ Fr(A) и,
следовательно, A ∈ Fr(B), что и означает A ≤ B. Таким образом доказана равно-
сильность условий 1.1 и 1.2.
Равносильность 1.2 и 1.3 непосредственно следует из соотношений CoFr(A) =
A− Fr(A) и CoFr(B) = A− Fr(B).
2. Следует из пункта 1 настоящего доказательства, если заметить, что A ∼= B
точно тогда, когда A ≤ B и B ≤ A.
3. Вытекает непосредственно из пунктов 1 и 2 настоящего доказательства. ¤
65
И.С. Грунский, И.И. Максименко
На множестве 2A вводится операция алгебраического замыкания следующим
образом:
Утверждение 2. Операция Fr : 2A → 2A является операцией замыкания.
Доказательство. Покажем, что выполнены условия замыкания.
1. Для любого F ⊆ A выполнено соотношение F ⊆ Fr(F ). Действительно, пусть
C ∈ F . Тогда C ∈ Fr(C) и Fr(C) ⊆ Fr(F ). Следовательно, C ∈ Fr(F ).
2. Даны F1, F2 ∈ A и F1 ⊆ F2. Покажем, что Fr(F1) ⊆ Fr(F2). Действительно,
выберем произвольно C ∈ Fr(F1). Это значит, что C ∈ Fr(D) для некоторого D ∈
F1. Но тогда Fr(D) ⊆ Fr(F2) и следовательно, C ∈ Fr(F2).
3. Покажем, что Fr(Fr(F )) = Fr(F ) для любого F ⊆ A. Согласно пункта 1
настоящего доказательства выполнено включение Fr(F ) ⊆ Fr(Fr(F )). Покажем,
что выполнено обратное включение. Выберем произвольно C ∈ Fr(Fr(F )). Тогда
существует такое D ∈ Fr(F ), для которого C ∈ Fr(D). Из соотношения D ∈ Fr(F )
вытекает существование такого G ∈ F , что D ∈ Fr(G). Но в этом случае C ∈ Fr(G)
и, следовательно, C ∈ Fr(F ). Таким образом, Fr(Fr(F )) = Fr(F ) для любого F ⊆
A. ¤
Следующее утверждение показывает, что каждый объект с точностью до эквива-
лентности изоморфен его нижнему конусу с сохранением предпорядка и сложности
объекта:
Утверждение 3. Алгебраические системы (A/ ∼=,≤,n) и (Fr(A),⊆, n) изо-
морфны.
Доказательство. Введем соответствие δ классов эквивалентности ∼= A и мно-
жеств Fr(A). По условию 2 леммы 1 образы по δ разных классов эквивалентности
∼= A и ∼= B различны. Таким образом, существует биекция между множествами
A/ ∼= и Fr(A).
Кроме того, вводим предпорядок ≤ на A/ ∼= полагая, что ∼= A ≤∼= B точно тогда,
когда A ≤ B. Согласно пункту 1 леммы 1 в этом случае ∼= A ≤∼= B тогда и только
тогда, когда Fr(A) ⊆ Fr(B).
Заметим также, что n(∼= A) = sup{n(B)|B ∼= A} = n(A) и n(Fr(A)) = sup{n(B)|B
≤ A} = n(A).
Утверждение 3 доказано. ¤
Докажем простую, но полезную в дальнейшем лемму
Лемма 4. Дана алгебраическая система (A,≤,n).
1. Для двух объектов A и B существует разделяющий их объект C тогда и
только тогда, когда A 6∼= B.
2. Для двух объектов A и B существует разделяющий их финитный объект C
точно тогда, когда β(A,B) > 0.
Доказательство.
1. Покажем от противного. Пусть C – разделяющий объект для эквивалентных
объектов A и B. Тогда C ∈ Fr(A)⊕ Fr(B). Но согласно пункта 2 леммы 1 Fr(A) =
Fr(B) и такого объекта не существует.
66
Финитные представления в алгебраических системах
Обратно, пусть A 6∼= B. Тогда по пункту 2 леммы 1 множество Fr(A)⊕Fr(B) не
пусто и любой объект из Fr(A)⊕ Fr(B) будет искомым разделяющим объектом.
2. Пусть C – разделяющий финитный объект для объектов A и B. Тогда β(A,B) ≥
1/n(C) > 0.
Обратно, пусть β(A,B) > 0. Тогда существует объект C, разделяющий объекты
A и B, причем n(C) = 1/β(A,B). Таким образом, объект C финитен. ¤
В отличие от утверждения 3 статьи [4], в алгебраических системах (A,≤, n) не
всегда существует представление относительно любого A и A. Более того, справед-
лив следующий критерий сильной непредставимости системы:
Утверждение 5. Пусть дана линейно упорядоченная система (A,≤,n). Си-
стема сильно непредставима тогда и только тогда, когда она является всюду
плотной.
Доказательство. Пусть дана сильно непредставимая, но не всюду плотная си-
стема. Тогда существует такая пара объектов A и B, что A < B и нет такого C,
для которого A < C < B. Покажем от противного, что пара (A,B) является пред-
ставлением для A и A. Предположим, что существует такое C ′ 6∼= A, для которого
A < C ′ < B. Но в этом случае система является всюду плотной.
Обратно, пусть дана всюду плотная система. Предположим, что для некоторого
A0 ∈ A существует представление вида (A,B) для A0 и A. Тогда A ≤ A0 < B. В
данной системе найдется такой объект C, для которого A0 < C < B. Но тогда (A,B)
не является представлением для C и A. Полученное противоречие и доказывает
требуемое утверждение. ¤
Теорема 6. Дана финитно разделимая алгебраическая система (A,≤, n). Если
для произвольных A0 ∈ A и F ⊆ A существует финитное простое представление,
тогда A0 /∈ limF . Обратное утверждение неверно.
Доказательство. Пусть для A0 ∈ A и F ⊆ A существует финитное простое
представление (A; B1), для которого n({A,B1}) ≤ N0, где N0 – некоторое натураль-
ное число. Выберем произвольный объект B ∈ F , не эквивалентный A0. Если такого
объекта нет, то по определению limF пусто и условие утверждения выполнено.
В противном случае, пара (A; B1) разделяет A0 и любой объект C ∈ F , неэкви-
валентный A0. Очевидно, что β(A0, C) ≥ 1/N0. В силу произвольности выбора C
делаем вывод, что A0 /∈ limF .
Обратно, пусть A0 /∈ limF . Построим пример алгебраической системы, для ко-
торой условие A0 /∈ limF выполнено, но нет представления для A0 и F . Рассмотрим
множество конечных слов X∗ в алфавите X, |X| ≥ 2. Будем считать, что для слов p, q
выполнено соотношение p ≤ q, если p является префиксом q, а сложность слова по-
ложим равным его длине. Зафиксируем некоторое непустое слово p0 сложности N0 и
класс F = p0∗X, где операция ∗ есть конкатенация слов. Слова из X∗ эквивалентны,
если они имеют одинаковую запись. Очевидно, что расстояние β(p0, p
′) ≥ 1/(N0 +1)
для любого p′ ∈ F . Следовательно, p0 6∈ LimF .
Покажем теперь, что для p0 и F нет представлений. Предположим противное.
Пусть пара слов (p1, p2) есть представление для p0 и F . Тогда слово p1 является
67
И.С. Грунский, И.И. Максименко
префиксом (фрагментом) для p0 и любого слова из F . Пусть слово p2 является
кофрагментом (т.е. не префиксом) слова p0, но является фрагментом некоторого
слова из F . Это возможно только в том случае, если слово p2 совпадает с некоторым
словом q из F . Так как алфавит X содержит не менее двух символов, то можно
выбрать слово q′ из F , для которого слово p2 не является префиксом. Но тогда слова
q′ и p0 должны совпадать, что невозможно. Полученное противоречие показывает,
что не существует представления для p0 и F . ¤
В работах [1, 3] показано, что для классов автоматов Мили подобный метриче-
ский критерий является необходимым и достаточным условием. Обобщение этого
результата на неструктурированные множества описателей любой природы дано в
[4]. Теорема 6 показывает, что для произвольных алгебраических систем с предпо-
рядком критерий справедлив только как необходимое условие.
4. Представимость алгебраических систем вида (A,≤,∇,4, n). Покажем,
что в алгебраических системах вида (A,≤,∇,4, n) имеют место результаты, анало-
гичные работе [4].
Предварительно докажем вспомогательное утверждение
Утверждение 7. Дана алгебраическая система (A,≤,∇,4, n).
Справедливы утверждения:
1. Для любых A1, A2, B ∈ A из соотношения A1 6≤ B следует, что A1∇A2 6≤ B.
2. Для любого A ∈ A и натурального N множества Af , Ain, Fr(A), CoFr(A),
FrN (A), CoFrN (A) замкнуты относительно операций ∇ и 4.
3. Факторизованная алгебраическая система вида (A,≤,∇,4, n) является верх-
ней полурешеткой.
4. Алгебраическая система вида (A,≤,∇,4,n) является решеткой, если она
однородна по кофрагментам.
Доказательство.
1. Докажем от противного. Предположим, что A1∇A2 ≤ B. Тогда A1 ≤ A1∇A2
и из транзитивности операции ≤ следует A1 ≤ B, что противоречит условию утвер-
ждения.
2. Замкнутость приведенных множеств непосредственно следует из аксиом ал-
гебраической системы (A,≤,∇,4, n).
3. Покажем, что для двух объектов A1, A2 объект A1∇A2 является супремумом.
Предположим, что существует такой B, что A1 ≤ B и A2 ≤ B и B неэквивалентен
A1∇A2. Тогда выполнены соотношения A1∇A2 ≤ B и A1∇A2
∼= B. Выполнение
аксиом полурешетки [6] следует из свойств операций ∇ и 4 и факторизованности
системы.
4. Покажем, что в данном случае система вида (A,≤,∇,4, n) линейно упорядо-
чена. Пусть B = A14A2. Нетрудно видеть, что A1 6≤ B и A2 6≤ B и из однородности
системы вытекает, что A14A2 6≤ A14A2, что возможно только в случае, когда лю-
бые два объекта A1 и A2 сравнимы.
Положим для определенности, что для объектов A1 и A2 выполнено сотношение
A1 ≤ A2. Введем операции ∇ и 4, полагая A14A2 = A1 и A1∇A2 = A2. Тогда
68
Финитные представления в алгебраических системах
система является решеткой по определению [6]. Нетрудно показать, что все аксиомы
определения системы (A,≤,∇,4, n) выполнены. ¤
В предыдущем разделе был приведен пример отсутствия представления для
объекта A0 и конечного множества объектов F . Для алгебраических систем вида
(A,≤,∇,4,n) справедливо следующее утверждение
Утверждение 8.
1. Существует конечное представление для всякого A0 ∈ A и конечного мно-
жества F ⊆ A.
2. Если система (A,≤,∇,4, n) финитно разделима, то существует финитное
конечное представление для всякого A0 ∈ A и конечного множества F ⊆ A.
Доказательство.
1. Пусть дано конечное множество объектов F = {A1, A2, .., AN}. Построим раз-
ность F и ∼= A0 и обозначим через r ее мощность. Если r = 0, то представление
(A0, 1) является искомым представлением.
В противном случае полагаем, что Ci есть разделяющий объект для A0 и Ai, где
i ≤ N . Если Ci ≤ A0, то обозначим его как C ′
i, в противном случае – C ′′
j . В результате
получаем два конечных множества {C ′
i} и {C ′′
j }. Построим объект C ′, применяя к
элементам 1-го множества операцию ∇ и объекты C ′′
τ , применяя к элементам 2-го
множества одного сорта τ операцию 4. Если кофрагментов τ -го сорта среди C ′′
j нет,
то положим C ′′
τ равным 1. Покажем, что полученный кортеж (C ′; C ′′
1 , ..., C ′′
r ) будет
искомым представлением для A0 и F , где r – количество сортов кофрагментов A0.
Действительно, согласно аксиомам 1,2 алгебраической системы получаем, что
C ′ ≤ A0 и C ′′
k 6≤ A0 для всех k ≤ r. Предположим, что существует такой неэкви-
валентный A0 объект B ∈ F , что C ′ ≤ B и C ′′
k 6≤ B. Пусть C ′
s есть разделяющий
объект для B и A0. Но в этом случае C ′
s 6≤ A0, а значит и C ′ 6≤ A0, что противоре-
чит свойствам C ′. Если же C ′′
s есть разделяющий объект для B и A0, то C ′′
s ≤ A0,
что также противоречит свойствам C ′′
s . Полученное противоречие доказывает, что
кортеж (C ′; C ′′
1 , ..., C ′′
r ) будет искомым представлением для A0 и F .
2. Следует из пункта 1 настоящего доказательства и того факта, что в процессе
доказательства выбираны множества {C ′
i} и {C ′′
j } финитной сложности. ¤
Для локально замкнутых алгебраических систем вида (A,≤,∇,4, n) имеет место
Утверждение 9. Существует представление для всякого A0 ∈ A и произволь-
ного множества F ⊆ A.
Доказательство. Пусть дано произвольное счетное множество объектов F . Уда-
лим из данного множества ∼= A0 и обозначим мощность разницы r. Если разность
пуста, то очевидно, что (A0, 1) является искомым представлением.
В противном случае полагаем, что Ci есть разделяющий объект для A0 и Ai.
Если Ci ≤ A0, то обозначим его как C ′
i, в противном случае – C ′′
j . В результате по-
лучаем два не более чем счетных множества {C ′
i} и {C ′′
j }. Пусть объект C ′ получен
применением операции ∇ ко всем элементам 1-го множества и объекты C ′′
k – резуль-
тат применения к элементам 2-го множества сорта k операции4. Если кофрагмента
сорта k нет среди C ′′
j , то полагаем C ′′
k равным 1.
69
И.С. Грунский, И.И. Максименко
Такие объекты всегда существуют в силу локальной замкнутости системы. По-
кажем, что полученный кортеж (C ′;C ′′
1 , ..., C ′′
r ) будет искомым представлением для
A0 и F , где r – число сортов кофрагментов A0.
Действительно, имеют место соотношения C ′ ≤ A0 и C ′′
k 6≤ A0 для всех k ≤ r.
Предположим, что существует такой неэквивалентный A0 объект B ∈ F , что C ′ ≤ B
и C ′′
k 6≤ B. Пусть C ′
s есть разделяющий объект для B и A0. Тогда C ′
s 6≤ A0, а значит
и C ′ 6≤ A0, что противоречит свойствам C ′. Если же C ′′
k есть разделяющий объект
для B и A0, то C ′′
k ≤ A0, что также противоречит свойствам C ′′
k . Полученное проти-
воречие показывает, что кортеж (C ′; C ′′
1 , ..., C ′′
r ) будет искомым представлением для
A0 и F . ¤
Для финитно разделимых и локально замкнутых алгебраических систем вида
(A,≤,∇,4,n) справедлив метрический критерий финитной представимости:
Теорема 10. Финитное представление для A0 ∈ A и множества F ⊆ A суще-
ствует тогда и только тогда, когда A0 6∈ LimF .
Доказательство. Из теоремы 6 следует, что для более общих алгебраических
систем из существования финитного представления для A0 ∈ A и множества F ⊆ A
следует, что A0 6∈ LimF .
Обратно, пусть A0 6∈ LimF . Тогда для любого Bk ∈ F , не эквивалентного A0,
существует объект Ci, разделяющий A0 и Bk со сложностью n(Ci) ≤ N0 для неко-
торого натурального числа N0. Если Ci ≤ A0, то обозначим его как C ′
i, в противном
случае – C ′′
j . В результате получаем два не более чем счетных множества {C ′
i} и
{C ′′
j }. Пусть объект C ′ равен результату применения операции ∇ ко всем элементам
1-го множества и объекты C ′′
k – результат применения к элементам 2-го множества
одинакового сорта k операции 4. Если кофрагмента сорта k нет среди C ′′
j , то пола-
гаем C ′′
k равным 1. Покажем, что полученный кортеж (C ′; C ′′
1 , ..., C ′′
r ) будет искомым
финитным представлением для A0 и F , где r – число сортов кофрагментов A0.
Нетрудно показать, что C ′ ≤ A0 и C ′′
k 6≤ A0 для всех k ≤ r. Предположим,
что существует такой неэквивалентный A0 объект B ∈ F , что C ′ ≤ B и C ′′ 6≤ B.
Пусть C ′
s есть разделяющий объект для B и A0. Но в этом случае C ′
s 6≤ A0, а значит и
C ′
s 6≤ A0, что противоречит свойствам C ′. Если же C ′′
s есть разделяющий объект для
B и A0, то C ′′
s ≤ A0, что также приводит к противоречию. Таким образом, кортеж
(C ′;C ′′
1 , ..., C ′′
r ) будет представлением для A0 и F , причем n({C ′, C ′′
1 , ..., C ′′
r }) ≤ N0.
Теорема 10 доказана. ¤
Метрический критерий представимости неструктурированных множеств дескрип-
торов [4] и теорема 10 обобщают аналогичные метрические критерии представимо-
сти для классов автоматов Мили [3] и помеченных графов.
Справедливо следующее
Следствие 11. Для произвольных A0 ∈ Af и F ⊆ Af , где n(F ) ≤ N0, существу-
ет финитное представление для A0 и F сложности не выше N ′ = max(N0, n(A0)).
Доказательство. Выберем любой неэквивалентный A0 объект B ∈ F . Если та-
кого объекта нет, то пара (A0, 1) является искомым финитным представлением со
сложностью n(A0). Пусть объект C разделяет A0 и B. Очевидно, что C ≤ A0 или
70
Финитные представления в алгебраических системах
C ≤ B. В любом случае, n(C) ≤ N ′ и β(A0, B) ≥ 1/N ′. Таким образом, выполнено
A0 6∈ LimF и по теореме 10 существует финитное представление для A0 и F со
сложностью не выше N ′. ¤
Следующее утверждение позволяет порождать представления объединения клас-
сов в финитно разделимых и локально замкнутых алгебраических системах вида
(A,≤,∇,4,n)
Утверждение 12. Даны A0 ∈ A и F1, F2 ⊆ A. Если O1 является представлени-
ем для A0 и F1, а O2 – представлением для A0 и F2, то O1¯O2 есть представление
для A0 и F1 ∪ F2.
Доказательство. Пусть O1 = (A1; B1, ..., Br) и O2 = (A2;C1, ..., Cs) – некоторые
представления для A0 и F1, F2 ранга r и s, соответственно. Если r не равно s, то
всегда представления O1 и O2 можно расширить объектами 1 в нужных позициях
кортежа для достижения r = s. Предположим, что O1 ¯ O2 не является представ-
лением для A0 и F1 ∪ F2. В этом случае существует неэквивалентный A0 объект
B ∈ F1 ∪ F2, для которого A1∇A2 ≤ B и Bk4Ck 6≤ B. Без потери общности будем
считать, что B ∈ F1. Тогда из A1 ≤ A1∇A2 и A1∇A2 ≤ B следует, что A1 ≤ B.
Аналогично, из соотношений Bk4Ck 6≤ B и Bk4Ck ≤ Bk вытекает Bk 6≤ B. Но то-
гда кортеж O1 не является представлением для A0 и F1. Полученное противоречие
доказывает утверждение 12. ¤
Алгебраическая структура представлений в финитно разделимых и локально
замкнутых алгебраических системах вида (A,≤,∇,4,n) описывается следующей
Теорема 13.
1. Множество представлений для фиксированных A0 и F является идемпо-
тентной и коммутативной полугруппой относительно операции ¯.
2. Множество финитных представлений для фиксированных A0 и F является
идемпотентной и коммутативной полугруппой относительно операции ¯.
Доказательство.
1. Замкнутость множества представлений для фиксированных A0 и F относи-
тельно операции ¯ следует из утверждения 12 при предположении F1 = F2 = F .
Идемпотентность, коммутативность и ассоциативность операции ¯ вытекает из ана-
логичных свойств операций ∇,4.
2. Вытекает из пункта 1 настоящего доказательства и соотношения n(O1¯O2) ≤
max(n(O1), n(O2)) для любых пар объектов O1, O2. ¤
5. Заключение. В настоящей статье методы исследования представлений не-
структурированных объектов распространены на алгебраические структуры специ-
ального вида. Для локально замкнутых и финитно разделимых алгебраических си-
стем получен метрический критерий существования финитных представлений, ана-
логичный результатам работы [4]. Описана алгебраическая структура представле-
ний для фиксированных объекта-эталона и множества объектов.
71
И.С. Грунский, И.И. Максименко
1. Грунский И.С., Козловский В.А. Синтез и идентификация автоматов. – Киев.: Наукова думка,
2004. – 245 c.
2. Бородай С.Ю. Эксперименты в эффективно заданных классах автоматов: Автореферат канд.
физ.-мат. наук; 01.01.09 / СГУ – Саратов, 1997. – 21 с.
3. Максименко И.И. Эксперименты в финитно-определенных метрических пространствах автома-
тов: Автореферат канд. физ.-мат. наук; 01.01.09 / СГУ – Саратов, 2000. – 16 с.
4. Максименко И.И. Финитные представления неструктурированных объектов // Труды ИПММ.
– 2009. – Т. 19. – С. 162-167.
5. Грунский И.С., Максименко И.И. Распознавание неструктурированных объектов // Труды
ИПММ. – 2010. – Т. 21. – С. 76-85.
6. Общая алгебра. – Т. 1. / Под общ. ред. Л.А.Скорнякова. – М.: Наука, 1990. – 592 с.
I. S. Grunsky, I. I. Maksimenko
Finite representation in algebraic systems.
Сoncepts of representation, fragment and сofragment for some special algebraic systems are considered.
A conditions of finiteness representations give in terms of specialized metrics of Ber. The algebraic
properties and conditions for the existence of representations investigated for algebraic systems in the
two cases.
Keywords: unstructured object, representation, fragment, cofragment, algebraic systems.
I. С. Грунський, I. I. Максименко
Фiнiтнi зображення в алгебраїчних системах.
Введено поняття зображення, фрагмента та кофрагмента для деяких спецiальних алгебраїчних
систем. У термiнах спецiалiзованих "беровських" метрик надано критерiй фiнiтностi зображень.
Дослiджено алгебраїчнi властивостi та умови iснування зображень для алгебраїчних систем двох
видiв.
Ключовi слова: неструктурований об’єкт, зображення, фрагмент, кофрагмент, алгебраїчна
система.
Ин-т прикл. математики и механики НАН Украины, Донецк
Донецкий национальный ун-т
iim@bank-prsp.dn.ua
Получено 15.11.11
72
|