Глава 3. Алгебра регулярных структур

3.1. Координаты образующих

В первом томе были введены объекты теории образов: образующие, конфигурации и изображения, а также и отношения образов: преобразования подобия, комбинаторные отношения и деформации. Теперь мы займемся углублением нашего понимания этих объектов, обращая особое внимание на их алгебраические свойства.

Пространства конфигураций и алгебры изображений обладают комбинаторными свойствами, так же как и другие, более привычные для нас математические структуры, такие, как группы, векторные пространства, алгебры и поля. К таким комбинаторным свойствам относятся алгебраические свойства, характеризующие возможности соединения отдельных объектов друг с другом, связи, устанавливаемые между объектами с помощью преобразований подобия, и особенности восприятия этих объектов идеальным наблюдателем.

Алгебраизация теории образов проходит младенческий период развития, однако с момента ее зарождения в середине шестидесятых годов было очевидно, что общеалгебраические понятия могут способствовать упрощению теоретического анализа. Именно поэтому автор и ввел термин «алгебра изображений».

В данной главе будет показано, каким образом понятия теории классов образов можно представить с помощью языка универсальной алгебры. Комбинации конфигураций или изображений являются допустимыми только в том случае, если получаемый результат удовлетворяет условиям регулярности. Очевидно, что основные операции определены не для всех значений аргументов, а лишь частично. Это обстоятельство осложняет изучение гомоморфизмов, соотношений конгруэнтности и т. п., поскольку для таких понятий существует более чем одно естественное определение; эта трудность не возникает в связи с полугруппами, группами, векторными пространствами и т. д. Поэтому мы будем иметь дело с частичными универсальными алгебрами.

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

справиться с колоссальным разнообразием и изменчивостью регулярных структур.

Как и во всех алгебраических теориях, в нашем случае роль гомоморфизма очень существенна и мы будем изучать их применительно ко многим регулярным структурам и на уровне конфигурации, и для индуцированных отображений изображений. Это приведет нас к представлению о пространствах конфигураций и алгебрах изображений как категориях и рассмотрению нескольких соответствующих функторов. Хотя это, несомненно, шаг в правильном направлении, совершенно очевидно, что мы лишь слегка прошлись по поверхности, под которой лежит богатый пласт алгебраической структуры, еще ожидающий разработки.

Все рассматриваемые нами регулярные структуры построены из неделимых элементов — образующих, соединенных в определенном порядке таким образом, что наблюдатель воспринимает регулярность. Эта регулярность может иметь как глобальный, так и локальный характер; тип соединения определяет регулярность глобального типа, а отношение связей — регулярность локального типа.

Задание глобальной регулярности будет весьма подробно обсуждаться в следующем разделе, и мы не будем сейчас предвосхищать это обсуждение. А пока тщательно рассмотрим локальную регулярность, опираясь на показатели связи, и поставим ряд вопросов, ответы на которые следует получить прежде, чем мы перейдем к определению конфигураций на глобальном уровне.

Напомним некоторые сведения из гл. 1 и 2 первого тома. Образующая представляет собой непроизводный информационный элемент. Образующая содержит некоторую совокупность информации, которую можно представить с помощью функции признаков

Выделим некоторые особенно важные из этих признаков. Индекс класса образующих разбивает множество образующих на непересекающиеся подмножества и мы имеем некоторое разбиение инвариантное относительно преобразований, входящих в группу преобразований подобия Индекс класса образующих служит для того, чтобы разделять образующие, отличающиеся друг от друга коренным образом.

Образующая может быть снабжена также и некоторым идентификатором, предназначенным для того, чтобы помечать образующие, входящие в конфигурацию с. Если все образующие конфигурации с различны, то никаких проблем не возникает и можно воспользоваться любой системой меток, например обозначать образующие с помощью нижнего индекса , по крайней мере в тех случаях, когда конечна, что и будет для простоты предполагаться на протяжении всего настоящего тома (можно также рассматривать и случай бесконечной арности). В противоположном случае, когда регулярная структура позволяет включение в конфигурацию идентичных образующих необходимо проявлять

большую осторожность. При этом необходимо установить, располагают ли эти образующие каким-либо идентификатором, и последующий синтез образов зависит от этого решения. В следующем разделе мы вернемся к этой проблеме в связи с системами координат для конфигураций.

Сейчас мы займемся признаками, определяющими локальную регулярность, а именно связями. Связи любой образующей определяются как

где представляет структуру связей, показатели связей.

В соотношении может быть представлена некоторым вектором длины элементами которого являются параметры структуры связей, принимающие значения типа in (входной) и out (выходной), «активный» и «пассивный», просто натуральные числа; их значениями могут быть и комбинации таких значений. Необходимо пометить связи образующей с помощью какой-нибудь координаты для того, чтобы можно было однозначно указывать соответствующую связь; способ же выбора координаты несуществен, пока мы сохраняем информацию о значениях параметров связи. Этот вопрос будет рассмотрен в настоящем разделе ниже. Мы будем говорить об интересующей нас связи как о «связи образующей где координата соответствующей связи.

Множество должно иметь ту же мощность, что и множество мы будем говорить, что «показатель связи равен . Допустимыми значениями Р служат элементы некоторого пространства которое может изменяться в соответствии с изменениями величины

Мы будем изучать регулярности двух типов, причем соответствующая терминология несколько отличается от использовавшейся в томе «Синтез образов».

Определение 3.1.1.

Регулярность называется симметрической в тех случаях, когда все связи являются неориентированными, а отношение связи симметрическое.

Регулярность называется ориентированной в тех случаях, когда все связи являются ориентированными, т. е. либо входными, либо выходными, соответственно

В случае арность образующей не разделяется на входную и выходную. В случае входные связи присоединяются исключительно к выходным и наоборот.

Рассмотрим несколько примеров, иллюстрирующих смысл Определения 3.1.1, начав при этом с простейших.

Пример 3.1.1. Образующая сформирована из некоторого дискретного «интервала»

содержащего целых чисел, причем Кроме того,

Пример 3.1.2. же самое, что и в предыдущем примере, но образующая включает также и ординаты (действительные) вместе с прежними значениями.

Пример 3.1.3. Образующая представляет собой некоторый (обычный) интервал где целые числа, Кроме того,

Пример 3.1.4. же самое, что и в предыдущем примере, но образующая к тому же описывает некоторую функцию действительного переменного по-прежнему Кроме того,

Пример 3.1.5. Образующая представляет собой некоторый прямоугольник со сторонами единичной длины и углами, расположенными в узлах целочисленной решетки . Пусть причем (сторона , и т.д., ). Множество состоит из элементов пространства описывающих такие стороны. Связи в точках — выходные, а в точках входные.

Пример 3.1.6. То же самое, что и в предыдущем случае, за исключением того, что непрерывная функция действительного переменного, заданная на прямоугольнике; структура связей та же, что и в предыдущем случае, причем , показатели на этой стороне), и т. д.

Рис. 3.1.1

Отметим, что элементами множества являются стороны и функции, представляющие собой сужение на эти стороны.

Пример 3.1.7. То же самое, что в примерах 3.1.5 и 3.1.6, за исключением того, что прямоугольники заменены треугольниками (см. рис. 3.1.1) с индексом класса образующих, принимающим значения «верхний» или «нижний». Образующая представляет собой либо верхний треугольник с углами

образовано соответствующими описаниями сторон, либо нижний треуюлышк, определенный таким же образом. В данном случае представляет стороны. При значении связи в точке являются выходными, а в точках входными. При связи в являются входными, а остальные ориентированы вовне.

Пример 3.1.8. То же самое, что в предыдущем случае, за исключением того, что некоторая непрерывная функция действительного переменного, заданная на треугольнике, так что в число показателей связи включается сужение на стороны.

Пример 3.1.9. Пусть описывает ветви некоторого конечного автомата, а показатели связей равны числу состояний в начале и конце ориентированной ветви соответственно. В данном случае пространство состояний автомата.

Пример 3.1.10. Пусть описывает некоторое правило подстановки бесконтекстного языка, «произвольная конечная величина». В данном случае

и выходные связи упорядочены указанным способом. Кроме того,

порядок в данном случае также указывается. Здесь нетерминальных символов

Пример 3.1.11. Пусть представляет функции, допустим вычислительные модули; «число аргументов «число результатов», так что мы записываем

Соответствующие показатели связей представляют собой области определения и значений которые часто можно рассматривать в качестве подмножеств некоторых больших пространств образующая в последнем случае определяется как частичная функция, осуществляющая отображение из , где р - входная, a q - выходная арности.

Мы уже отмечали, что образующие, объединенные в регулярную конфигурацию, не всегда снабжены метками, позволяющими различать эти образующие. Точно таким же образом может оказаться, что связи какой-то определенной образующей не будут различаться.

Чтобы пояснить, рассмотрим схемы образующих, приведенные на рис. 3.1.2. Рис. 3.1.2(a) иллюстрирует пример 3.1.4: рассматривается функция определенная на интервале Арность в данном случае равна двум, и вопрос о возможности различать две связи разрешается немедленно: одна из связей является входной, а другая — выходной.

Рис. 3.1.2

На рис. 1.3.2(б) образующая является правилом подстановки бесконтекстной грамматики, преобразующим группу существительного в цепочку синтаксических переменных; здесь Опр - «определитель», Прил — «прилагательное», Сущ - «существительное». В этом случае имеется единственная входная связь, которая идентифицируется непосредственно. Три выходные связи также можно отличить друг от друга, поскольку в данном случае они упорядочены. Это остается справедливым даже при равенстве двух показателей связей, например при наличии двух прилагательных.

На рис. 3.1.2(в) ситуация, однако, меняется. В данном случае образующая представляет арифметический модуль, вычисляющий сумму двух функций действительного переменного, область значений которых, так же как и области определения, представляют собой ось действительных чисел. Две входные связи не поддаются различению: показатели связей одинаковы и перестановка двух аргументов не изменяет результата.

Если задана образующая со связями В, то в общем случае мы будем обозначать через множество перестановок фактически не изменяющих связи, а приводящих лишь к изменению меток. Очевидно, что формирует

группу, а именно группу связей образующей . В частном случае, когда такая группа содержит только единицу, все связи могут быть определены однозначно; этот случай будет нам встречаться часто.

Очевидно, что в случае, представленном на рис. является подгруппой порядка два симметрической группы ; в случаях, представленных рис. 3.1.2(a) и (б), .

Пусть образующая рассматривается в качестве кандидата для соединения с некой конфигурацией с, т. е. мы пытаемся соединить некоторые из внешних связей с с подмножеством В множества мы хотим установить взаимно однозначное отношение между связями и некоторыми внешними связями конфигурации с. Если то маркировка связей образующей неоднозначна, и это обстоятельство следует иметь в виду при определении соединения при помощи координат связей. Мы только что сформулировали подобный принцип, состоящий в том, что выбор системы координат не должен влиять на суть дела.

Маркировка связей однозначна по модулю Пусть нам удалось задать биективное отображение между связями двух образующих имеющих одинаковую арность, так что соответствующие связи (структура связей и показатели связей) одинаковы. В таком случае изоморфны относительно связей (символически этот факт записывается как но, естественно, они могут очень существенно различаться по другим признакам.

Если речь идет о локальной регулярности, то возможность присоединения образующей к некоторой конфигурации полностью определяется множеством . В связи с этим естественно ввести следующее определение.

Определение 3.1.2. Две образующие называются локально конгруэнтными, если эти образующие изоморфны относительно связей.

Совершенно очевидно, что речь здесь идет об отношении эквивалентности и, следовательно, оно разбивает множество образующих на классы взаимно (локально) конгруэнтных образующих. Следует, однако, заметить, что данное понятие не идентично конгруэнтности конфигураций, введенной в первом томе; в данном случае глобальную регулярность мы оставляем в стороне.

Напомним в этой связи, что все преобразования подобия сохраняют структуру связей и индекс класса образующих и осуществляют биективное отображение Рассмотрим множество всех биективных отображений обеспечивающих инвариантность связей (как структуры связей, так и показателей связей) и индекса класса образующих. Нетрудно убедиться в том, что они образуют некоторую группу— конгруэнтных преобразований

подобия. Всякая регулярная конфигурация сохраняет регулярность при «пульсациях», возникающих в результате воздействия конгруэнтных преобразований подобия . Отметим, что в общем случае преобразований подобия это сохранение регулярности обычно не имеет места.

Продолжим наше обсуждение и рассмотрим следующие два примера.

Пример 3.1.12. Каждая образующая снабжена четырьмя связями, помеченными координатами, например для выходных связей и для входных. Соответствующие показатели связей совпадают с координатами связей.

Поскольку все четыре показателя связей различны, и, следовательно, связи можно отличить друг от друга. При

Эти образующие можно использовать для формирования конфигураций, топологически эквивалентных подмножествам квадратной решетки на плоскости; для этого необходимо воспользоваться дополнительным условием глобальной регулярности, которое будет введено позже.

Особенность данного примера по сравнению с примером 3.1.5 заключается в том, что в последнем показатели связей более информативны: они содержат информацию о местоположении. Таким образом, соответствующие образующие можно интерпретировать как единичные квадраты с заданным местоположением, в примере же 3.1.12 образующие — это просто единичные квадраты. Подобные внешне безобидные различия будут встречаться нам во многих случаях.

Пример 3.1.13. Образующие представляют собой замкнутые полуплоскости в пространстве «ориентация границы». При условии, что со показатели связей образующей равны а, тип соединения и отношение связи «неравный», мы получаем описания выпуклых множеств. Смысл такой регулярности («полный», «неравный») заключается в том, чтобы избежать включения в описание лишних образующих (см. Случай 2.9.1 из т. 1); по этой же причине та же самая регулярность естественно возникает и во многих других ситуациях. Для того чтобы уменьшить значение простоты описания, можно обратиться к регулярности более широкого типа «свободный».

Мы приводим здесь пример 3.1.13, поскольку он показывает, каким образом использовать локальную регулярность (например,

в тех случаях, когда могла бы использоваться глобальная регулярность, — посредством выбора типа соединения 2, предусматривающего построение регулярных конфигураций только при помощи соединения образующих с различными индексами класса. Последнее возможно, поскольку 2 допускает использование информации о значениях а. Таким образом, иногда мы можем выбирать между использованием локальной и глобальной регулярности при достижении некоторой определенной цели.

В качестве подготовки к подробному обсуждению глобальной регулярности рассмотрим некоторую заданную образующую . Будем пренебрегать локальными условиями: в результате показатели связей перестают играть какую-либо роль. Вся глобальная информация, касающаяся заключена, таким образом, в структуре связей и индексе класса образующей Эта информация, записываемая символически как остов образующей

представляет глобальную связность образующей Все значения (3.1.7), соответствующие вариациям в пределах множества образуют некоторое множество

Глобальная связность абстрагирована от всех признаков, за исключением структуры связей и индекса класса образующих. Поскольку вся остальная информация исключена, мы представим схематически остов как основной узел — зачерненный кружок (снабженный значением а) вкупе со связями, снабженными координатами. Глобальная связность образующих, приведенных на рис. 3.1.2, будет в таком случае иметь вид, представленный на рис. 3.1.3.

Для схем, изображенных на этом рисунке, выбор координат связей осуществляется по-разному. На схемах и связи должны поддаваться идентификации, как описано выше, но координаты 1, 2 связей могут переставляться относительно Классы таких остовов образующих будут служить отправной точкой для обсуждения глобальной регулярности — типов соединения — в разд. 3.2 и 3.3.

Рис. 3.1.3

Точно так же как связи образующей не всегда однозначно определяются структурой и показателями связей, связи остова могут оказаться неразличимыми подобно тому, как это имеет место на рис. 3.1.3(в) для входных связей. Представлена группа

перестановок, фактически не изменяющая связи, за исключением изменения маркировки при помощи Отметим, что является подгруппой при .

Если заданы два семейства образующих мы, естественно, можем задать обычные теоретико-множественные операции и т. п. В дополнение к ним у нас иногда будет возможность применять и другие операции. Одна из таких операций — произведение семейств образующих — формирует множество всех упорядоченных пар причем структура связей задается объединением

а соответствующие показатели связей—объединением

что обеспечивает естественную связь между новыми координатами связей и новыми показателями связей. Кроме того,