Cтраница 1
Множество входных последовательностей, распознаваемых М2, обозначим через В. Согласно Хартманису и Стирнзу [2, 3], переход от двумерной реализации к одномерной требует самое большее квадрата времени вычисления. Теперь мы желаем найти нижнюю границу времени вычисления одномерной машины, которая распознает В. [1]
Пусть множество входных последовательностей, распознаваемых Мт, обозначено через Wm. Множество Wm распознаваемо m - мерной машиной в реальное время. Но какое время нужно машине с меньшим числом измерений, чтобы распознать его. [2]
Определим R как множество входных последовательностей длины п для всех п, таких, что n - й член w есть единица. [3]
Описываются приведенные перестановочные автоматы, реализующие отображения множества периодических входных последовательностей во множество периодических выходных последовательностей, не увеличивающие или сохраняющие введенное в работе расстояние между периодическими последовательностями. [4]
Конечный автомат определяет конечное отношение конгруэнтности на множестве входных последовательностей. Для каждой входной последовательности автомат начинает поочередно работать из каждого начального состояния, переходя в соответствующее конечное состояние. Последовательности будут эквивалентными, если они вызывают для каждого начального состояния одинаковые переходы. Таким образом, получено отношение конгруэнтности. Множество классов эквивалентности с введенным законом композиции образует конечную полугруппу. Более удобно множество классов конгруэнтности ввести при помощи внешнего поведения автомата. Мы воспользуемся функциями типа вход-выход для того, чтобы ввести понятие эквивалентности последовательностей, а именно назовем последовательности х и у эквивалентными, если ft ( uxv) ft ( uyv) для всех fi из данного множества функций. [5]
Конечный автомат определяет правоинвариантное конечное отношение эквивалентности на множестве входных последовательностей. Входные последовательности, для которых соответствующие состояния одинаковы, будем считать эквивалентными. И наоборот, для заданного правоинвариантного конечного отношения эквивалентности на множестве входных последовательностей мы можем построить автомат с минимальным множеством состояний, который определяет отношение эквивалентности на множестве входных последовательностей, совпадающее с первоначальным. Каждому классу эквивалентности соответствует вполне определенное состояние автомата. Следует как-то выделить начальное состояние, для этого дополним множество входных последовательностей пустой последовательностью. Класс эквивалентности, содержащий элемент Л, соответствует начальному состоянию. Может так случиться, что этот класс содержит только пустую последовательность. Функция переходов определяется с помощью соотношения 8 ( Ы, аг) [ xat ], где Ы обозначает состояние, соответствующее классу эквивалентности, содержащему входную последовательность к. Приведем примеры отождествления различных входных последовательностей, когда состояния, не принадлежащие минимальному множеству, не учитываются. [6]
Для каждого двустороннего автомата А можно эффективно определить такой автомат В, который имеет то же множество приемлемых входных последовательностей, что и автомат А. [7]
Это среднее будет существовать, если при любом выборе v0 функция d ( u; u0) будет измеримой на борелевском поле множеств входных последовательностей, на котором вероятностная мера источника определена. Этот класс содержит любую функцию, представляющую какой-либо интерес для практических целей. [8]
Основной задачей автомата является реализация соответствия между входными и выходными последовательностями. Множество допустимых входных последовательностей бесконечно, поэтому не представляется возможным составить таблицу соответствия между всеми входными и выходными последовательностями. В инженерной практике законы функционирования автоматов формулируются сначала словесно или задаются с помощью временных диаграмм. Однако эти описания поведения автоматов не являются математически строгими, поэтому необходим переход к таким способам задания автоматов, которые позволили бы установить соответствие между бесконечными множествами входных и выходных последовательностей. Одним из способов задания автоматов, удобным для их синтеза, являются таблицы переходов. [9]
При уточнении понятий самоорганизации и самосовершенствования удобно пользоваться так называемым циклическим приведением автоматов. Циклическое приведение определяется для автоматов, у которых фиксировано множество допустимых входных последовательностей и произведено циклирование входной и выходной информации. Для любого автомата А при выполнении этих условий входной и выходной алфавиты могут быть заменены следующим образом: буквами нового входного алфавита Зс считаются все различные входные слова всех циклов во всех допустимых последовательностях, буквами нового выходного алфавита D аналогично считаются все различные выходн-ые слова указанных циклов. [10]
Во-вторых, интуитивно ясно, что хорошо различаться будут такие автоматы, многогранники которых имеют незначительный объем общей части. Существенным здесь является и то, насколько вероятно попадание точки, соответствующей рабочему отрезку последовательности, в общую часть обоих многогранников. Это зависит от вероятностного распределения на множестве входных последовательностей. [11]
Конечный автомат определяет правоинвариантное конечное отношение эквивалентности на множестве входных последовательностей. Входные последовательности, для которых соответствующие состояния одинаковы, будем считать эквивалентными. И наоборот, для заданного правоинвариантного конечного отношения эквивалентности на множестве входных последовательностей мы можем построить автомат с минимальным множеством состояний, который определяет отношение эквивалентности на множестве входных последовательностей, совпадающее с первоначальным. Каждому классу эквивалентности соответствует вполне определенное состояние автомата. Следует как-то выделить начальное состояние, для этого дополним множество входных последовательностей пустой последовательностью. Класс эквивалентности, содержащий элемент Л, соответствует начальному состоянию. Может так случиться, что этот класс содержит только пустую последовательность. Функция переходов определяется с помощью соотношения 8 ( Ы, аг) [ xat ], где Ы обозначает состояние, соответствующее классу эквивалентности, содержащему входную последовательность к. Приведем примеры отождествления различных входных последовательностей, когда состояния, не принадлежащие минимальному множеству, не учитываются. [12]
Конечный автомат определяет правоинвариантное конечное отношение эквивалентности на множестве входных последовательностей. Входные последовательности, для которых соответствующие состояния одинаковы, будем считать эквивалентными. И наоборот, для заданного правоинвариантного конечного отношения эквивалентности на множестве входных последовательностей мы можем построить автомат с минимальным множеством состояний, который определяет отношение эквивалентности на множестве входных последовательностей, совпадающее с первоначальным. Каждому классу эквивалентности соответствует вполне определенное состояние автомата. Следует как-то выделить начальное состояние, для этого дополним множество входных последовательностей пустой последовательностью. Класс эквивалентности, содержащий элемент Л, соответствует начальному состоянию. Может так случиться, что этот класс содержит только пустую последовательность. Функция переходов определяется с помощью соотношения 8 ( Ы, аг) [ xat ], где Ы обозначает состояние, соответствующее классу эквивалентности, содержащему входную последовательность к. Приведем примеры отождествления различных входных последовательностей, когда состояния, не принадлежащие минимальному множеству, не учитываются. [13]
При исследовании поведения машин, которые реализуют это конкретное входно-выходное преобразование, мы займемся сначала входными последовательностями, которые состоят более чем из 2й блоков некоторой общей длины &, отделенными единственной двойкой. Первые 2й блоков в такой последовательности называются базой последовательности, а оставшиеся блоки - хвостом последовательности. Выходной символ, выработанный в ответ на двойку, которая заканчивает блок в хвосте последовательности, будет рассматриваться как выход, связанный с этим блоком. Наконец, мы обозначим множество входных последовательностей, для которых соответствующая выходная последовательность заканчивается символом 1, через А. Выходы, связанные с тремя хвостовыми блоками, суть 1, 0 и 1 в порядке их появления. [14]
Конечный автомат определяет правоинвариантное конечное отношение эквивалентности на множестве входных последовательностей. Входные последовательности, для которых соответствующие состояния одинаковы, будем считать эквивалентными. И наоборот, для заданного правоинвариантного конечного отношения эквивалентности на множестве входных последовательностей мы можем построить автомат с минимальным множеством состояний, который определяет отношение эквивалентности на множестве входных последовательностей, совпадающее с первоначальным. Каждому классу эквивалентности соответствует вполне определенное состояние автомата. Следует как-то выделить начальное состояние, для этого дополним множество входных последовательностей пустой последовательностью. Класс эквивалентности, содержащий элемент Л, соответствует начальному состоянию. Может так случиться, что этот класс содержит только пустую последовательность. Функция переходов определяется с помощью соотношения 8 ( Ы, аг) [ xat ], где Ы обозначает состояние, соответствующее классу эквивалентности, содержащему входную последовательность к. Приведем примеры отождествления различных входных последовательностей, когда состояния, не принадлежащие минимальному множеству, не учитываются. [15]