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

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

Определение

По данному набору частичный циклический порядок - это тернарное отношение ${\displaystyle R}$ то есть:

• циклический, т.е. это инвариантный под циклическая перестановка: ${\displaystyle R(x,y,z)\Rightarrow R(y,z,x)}$
• асимметричный: ${\displaystyle R(x,y,z)\Rightarrow \not R(z,y,x)}$
• переходный: ${\displaystyle R(x,y,z)}$ и ${\displaystyle R(x,z,u)\Rightarrow R(x,y,u)}$^[1]

Конструкции

Прямая сумма

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

Мощность^[2][3]

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

Расширения

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

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

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

Вышеприведенный пример был относительно мягким. Можно также построить частичные циклические порядки с препятствиями более высокого порядка, так что, например, любые 15 троек могут быть добавлены, а 16-я - нет. Фактически, циклический порядок НП-полный, поскольку он решает 3СБ. Это резко контрастирует с проблемой распознавания линейных порядков, которую можно решить в линейное время.^[5][6]

Примечания

1. Новак 1982.
2. Новак и Новотны 1984a.
3. Новак и Новотны 1984b.
4. Мегиддо 1976 С. 274–275.
5. Мегиддо 1976 С. 275–276.
6. Галил и Мегиддо 1977, п. 179.

Рекомендации

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

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

• Аллес, Питер; Нешетржил, Ярослав; Poljak, Svatopluck (1991), "Расширяемость, размеры и диаграммы циклических порядков", Журнал SIAM по дискретной математике, 4 (4): 453–471, Дои:10.1137/0404041
• Бандельт, Ханс-Юрген; Чепой, Виктор; Эппштейн, Дэвид (2010), «Комбинаторика и геометрия конечных и бесконечных квадратных графов» (PDF), Журнал SIAM по дискретной математике, 24 (4): 1399–1440, arXiv:0905.4537, Дои:10.1137/090760301, получено 23 мая 2011
• Чайда, Иван; Новак, Витезслав (1985), «О продолжении циклических порядков» (PDF), Časopis Pro Pěstování Matematiky, 110 (2): 116–121, HDL:10338.dmlcz / 108597, получено 30 апреля 2011
• Фишберн, П.С.; Вудалл, Д. Р. (июнь 1999 г.), «Циклические приказы», Заказ, 16 (2): 149–164, Дои:10.1023 / А: 1006381208272
• Хаар, Стефан (2001), «Циклические модели и модели частичного порядка для параллелизма» (PDF), Геометрия и топология в теории параллелизма GETCO '01, стр. 51–62, получено 23 мая 2011
• Иль, Пьер; Руэ, Поль (30 апреля 2008 г.), «Циклические расширения многообразий порядка», Электронные заметки по теоретической информатике, 212: 119–132, CiteSeerX  10.1.1.103.2305, Дои:10.1016 / j.entcs.2008.04.057
• Якубик, Ян (1994), «По расширенным циклическим заказам» (PDF), Чехословацкий математический журнал, 44 (4): 661–675, HDL:10338.dmlcz / 128486, получено 30 апреля 2011
• Меллиес, Поль-Андре (2004), «Критерий топологической корректности некоммутативной логики» (PDF), Томас Эрхард, Жан-Ив Жирар, Поль Руэ и Филип Скотт (ред.), Линейная логика в информатике, стр. 283–323, получено 23 мая 2011
• Новак, Витезслав (1984), «О какой-то минимальной проблеме» (PDF), Archivum Mathematicum, 20 (2): 95–99, HDL:10338.dmlcz / 107191, МИСТЕР  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): 209–228