アイテム詳細

要旨

When a system sends messages through a lossy channel, then the language
encoding all sequences of messages can be abstracted by its downward closure,
i.e. the set of all (not necessarily contiguous) subwords. This is useful
because even if the system has infinitely many states, its downward closure is
a regular language. However, if the channel has congestion control based on
priorities assigned to the messages, then we need a finer abstraction: The
downward closure with respect to the priority embedding. As for subword-based
downward closures, one can also show that these priority downward closures are
always regular.
While computing finite automata for the subword-based downward closure is
well understood, nothing is known in the case of priorities. We initiate the
study of this problem and provide algorithms to compute priority downward
closures for regular languages, one-counter languages, and context-free
languages.