Антиматроїд

Антиматроїд — це формальна система, яка описує процеси, в яких множина будується шляхом включення елементів по одному, і в якій елемент, будучи доступним для включення, залишається доступним до тих пір, поки він не буде включений. Антиматроїди зазвичай аксіоматизуються двома еквівалентними способами: або як сімейство множин, що моделюють можливі стани такого процесу, або як формальна мова, що моделює різні послідовності, у які можуть бути включені елементи. Американський вчений ^[en] був першим, хто вивчав антиматроїди, використовуючи ще одну аксіоматизацію, засновану на теорії ґратки.

Три види антиматроїду: впорядкування включення в його сімейство здійсненних множин, формальна мова і відповідний шлях.

Аксіоми, які визначають антиматроїди як сімейство множин, дуже схожі на аксіоми матроїдів, але, тоді як матроїди визначаються аксіомою обміну, антиматроїди визначаються замість того аксіомою протиобміну, від якої походить їх назва. Антиматроїди можна розглядати як особливий випадок ^[en] та ^[en]. Антиматроїди еквівалентні завдяки доповненню, опуклій геометрії, комбінаторній абстракції опуклих множин в геометрії.

Антиматроїди були застосовані для моделювання обмежень пріоритету у теорії розкладів, послідовностей подій у симуляціях, а також у плануванні завдань для штучного інтелекту.

Визначення

Антиматроїд можна визначити як скінченне сімейство ${\displaystyle {\mathcal {F}}}$ скінченних множин з наступними двома властивостями:

• Об'єднання будь-яких двох допустимих множин також є допустимою множиною. Тобто, ${\displaystyle {\mathcal {F}}}$ є замкненим відносно об'єднань.
• Якщо ${\displaystyle S}$ є непорожньою допустимою множиною, то ${\displaystyle S}$ містить елемент ${\displaystyle x}$, для якого ${\displaystyle S\setminus \{x\}}$ (множина, утворена шляхом видалення ${\displaystyle x}$ з ${\displaystyle S}$) також допустима. Тобто, ${\displaystyle {\mathcal {F}}}$ є ^[en].

Антиматроїди також мають еквівалентне визначення як формальна мова, тобто як набір рядків, визначених з кінцевого алфавіту символів. Рядок, що належить цьому набору, називається словом мови. Мова ${\displaystyle {\mathcal {L}}}$, яка визначає антиматроїд, повинна задовольняти наступні властивості:

• Кожен символ алфавіту зустрічається принаймні в одному слові ${\displaystyle {\mathcal {L}}}$.
• Кожне слово з ${\displaystyle {\mathcal {L}}}$ містить щонайбільше одне повторення кожного символу. Мова з такою властивістю називається нормальною.
• Кожен (префікс) слова в ${\displaystyle {\mathcal {L}}}$ також знаходиться в ${\displaystyle {\mathcal {L}}}$. Мова, що володіє цією властивістю, називається спадковою.
• Якщо ${\displaystyle S}$ і ${\displaystyle T}$ є словами у мові ${\displaystyle {\mathcal {L}}}$, і слово ${\displaystyle S}$ містить принаймні один символ, якого немає в ${\displaystyle T}$, то існує такий символ ${\displaystyle x}$ в ${\displaystyle S}$, що конкатенація ${\displaystyle T}$ та ${\displaystyle x}$ є іншим словом у мові ${\displaystyle {\mathcal {L}}}$.

Еквівалентність цих двох форм визначення можна показати наступним чином: якщо ${\displaystyle {\mathcal {L}}}$ є антиматроїдом, визначеним як формальна мова, то множини символів у словах ${\displaystyle {\mathcal {L}}}$ утворюють доступну систему об'єднаних множин. Це визначається властивістю наслідування для рядків, а умову об'єднаності можна довести за допомогою властивості конкатенації рядків. У інший бік, з доступної об'єднано-замкненої системи множин ${\displaystyle {\mathcal {F}}}$, мова нормальних рядків, у яких префікси містять множини символів, що належать ${\displaystyle {\mathcal {F}}}$, відповідає вимогам формальної мови, яка є антиматроїдом. Ці дві трансформації є оберненими одна до одної: перетворення формальної мови в систему множин і назад, або навпаки, породжує ту саму систему. Отже, ці два визначення призводять до математично еквівалентних класів об'єктів.

Примітки

1. Див. Korte, Lovász та Schrader, (1991) для повного огляду теорії антиматроїдів з багатьма додатковими посиланнями.

Примітки

• Adaricheva, K. V.; Gorbunov, V. A.; Tumanov, V. I. (2003), Join-semidistributive lattices and convex geometries, , 173 (1): 1—49, doi:10.1016/S0001-8708(02)00011-7.
• Armstrong, Drew (2009), The sorting order on a Coxeter group, , Series A, 116 (8): 1285—1305, arXiv:0712.1047, doi:10.1016/j.jcta.2009.03.009, MR 2568800, S2CID 15474840.
• ; Bennett, M. K. (1985), The convexity lattice of a poset, , 2 (3): 223—242, doi:10.1007/BF00333128, S2CID 118907732
• ; Lovász, László; (1991), Chip-firing games on graphs, , 12 (4): 283—291, doi:10.1016/S0195-6698(13)80111-4, MR 1120415
• ; (1992), Introduction to greedoids, у White, Neil (ред.), Matroid Applications, Encyclopedia of Mathematics and its Applications, т. 40, Cambridge: Cambridge University Press, с. 284–357, doi:10.1017/CBO9780511662041.009, ISBN , MR 1165537
• Boyd, E. Andrew; Faigle, Ulrich (1990), An algorithmic characterization of antimatroids, Discrete Applied Mathematics, 28 (3): 197—205, doi:10.1016/0166-218X(90)90002-T, hdl:1911/101636.
• Chandran, L. S.; Ibarra, L.; ; Sawada, J. (2003), Generating and characterizing the perfect elimination orderings of a chordal graph (PDF), Theoretical Computer Science, 307 (2): 303—317, doi:10.1016/S0304-3975(03)00221-4
• (1940), Lattices with unique irreducible decompositions, Annals of Mathematics, 41 (4): 771—777, doi:10.2307/1968857, JSTOR 1968857.
• Doignon, Jean-Paul; (1999), Knowledge Spaces, Springer-Verlag, ISBN .
• Edelman, Paul H. (1980), Meet-distributive lattices and the anti-exchange closure, Algebra Universalis, 10 (1): 290—299, doi:10.1007/BF02482912, S2CID 120403229.
• Edelman, Paul H.; (1988), Combinatorial representation and convex dimension of convex geometries, , 5 (1): 23—32, doi:10.1007/BF00143895, S2CID 119826035.
• Eppstein, David (2008), Learning sequences, arXiv:0803.4030. Partially adapted as Chapters 13 and 14 of ; Albert, Dietrich; Doble, Chris; Eppstein, David; Hu, Xiangen, ред. (2013), Knowledge Spaces: Applications in Education, Springer-Verlag, doi:10.1007/978-3-642-35329-1, ISBN .
• Farber, Martin; Jamison, Robert E. (1986), Convexity in graphs and hypergraphs, SIAM Journal on Algebraic and Discrete Methods, 7 (3): 433—444, doi:10.1137/0607049, hdl:10338.dmlcz/127659, MR 0844046.
• Glasserman, Paul; Yao, David D. (1994), Monotone Structure in Discrete Event Systems, Wiley Series in Probability and Statistics, Wiley Interscience, ISBN .
• Gordon, Gary (1997), A β invariant for greedoids and antimatroids, , 4 (1): Research Paper 13, doi:10.37236/1298, MR 1445628.
• Jamison, Robert (1980), Copoints in antimatroids, Proceedings of the Eleventh Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1980), Vol. II, Congressus Numerantium, т. 29, с. 535—544, MR 0608454.
• Kashiwabara, Kenji; Nakamura, Masataka; Okamoto, Yoshio (2005), The affine representation theorem for abstract convex geometries, , 30 (2): 129—144, CiteSeerX 10.1.1.14.4965, doi:10.1016/j.comgeo.2004.05.001, MR 2107032.
• Kempner, Yulia; Levit, Vadim E. (2003), Correspondence between two antimatroid algorithmic characterizations, , 10: Research Paper 44, arXiv:math/0307013, Bibcode:2003math......7013K, doi:10.37236/1737, MR 2014531, S2CID 11015967
• Knauer, Kolja (2009), Chip-firing, antimatroids, and polyhedra, European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2009), Electronic Notes in Discrete Mathematics, т. 34, с. 9—13, doi:10.1016/j.endm.2009.07.002, MR 2591410
• ; Lovász, László; Schrader, Rainer (1991), Greedoids, Springer-Verlag, с. 19—43, ISBN .
• Merchant, Nazarré; Riggle, Jason (2016), OT grammars, beyond partial orders: ERC sets and antimatroids, Natural Language & Linguistic Theory, 34: 241—269, doi:10.1007/s11049-015-9297-5, S2CID 170567540.
• Monjardet, Bernard (1985), A use for frequently rediscovering a concept, , 1 (4): 415—417, doi:10.1007/BF00582748, S2CID 119378521.
• Parmar, Aarati (2003), Some Mathematical Structures Underlying Efficient Planning, AAAI Spring Symposium on Logical Formalization of Commonsense Reasoning (PDF).