Последовательно-параллельный частичный порядок

В теоретико-порядковой математике последовательно-параллельный частичный порядок — это частично упорядоченный набор, построенный из меньших последовательно-параллельных частичных порядков с помощью двух простых операций композиции. ^[1]^[2]

Последовательно-параллельные частичные порядки можно охарактеризовать как N-свободные конечные частичные порядки; они имеют размерность порядка не более двух. ^[1]^[3] Они включают слабые порядки и отношение достижимости в направленных деревьях и направленных последовательно-параллельных графах . ^[2]^[3] Графы сравнимости последовательно-параллельных частичных порядков являются кографами . ^[2]^[4]

Последовательно-параллельные частичные заказы применялись в планировании работ на месте , ^[5] машинном обучении последовательности событий в данных временных рядов , ^[6] последовательности передачи мультимедийных данных, ^[7] и максимизации пропускной способности в программировании потоков данных . ^[8]

Последовательно-параллельные частичные порядки также называются мультидеревьями; ^[4] однако это название неоднозначно: мультидеревьями также называют частичные порядки без четырехэлементного ромбовидного подпорядка ^[9] и другие структуры, образованные из нескольких деревьев.

Определение

Рассмотрим $P$ и $Q$ , два частично упорядоченных множества . Композиция серий $P$ и $Q$ , записанная как $P; Q$ , ^[7] $P * Q$ , ^[2] или $P ⧀ Q$ , ^[1], — это частично упорядоченное множество, элементы которого являются несвязным объединением элементов $P$ и $Q$ . В $P; Q$ два элемента $x$ и $y$ , которые оба принадлежат $P$ или оба принадлежат $Q ,$ имеют то же самое отношение порядка, что и в $P$ или $Q$ соответственно. Однако для каждой пары $x$ , $y$ , где $x$ принадлежит $P$ , а $y$ принадлежит $Q$ , в композиции серий существует дополнительное отношение порядка $x \leq y$ . Композиция серий — это ассоциативная операция : можно записать $P; Q; R$ как композицию серий трех порядков, без двусмысленности относительно того, как их попарно объединять, потому что обе скобки $(P; Q); R$ и $P; (Q; R)$ описывают один и тот же частичный порядок. Однако это не коммутативная операция , поскольку перестановка ролей $P$ и $Q$ создаст другой частичный порядок, который меняет порядок пар с одним элементом в $P$ и одним в $Q.$ ^[1 ]

Параллельная композиция $P$ и $Q$ , записанная как $P || Q$ , ^[7] $P + Q$ , ^[2] или $P \oplus Q$ , ^[1] определяется аналогично, из несвязного объединения элементов в $P$ и элементов в $Q$ , с парами элементов, которые оба принадлежат $P$ или оба принадлежат $Q,$ имеющими тот же порядок, что и в $P$ или $Q$ соответственно. В $P || Q$ пара $x$ , $y$ несравнима, если $x$ принадлежит $P$ , а $y$ принадлежит $Q.$ Параллельная композиция является как коммутативной, так и ассоциативной. ^[1]

Класс последовательно-параллельных частичных порядков — это множество частичных порядков, которые могут быть построены из одноэлементных частичных порядков с использованием этих двух операций. Эквивалентно, это наименьшее множество частичных порядков, которое включает одноэлементный частичный порядок и замкнуто относительно операций последовательной и параллельной композиции. ^[1]^[2]

Слабый порядок — это последовательный параллельный частичный порядок, полученный из последовательности операций композиции, в которой сначала выполняются все параллельные композиции, а затем результаты этих композиций объединяются с использованием только последовательных композиций. ^[2]

Запрещенная характеристика подотряда

Частичный порядок $N$ с четырьмя элементами $a$ , $b$ , $c$ , и $d$ и ровно тремя отношениями порядка $a \leq b \geq c \leq d$ является примером забора или зигзагообразного частично упорядоченного множества; его диаграмма Хассе имеет форму заглавной буквы «N». Он не является последовательно-параллельным, потому что нет способа разбить его на последовательную или параллельную композицию двух меньших частичных порядков. Частичный порядок $P$ называется N-свободным, если не существует множества из четырех элементов в $P$ такого, что ограничение $P$ на эти элементы является порядково-изоморфным $N$ . Последовательно-параллельные частичные порядки являются в точности непустыми конечными N-свободными частичными порядками. ^[1]^[2]^[3]

Из этого немедленно следует (хотя это можно доказать и напрямую), что любое непустое ограничение последовательно-параллельного частичного порядка само является последовательно-параллельным частичным порядком. ^[1]

Размер заказа

Размерность порядка частичного порядка $P$ — это минимальный размер реализатора $P$ , множества линейных расширений $P$ со свойством, что для любых двух различных элементов $x$ и $y$ из $P$ , $x \leq y$ в $P$ тогда и только тогда, когда $x$ имеет более раннюю позицию, чем $y$ в каждом линейном расширении реализатора. Последовательно-параллельные частичные порядки имеют размерность порядка не более двух. Если $P$ и $Q$ имеют реализаторы ${L 1, L 2}$ и ${L 3, L 4}$ соответственно, то ${L 1 L 3, L 2 L 4}$ является реализатором последовательной композиции $P; Q$ , а ${L 1 L 3, L 4 L 2}$ является реализатором параллельной композиции $P || Q$ . ^[2]^[3] Частичный порядок является последовательно-параллельным тогда и только тогда, когда он имеет реализатор, в котором одна из двух перестановок является тождественной, а другая — отделимой перестановкой .

Известно, что частичный порядок $P$ имеет размерность два тогда и только тогда, когда существует сопряженный порядок $Q$ на тех же элементах, со свойством, что любые два различных элемента $x$ и $y$ сравнимы ровно по одному из этих двух порядков. В случае последовательно-параллельных частичных порядков сопряженный порядок, который сам по себе является последовательно-параллельным, может быть получен путем выполнения последовательности операций композиции в том же порядке, что и те, которые определяют $P$ на тех же элементах, но выполняя последовательную композицию для каждой параллельной композиции в разложении $P$ и наоборот. Более строго, хотя частичный порядок может иметь много различных сопряженных элементов, каждый сопряженный элемент последовательно-параллельного частичного порядка сам по себе должен быть последовательно-параллельным. ^[2]

Связь с теорией графов

Любой частичный порядок может быть представлен (обычно более чем одним способом) направленным ациклическим графом , в котором существует путь из $x$ в $y$ , когда $x$ и $y$ являются элементами частичного порядка с $x \leq y$ . Графы, которые представляют последовательно-параллельные частичные порядки таким образом, называются вершинно-последовательно-параллельными графами, а их транзитивные редукции (графы покрывающих отношений частичного порядка) называются минимальными вершинно-последовательно-параллельными графами. ^[3] Направленные деревья и (двухтерминальные) последовательно-параллельные графы являются примерами минимальных вершинно-последовательно-параллельных графов; поэтому последовательно-параллельные частичные порядки могут использоваться для представления отношений достижимости в направленных деревьях и последовательно-параллельных графах. ^[2]^[3]

Граф сравнимости частичного порядка — это неориентированный граф с вершиной для каждого элемента и неориентированным ребром для каждой пары различных элементов $x$ , $y$ с $x \leq y$ или $y \leq x$ . То есть он образован из минимального вершинного последовательно-параллельного графа путем забывания ориентации каждого ребра. Граф сравнимости последовательно-параллельного частичного порядка — это кограф : последовательные и параллельные операции композиции частичного порядка порождают операции на графе сравнимости, которые образуют несвязное объединение двух подграфов или которые соединяют два подграфа всеми возможными ребрами; эти две операции являются основными операциями, из которых определяются кографы. И наоборот, каждый кограф является графом сравнимости последовательно-параллельного частичного порядка. Если частичный порядок имеет кограф в качестве своего графа сравнимости, то он должен быть последовательно-параллельным частичным порядком, поскольку любой другой вид частичного порядка имеет N-подпорядок, который соответствовал бы индуцированному четырехвершинному пути в его графе сравнимости, а такие пути запрещены в кографах. ^[2]^[4]

Сложность вычислений

Характеристика запрещенного подпорядка последовательно-параллельных частичных порядков может быть использована в качестве основы для алгоритма, который проверяет, является ли заданное бинарное отношение последовательно-параллельным частичным порядком, за время, линейно зависящее от числа связанных пар. ^[2]^[3] В качестве альтернативы, если частичный порядок описывается как порядок достижимости направленного ациклического графа , можно проверить, является ли он последовательно-параллельным частичным порядком, и если это так, вычислить его транзитивное замыкание за время, пропорциональное числу вершин и ребер в транзитивном замыкании; остается открытым вопрос, можно ли улучшить время распознавания последовательно-параллельных порядков достижимости, сделав его линейным по размеру входного графа. ^[10]

Если последовательно-параллельный частичный порядок представлен как дерево выражений, описывающее операции последовательной и параллельной композиции, которые его сформировали, то элементы частичного порядка могут быть представлены листьями дерева выражений. Сравнение между любыми двумя элементами может быть выполнено алгоритмически путем поиска наименьшего общего предка соответствующих двух листьев; если этот предок является параллельной композицией, два элемента несравнимы, а в противном случае порядок операндов последовательной композиции определяет порядок элементов. Таким образом, последовательно-параллельный частичный порядок на $n$ элементах может быть представлен в $O (n)$ пространстве с $O (1)$ временем для определения любого значения сравнения. ^[2]

$Для двух заданных последовательно-параллельных частичных порядков P$ и $Q$ проверка того, содержит ли $P$ ограничение, изоморфное $Q$ , является NP-полной задачей . ^[3]

Хотя задача подсчета числа линейных расширений произвольного частичного порядка является #P-полной , ^[11] она может быть решена за полиномиальное время для последовательно-параллельных частичных порядков. В частности, если $L (P)$ обозначает число линейных расширений частичного порядка $P$ , то $L (P; Q) = L (P) L (Q)$ и

L(P||Q)={\frac {(|P|+|Q|)!}{|P|!|Q|!}}L(P)L(Q),

поэтому число линейных расширений можно вычислить с помощью дерева выражений с той же формой, что и дерево разложения данного последовательно-параллельного порядка. ^[2]

Приложения

Mannila & Meek (2000) используют последовательно-параллельные частичные порядки в качестве модели для последовательностей событий в данных временных рядов . Они описывают алгоритмы машинного обучения для вывода моделей этого типа и демонстрируют их эффективность при выводе предварительных условий курса из данных о зачислении студентов и при моделировании шаблонов использования веб-браузера. ^[6]

Амер и др. (1994) утверждают, что последовательно-параллельные частичные порядки хорошо подходят для моделирования требований к последовательности передачи мультимедийных презентаций. Они используют формулу для вычисления количества линейных расширений последовательно-параллельного частичного порядка в качестве основы для анализа алгоритмов передачи мультимедиа. ^[7]

Choudhary et al. (1994) используют последовательно-параллельные частичные порядки для моделирования зависимостей задач в модели потока данных массовой обработки данных для компьютерного зрения . Они показывают, что, используя последовательно-параллельные порядки для этой проблемы, можно эффективно построить оптимизированный график, который назначает различные задачи различным процессорам параллельной вычислительной системы для оптимизации пропускной способности системы. ^[8]

Класс упорядочений, несколько более общий, чем последовательно-параллельные частичные порядки, предоставляется PQ-деревьями , структурами данных, которые применяются в алгоритмах для проверки того, является ли граф планарным , и распознавания интервальных графов . ^[12] Узел P PQ-дерева допускает все возможные упорядочения своих потомков, такие как параллельная композиция частичных порядков, в то время как узел Q требует, чтобы потомки встречались в фиксированном линейном порядке, таком как последовательная композиция частичных порядков. Однако, в отличие от последовательно-параллельных частичных порядков, PQ-деревья допускают обратный линейный порядок любого Q- узла.

Смотрите также

Последовательные и параллельные цепи

Ссылки

^ abcdefghi Беше, Денис; Де Гроот, Филипп; Реторе, Кристиан (1997), «Полная аксиоматизация для включения последовательно-параллельных частичных порядков», Rewriting Techniques and Applications , Lecture Notes in Computer Science, т. 1232, Springer-Verlag, стр. 230–240, doi :10.1007/3-540-62950-5_74, ISBN 978-3-540-62950-4.
^ abcdefghijklmno Möhring, Rolf H. (1989), «Вычислительно трактуемые классы упорядоченных множеств», в Rival, Ivan (ред.), Algorithms and Order: Proceedings of the NATO Advanced Study Institute on Algorithms and Order, Оттава, Канада, 31 мая - 13 июня 1987 г. , NATO Science Series C, т. 255, Springer-Verlag, стр. 105–194, ISBN 978-0-7923-0007-6.
^ abcdefgh Вальдес, Хакобо; Тарьян, Роберт Э .; Лоулер, Юджин Л. (1982), «Распознавание серийных параллельных орграфов», SIAM Journal on Computing , 11 (2): 298–313, doi : 10.1137/0211023.
^ abc Юнг, HA (1978), «О классе частично упорядоченных множеств и соответствующих графах сравнимости», Журнал комбинаторной теории, Серия B , 24 (2): 125–133, doi : 10.1016/0095-8956(78)90013-8 , MR 0491356.
^ Лоулер, Юджин Л. (1978), «Упорядочение заданий для минимизации общего взвешенного времени завершения с учетом ограничений предшествования», Annals of Discrete Mathematics , 2 : 75–90, doi :10.1016/S0167-5060(08)70323-6, ISBN 9780720410433, МР 0495156.
^ ab Mannila, Heikki ; Meek, Christopher (2000), "Глобальные частичные порядки из последовательных данных", Proc. 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD 2000) , стр. 161–168, doi : 10.1145/347090.347122 , S2CID 14735932.
^ abcd Амер, Пол Д.; Шассо, Кристоф; Коннолли, Томас Дж.; Диас, Мишель; Конрад, Филлип (1994), «Транспортная служба частичного порядка для мультимедиа и других приложений», IEEE/ACM Transactions on Networking , 2 (5): 440–456, doi :10.1109/90.336326, S2CID 1974607.
^ ab Choudhary, AN; Narahari, B.; Nicol, DM; Simha, R. (1994), "Оптимальное назначение процессора для класса конвейерных вычислений", IEEE Transactions on Parallel and Distributed Systems , 5 (4): 439–445, doi :10.1109/71.273050, S2CID 5588390.
^ Фурнас, Джордж У.; Закс, Джефф (1994), «Мультидеревья: обогащение и повторное использование иерархической структуры», Труды конференции SIGCHI по человеческому фактору в вычислительных системах (CHI '94) , стр. 330–336, doi : 10.1145/191666.191778 , S2CID 18710118.
^ Ма, Цзы-Хэн; Спинрад, Джереми (1991), «Транзитивное замыкание для ограниченных классов частичных порядков», Order , 8 (2): 175–183, doi :10.1007/BF00383402, S2CID 120935610.
^ Брайтвелл, Грэм Р.; Винклер, Питер (1991), «Подсчет линейных расширений», Order , 8 (3): 225–242, doi :10.1007/BF00383444, S2CID 119697949.
^ Бут, Келлогг С.; Люкер, Джордж С. (1976), «Тестирование свойства последовательных единиц, интервальных графов и планарности графа с использованием алгоритмов PQ-дерева», Журнал компьютерных и системных наук , 13 (3): 335–379, doi : 10.1016/S0022-0000(76)80045-1.