...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Theoretical computer science >Algorithms for computing lengths of chains in integral partition lattices
【24h】

Algorithms for computing lengths of chains in integral partition lattices

机译：整数分割格中链长的计算算法

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

摘要

Let P{sub}(l,n) denote the partition lattice of l with n parts, ordered by Hardy-Littlewood-Polya majorization. For any two comparable elements x and y of P{sub}(l,n) we denote by M(x, y), m(x, y), f(x, y), and F(x, y), respectively, the sizes of four typical chains between x and y: the longest chain, the shortest chain, the lexicographic chain, and the counter-lexicographic chain. The covers u=(u{sub}1,...,u{sub}n) > v=(v{sub}1,...,v{sub}n) in P{sub}(l,n) are of two types: N-shift (nearby shift) where v{sub}i=u{sub}i -1, v{sub}(i+1)= u{sub}(i+1) + 1 for some i; and D-shift (distant shift) where u{sub}i - 1 =v{sub}i = v{sub}(i+1) = ... = v{sub}j = u{sub}j + 1 for some i and j. An N-shift (a D-shift) is pure if it is not a D-shift (an N-shift). We develop linear algorithms for calculating M(x, y), m(x, y), f(x, y), and F(x, y), using the leftmost pure N-shift first search, the rightmost pure D-shift first search, the leftmost N-shift first search, and the rightmost D-shift first search, respectively. Those algorithms have significant applications in complexity analysis of biological sequences.
机译：令P {sub}（l，n）表示l的n个部分的划分晶格，由Hardy-Littlewood-Polya主化排序。对于P {sub}（l，n）的任意两个可比较元素x和y，我们分别用M（x，y），m（x，y），f（x，y）和F（x，y）表示， x和y之间的四个典型链的大小分别是：最长的链，最短的链，词典序的链和反词典序的链。在P {sub}（l，n中）覆盖u =（u {sub} 1，...，u {sub} n）> v =（v {sub} 1，...，v {sub} n） ）有两种类型：N移位（附近移位），其中v {sub} i = u {sub} i -1，v {sub}（i + 1）= u {sub}（i + 1）+1我一些和D位移（远距离位移），其中u {sub} i-1 = v {sub} i = v {sub}（i + 1）= ... = v {sub} j = u {sub} j + 1对于某些i和j。如果N位移（D位移）不是D位移（N位移），则为纯位移。我们使用最左边的纯N位移优先搜索，最右边的纯D-移位优先搜索，最左侧的N移位优先搜索和最右侧的D移位优先搜索。这些算法在生物序列的复杂性分析中具有重要的应用。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号