A Geometric Characterization of Poly-antimatroids |
| |
Institution: | 1. Department of Computer Science, University of Ioannina, P.O. Box 1186, 45110 Ioannina, Greece;2. Department of Computer Engineering and Informatics, University of Patras, 26500 Patras, Greece;1. Department of Computing, Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong;2. Department of Computer Science, University of Texas at Dallas, Richardson, TX 75083, USA |
| |
Abstract: | The concept of "antimatroid with repetition" was coined by Bjorner, Lovasz and Shor in 1991 as an extension of the notion of antimatroid in the framework of non-simple languages Björner A., L. Lovász, and P. R. Shor, Chip-firing games on graphs, European Journal of Combinatorics 12 (1991), 283–291]. There are some equivalent ways to define antimatroids. They may be separated into two categories: antimatroids defined as set systems and antimatroids defined as languages. For poly-antimatroids we use the set system approach. In this research we concentrate on interrelations between geometric, algorithmic, and lattice properties of poly-antimatroids. Much to our surprise it turned out that even the two-dimensional case is not trivial. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|