m-Balanced words: A generalization of balanced words
m-Balanced words: A generalization of balanced words
复制标题
m-平衡词：平衡词的概括
DOI：
10.1016/j.tcs.2003.11.021
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
Ryohei Kataoka
中科院分区：
文献类型：
--
作者：
Shinya Sano;N. Miyoshi;Ryohei Kataoka
考虑从一组有限的字母中构造一个无限的序列，或者一个无限的单词，比如每个字母都以“良好的平衡”分布，也就是说，当字母的密度提供时，尽可能均匀地分布。这些词已经应用于许多领域的调度和路由问题。在词的平衡性方面，利用了规则词和平衡词的概念。然而，众所周知，对于给定的字母密度，并不总是存在一个平衡词。在本文中，我们引入了一个叫做m-平衡词的新概念，它给出了对任意字母密度的任何单词的“良好平衡”度量。我们推导了m-平衡词的一些性质，并给出了一组生成平衡词的算法。我们进一步给出了一些应用于简单网络调度问题的例子。
Consider to construct an infinite sequence, or an infinite word, from a finite set of letters such as each letter is distributed with “good balance,” that is, as evenly as possible, when the densities of letters are provided. Such words have been applied to many scheduling and routing problems in various areas. Concerning the balancedness of words, the notions of regularity and balanced words have been exploited. However, it is known that there does not always exist a balanced word for given densities of letters. In this paper, we introduce a new notion called m-balanced words, which gives a measure of “well balancedness” for any words with any densities of letters. We derive some properties of m-balanced words and give a set of algorithms generating well balanced words. We further give a few examples of applications to simple network scheduling problems.