A Limit Theorem for (min, +) Matrix Multiplication

A natural model for the sequential performance of tasks involves a system that can be configured into any one of a possible set S of states where the cost of performing a given task depends on the state. The cost of processing a sequence of tasks (taken from a set T of possible tasks) is the sum of the costs of performing each task plus the cost incurred by moving between states. A quantity of interest is the supremum over all task sequences of the average cost per task to process the sequence. We answer a question of R. Graham by proving that when the underlying costs are integral this supremum is rational.