Cтраница 1
Обобщенная параллельная композиция г р q процессов р, g разной длительности определяется следующим образом. [1]
Параллельная композиция алгоритмов 21, S3 заключается по существу в совместном рассмотрении их работы применительно к соответствующим исходным данным; пусть это будут слова Р и Н, соответственно. Более точно эту разновидность сочетания алгоритмов можно описать следующим образом. Допустим, что - некоторый символ, не встречающийся в алфавитах, посредством которых изображаются исходные данные и результаты алгоритмов 21, 93; тогда слова Р Н и ЩР 93 ( Я) могут применяться как изображения пар исходных слов и пар результирующих слов. [2]
Вследствие того что параллельную композицию двух автоматов с магазинной памятью нельзя преобразовать в другой автомат с магазинной памятью, контекстно-свободные языки не замкнуты по отношению к параллельной композиции. [3]
Если О - операция параллельной композиции, объединим цепи Ctl и С 2 в одну со-цепь С. Для построения цепи С достаточно вершины ю-цепей С / 1 и С / 2 упорядочить по невозрастанию их приоритетов. [4]
В работе [11] на основе теоремы о параллельной композиции [179] доказаны утверждения, дающие для некоторого класса алгоритмов достаточные условия преобразования последовательной композиции в параллельную. [5]
Переходим теперь к рассмотрению четырех важных типов сочетания алгоритмов: последовательная композиция, параллельная композиция, разветвление и повторное применение. [6]
Граф G называется разложимым, если граф G Может быть представлен в виде последовательной либо параллельной композиции двух других графов. В противном случае G называется неразложимым. Gm таковы, что граф G может быть получен из них в результате последовательного выполнения m - 1 операции последовательной и параллельной композиции. [7]
Следствие 6.1. Языки сетей Петри замкнуты по отношению к любому конечному числу выполнений операций объединения, пересечения, обращения, параллельной композиции и конкатенации, осуществляемых в любом порядке. [8]
Вследствие того что параллельную композицию двух автоматов с магазинной памятью нельзя преобразовать в другой автомат с магазинной памятью, контекстно-свободные языки не замкнуты по отношению к параллельной композиции. [9]
Доказательство теоремы 6.3 проводится индукцией по числу вершин графа G, исходя из того, что любой последовательно-параллельный граф может быть представлен в виде последовательной либо параллельной композиции двух графов Gt и G2, каждый из которых является в свою очередь последовательно-параллельным. [10]
Другое преимущество представления сети Петри связано с иными формами композиции. Например, параллельная композиция позволяет компонентам композиции автоматов работать одновременно. В этом случае вновь получаем автомат с составными состояниями, в то время как для сети Петри - это просто дублирование фишек во входах, соответствующих входным символам, и использование их во всех компонентах сети Петри. Наконец, на выходе мы просто выбираем соответствующие позиции выхода. Например, если мы хотим соединить параллельно две сети Петри ( рис. 3.13 и 3.14), то в результате получим сеть Петри, подобную изображенной на рис. 3.17, которая вычисляет дополнение числа до двух и его четность. Если на входе появляется символ сброса, то выходом является четность. [11]
Сравнение рассмотренных представлений иллюстрирует хорошую компактность и, следовательно, большое удобство автоматов при представлении дискретных систем последовательного действия. Рассмотрим, как моделируются параллельные композиции систем. [12]
Благодаря этому нетрудно показать, что автомат Crf X fx можно переписать как - hn 1 ( C f X gn) Tin. Теперь автомат Crf X gj представляет собой конечную параллельную композицию элементов из f, так. Проводя такие же рассуждения для автомата f2 X Brf, мы видим, что автомат f удовлетворяет условию предложения. Остальные этапы доказательства тривиальны. [13]
Однако с точки зрения методики программирования такое привлечение может оказаться удобным. В качестве упражнения рекомендуется доказать теорему о программировании параллельной композиции, исходя из следующей идеи. [14]
Заметим, однако, что каскадное соединение не совсем эквивалентно последовательно параллельной композиции. [15]