
Task Systems

A "task system" is defined to be a triple S = (Q,T,cost) where Q is a set of
states, T is a set of tasks, and cost(q,t,r) is defined to be the cost
of serving task t while moving from state q to state r.  We allow a value
of the cost function to be infinite, indicating that that movement is
not allowed.  One state is designated to be the start state.  We say that
a task system is "finite" if both Q and T are finite and if the value of
cost is always an integer or infinite.  A finite task system is thus an NFA
with input alphabet T, where each transition has an integral cost.  We
say that S is "complete" if cost(q,t,r) is finite for all q, r, and t.
We say that S is "non-trapping" if, for any q in Q and any t in T, there
is some r in Q for which cost(q,t,r) is finite.  We say that S is a "metrical
task system" if Q is a metric space with integral distances, and if there is
a function f(t,r) such that cost(q,t,r) = |q,r| + f(t,r) for all q, t, and r.

A "task sequence" (also called "request sequence") is a string over T.
A "service" of a given task sequence is defined to be a valid computation of
the NFA with that input string.  The cost of a service is defined to be the
sum of the costs of the transitions.  For a given task sequence, the optimal
cost is defined to be the minimum cost of any service of that task sequence.

Let S = (Q,T,cost) be a finite task system.  We say that O = (W,T,optcost) is
an "optimizer" for S if:
(a) O is a finite task system.
(b) O is deterministic, that is, for any w in W and any t in T, there is
at most one x in W such that optcost(w,t,x) is finite.

(c) Given any task sequence sigma, there is at most one valid computation of
sigma in O which uses no edges of infinite cost.  The cost of this computation
is equal to the optimal cost of sigma in S.

Theorem 1:  If a finite task system has an optimizer, it has a unique
minimal optimizer.

Theorem 2:  Every finite metrical task system has an optimizer.

Theorem 3:  Every complete finite task system has an optimizer.

Conjecture:  Every non-trapping finite task system has an optimizer.
