• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Information Theory, IEEE Transactions on >A Characterization of the Number of Subsequences Obtained via the Deletion Channel
【24h】

A Characterization of the Number of Subsequences Obtained via the Deletion Channel

机译：通过删除通道获得的子序列数的表征

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Motivated by the study of deletion channels, this paper presents improved bounds on the number of subsequences obtained from a binary string of length under deletions. It is known that the number of subsequences in this setting strongly depends on the number of runs in the string ; where a run is a maximal substring of the same character. Our improved bounds are obtained by a structural analysis of the family of -run strings , an analysis in which we identify the extremal strings with respect to the number of subsequences. Specifically, for every , we present -run strings with the minimum (respectively maximum) number of subsequences under any deletions; we perform an exact analysis of the number of subsequences of these extremal strings; and show that this number can be calculated in polynomial time.
机译：出于对缺失通道研究的推动，本文提出了在缺失条件下从二进制长度的字符串中获得的子序列数量的改进界限。众所周知，此设置中的子序列数很大程度上取决于字符串中的游程数；其中一次运行是相同字符的最大子串。我们通过对运行字符串家族进行结构分析获得了改进的边界，在分析中，我们根据子序列的数量确定了极值字符串。具体来说，对于每一个，我们呈现的运行字符串在任何删除下均具有最小（分别是最大）子序列数；我们对这些极端弦的子序列数进行了精确分析；并表明该数字可以用多项式时间计算。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号