A generalized semi-Markov scheme models the structure of a discrete event system, such as a network of queues. By studying combinatorial and geometric representations of schemes the authors find conditions for second-order properties-convexity/concavity, sub/supermodularity-of their event epochs and event counting processes. A scheme generates a language of feasible strings of events. The authors show that monotonicity of the event epochs is equivalent to this language forming an antimatroid with repetition. This connection gives rise to a rich combinatorial structure, and serves as a starting point for other properties. For example, by strengthening the antimatroid condition the authors give several equivalent characterizations of the convexity of event epochs within a scheme. All of these correspond, in slightly different ways, to making a certain score space a lattice, to closing an ordinary antimatroid under intersections. The authors also establish second-order properties across schemes tied together through a synchronization mechanism. A geometric view based on the score space facilitates verification of these properties in certain queueing systems.
