The Setting
In the inventory encoding of random planar maps, finite words of burgers and orders are reduced sequentially as each order consumes the freshest eligible burger. Given a one-sided or bi-infinite sequence of such word pieces, which sequences or boundary locations ensure that no finite stretch leaves pending orders on the right or surviving burgers on the left?
Inventory Words and Reduction
Let be the two-element set of burger types. The inventory order set consists of two fixed orders, one for each burger type in , and one flexible order.✦ The burger-order alphabet is the disjoint union of the set of burger types and the inventory order set .✦ For any set , write for the set of finite words over with empty word and concatenation written by juxtaposition, and let denote the reversal of .
An inventory stack evaluation state consists of a word of pending orders and a word of burger types stored freshest-first.✦ Given the single-step transition , in which an incoming burger is added to the burger stack and an order consumes the freshest eligible burger or joins the pending orders, the evaluation of a word on a state is defined recursively on by (1)✦ for all and . The word reduction of a word is the evaluation state obtained via word evaluation (1) from empty pending orders and an empty burger stack, (2)✦
For a sequence of inventory words, the concatenated piece prefix of over its first pieces is the word defined recursively by (3)✦ Given a bi-infinite sequence of inventory words indexed by the integers , an integer , and , the concatenated interval word starting at and spanning pieces is the word obtained from the concatenated piece prefix (3) of a shifted sequence by (4)✦
The Definition
Definition 1. A one-sided sequence of inventory words has a left cut if its concatenated piece prefixes (3) under word reduction (2) satisfy (5)✦ For a sequence of inventory words, has a right cut when the reversals of its concatenated piece prefixes satisfy (6)✦ Given a bi-infinite sequence of inventory words and an integer , the sequence has a left cut at if its concatenated interval words (4) satisfy (7)✦ For a bi-infinite sequence of inventory words and an integer , the sequence has a right cut at when its concatenated interval words starting at and spanning pieces satisfy (8)✦
What Is Checked
The one-sided cut definitions (5) and (6) are stated over sequences via word reduction (2) of concatenated piece prefixes (3) and their reversals, and the two-sided definitions (7) and (8) are stated over bi-infinite sequences and integers via word reduction of concatenated interval words (4).