Антиматроїд

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

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

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

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

Визначення

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

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

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

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

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

Примітки

• Adaricheva, K. V.; Gorbunov, V. A.; Tumanov, V. I. (2003), Join-semidistributive lattices and convex geometries, Advances in Mathematics, 173 (1): 1—49, doi:10.1016/S0001-8708(02)00011-7.
• Armstrong, Drew (2009), The sorting order on a Coxeter group, Journal of Combinatorial Theory, Series A, 116 (8): 1285—1305, arXiv:0712.1047, doi:10.1016/j.jcta.2009.03.009, MR 2568800, S2CID 15474840.
• Birkhoff, Garrett; Bennett, M. K. (1985), The convexity lattice of a poset, Order, 2 (3): 223—242, doi:10.1007/BF00333128, S2CID 118907732
• Björner, Anders; Lovász, László; Shor, Peter W. (1991), Chip-firing games on graphs, European Journal of Combinatorics, 12 (4): 283—291, doi:10.1016/S0195-6698(13)80111-4, MR 1120415
• Björner, Anders; Ziegler, Günter M. (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 0-521-38165-7, 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.; Ruskey, F.; 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
• Dilworth, Robert P. (1940), Lattices with unique irreducible decompositions, Annals of Mathematics, 41 (4): 771—777, doi:10.2307/1968857, JSTOR 1968857.
• Doignon, Jean-Paul; Falmagne, Jean-Claude (1999), Knowledge Spaces, Springer-Verlag, ISBN 3-540-64501-2.
• 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.; Saks, Michael E. (1988), Combinatorial representation and convex dimension of convex geometries, Order, 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 Falmagne, Jean-Claude; 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 978-3-642-35328-4.
• 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 978-0-471-58041-6.
• Gordon, Gary (1997), A β invariant for greedoids and antimatroids, Electronic Journal of Combinatorics, 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, Computational Geometry, 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, Electronic Journal of Combinatorics, 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
• Korte, Bernhard; Lovász, László; Schrader, Rainer (1991), Greedoids, Springer-Verlag, с. 19—43, ISBN 3-540-18190-3.
• 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, Order, 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).