The Setting
Consider a deterministic inventory system with two burger types, two fixed orders (one for each type), and one flexible order. Burgers sit on a stack ordered freshest-first, and each order consumes the freshest eligible burger. Given an initial burger stack and an equal-length sequence of orders, when does evaluating the orders clear both the burger stack and the list of pending orders?
Inventory Definitions
The set of burger types is a two-element set. The set of inventory orders consists of fixed orders for , eligible for burgers of type , and the flexible order , eligible for burgers of either type.✦ The burger-order alphabet is the finite set consisting of burger tokens for and order tokens for .✦
The set of burger stacks is the set of finite lists over stored freshest-first. The set of inventory stack evaluation states is the set of pairs consisting of a finite list of pending orders in and a burger stack .✦
For an order and a burger stack , the pop operation is the element of that removes the freshest eligible burger from , returning the failure value when none is present, defined by (1): (1)✦ with for .
Given a single-step transition for and , the evaluation of a word over from state is defined recursively by (2): (2)✦
The order evaluation on supply of a finite order list over against a burger stack is the evaluation state in defined by (3), where is the word of order tokens: (3)✦
For a finite list of length and an integer , the bottom suffix of is the terminal suffix of length given by (4): (4)✦
A stack and an order list over satisfy the supply condition when (5) holds, where denotes the number of occurrences of an entry in a finite list : (5)✦
The Claim
Whenever a burger stack and a type satisfy , there exists a stack fulfilling (6): (6)✦
If a stack and a nonempty order list with satisfy (5), then there exists a stack satisfying (7): (7)✦
Theorem 1. Suppose a burger stack and an order list over satisfy the supply condition (5). Then the order evaluation on supply satisfies (8): (8)✦
In the paper, the result reads: if a burger stack and an order word both have length and, for every and each burger type , the number of fixed type- orders among the terminal orders of is at most the number of type- burgers among the original bottom burgers of , then the greedy inventory rule matches all orders and leaves no burgers.
What Is Checked
The matching theorem (8), together with (6) and (7), is stated over inventory orders in , burger-order alphabet letters in , evaluation states in with freshest-first burger stacks in , word evaluation, order evaluation on supply, the pop operation, and the supply condition (5) built from bottom suffixes.