Частичный циклический порядок

В математике частичный циклический порядок — это троичное отношение , которое обобщает циклический порядок таким же образом, как частичный порядок обобщает линейный порядок .

Определение

Над данным набором частичный циклический порядок представляет собой троичное отношение. $R$ то есть:

• циклический , т. е. он инвариантен относительно циклической перестановки : $R(x,y,z)\Rightarrow R(y,z,x)$
• асимметричный : $R(x,y,z)\Rightarrow \not R(z,y,x)$
• переходный : $R(x,y,z)$ и $R(x,z,u)\Rightarrow R(x,y,u)$

Конструкции

Прямая сумма

Прямой продукт

Власть

Завершение Дедекинда – МакНила

Расширения

линейное расширение , теорема о продолжении Шпильрайна

стандартный пример

Отношения между частичными и полными циклическими порядками более сложны, чем отношения между частичными и полными линейными порядками. Начнем с того, что не каждый частичный циклический порядок можно расширить до полного циклического порядка. Примером может служить следующее отношение к первым тринадцати буквам алфавита: { acd, bde, cef, dfg, egh, fha, gac, hcb } ∪ { abi, cij, bjk, ikl, jlm, kma, lab, mbc } . Это отношение представляет собой частичный циклический порядок, но его нельзя расширить с помощью abc или cba ; любая попытка приведет к противоречию.

Вышеупомянутый пример был относительно мягким. Можно также построить частичные циклические порядки с препятствиями более высокого порядка, так что, например, можно добавить любые 15 троек, а 16-ю — нет. Фактически, циклическое упорядочение является NP-полным , поскольку оно решает 3SAT . Это резко контрастирует с проблемой распознавания линейных порядков, которую можно решить за линейное время .

Ссылки

• Галил, Цви ; Мегиддо, Нимрод (октябрь 1977 г.), «Циклический порядок NP-полный» (PDF) , Theoretical Computer Science , 5 (2): 179–182, doi : 10.1016/0304-3975(77)90005-6 , получено 30 апреля. 2011 год
• Мегиддо, Нимрод (март 1976 г.), «Частичные и полные циклические порядки» (PDF) , Бюллетень Американского математического общества , 82 (2): 274–276, doi : 10.1090/S0002-9904-1976-14020-7 , получено 30 апреля 2011 г.
• Новак, Витезслав (1982), «Циклически упорядоченные множества» (PDF) , Чехословацкий математический журнал , 32 (3): 460–473, doi : 10.21136/CMJ.1982.101821 , hdl : 10338.dmlcz/101821 , получено 30 апреля 2011 г.
• Новак, Витезслав; Новотны, Мирослав (1984a), «О степени циклически упорядоченных множеств» (PDF) , Časopis Pro Pěstování Matematiky , 109 (4): 421–424, doi : 10.21136/CPM.1984.118209 , hdl : 10338.dmlcz/118209 , получено 30 апреля 2011 г.
• Новак, Витезслав; Новотны, Мирослав (1984b), «Универсальные циклически упорядоченные множества» (PDF) , Чехословацкий математический журнал , 35 (1): 158–161, doi : 10.21136/CMJ.1985.102004 , hdl : 10338.dmlcz/102004 , получено 30 апреля 2011 г.

Дальнейшее чтение

• Аллес, Питер; Нешетржил, Ярослав; Поляк, Святоплук (1991), «Расширяемость, размерности и диаграммы циклических порядков», SIAM Journal on Discrete Mathematics , 4 (4): 453–471, doi : 10.1137/0404041
• Бандельт, Ганс-Юрген; Чепой, Виктор; Эппштейн, Дэвид (2010), «Комбинаторика и геометрия конечных и бесконечных квадратов» (PDF) , SIAM Journal on Discrete Mathematics , 24 (4): 1399–1440, arXiv : 0905.4537 , doi : 10.1137/090760301 , S2CID   10788524 , получено 23 мая 2011 г.
• Чайда, Иван; Новак, Витезслав (1985), «О расширениях циклических порядков» (PDF) , Časopis Pro Pěstování Matematiky , 110 (2): 116–121, doi : 10.21136/CPM.1985.108597 , hdl : 10338.dmlcz/108597 , получено 30 апрель 2011 г.
• Фишберн, ПК ; Вудалл, Д.Р. (июнь 1999 г.), «Приказы цикла», Order , 16 (2): 149–164, doi : 10.1023/A:1006381208272 , S2CID   37680085
• Хаар, Стефан (2001), «Циклические модели и модели частичного порядка для параллелизма» (PDF) , Геометрия и топология в теории параллелизма GETCO '01 , стр. 51–62 , получено 23 мая 2011 г.
• Иль, Пьер; Руэ, Пол (30 апреля 2008 г.), «Циклические расширения порядковых многообразий», Электронные заметки по теоретической информатике , 212 : 119–132, CiteSeerX   10.1.1.103.2305 , doi : 10.1016/j.entcs.2008.04.057
• Якубик, Ян (1994), «О расширенных циклических порядках» (PDF) , Чехословацкий математический журнал , 44 (4): 661–675, doi : 10.21136/CMJ.1994.128486 , hdl : 10338.dmlcz/128486 , получено 30 апреля 2011 г.
• Мельес, Поль-Андре (2004), «Критерий топологической корректности некоммутативной логики» (PDF) , в книге Томаса Эрхарда и Жан-Ива Жирара, а также Поля Рюэ и Филипа Скотта (ред.), Linear Logic in Computer Science , стр. . 283–323 , получено 23 мая 2011 г.
• Новак, Витезслав (1984), «О некоторой минимальной проблеме» (PDF) , Archivum Mathematicum , 20 (2): 95–99, hdl : 10338.dmlcz/107191 , MR   0784860 , Zbl   0554.06003 , получено 23 мая 2011 г.
• Штер, Марк-Оливер (1998), «Циклическое мышление», Дезель, Йорг; Сильва, Мануэль (ред.), ICATPN '98, Материалы 19-й Международной конференции по применению и теории сетей Петри , Конспекты лекций по информатике, том. 1420, стр. 205–225, номер документа : 10.1007/3-540-69108-1_12 , ISBN.  3-540-64677-9
• Хаар, Стефан (2016), «Циклическое упорядочение посредством частичных порядков» (PDF) , Журнал многозначной логики и мягких вычислений , 27 (2–3), Old City Publishing: 209–228