Глава 2. Конфигурации

2.1. Правила и ограничения

Комбинаторная теория образов предусматривает структурное объединение стандартных блоков — образующих — в конфигурации.

Конфигурация определяется составом и структурой. Две конфигурации считаются идентичными только в том случае, если и их составы, и их структуры совпадают.

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

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

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

В гл. 5 мы введем еще и меру сложности для изображений, однако уже сейчас мы введем

Определение 2.1.1. Будем говорить, что при заданном множестве образующих и двух системах структурная сложность

конфигураций, регулярных в смысле больше структурной сложности конфигураций, регулярных в смысле , если .

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