• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Computer Science Logic >Bijections between Partitions by Two-Directional Rewriting Techniques
【24h】

Bijections between Partitions by Two-Directional Rewriting Techniques

机译：通过双向重写技术在分区之间的双射

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

One basic activity in combinatorics is to establish combinatorial identities by so-called 'bijective proofs,' which consist in constructing explicit bijections between two types of the combinatorial objects under consideration. We show how such bijective proofs can be established, and how the bijections are computed by means of multiset rewriting, for a variety of combinatorial problems involving partitions. In particular, we fully characterizes all equinumerous partition ideals with 'disjointly supported' complements. As a corollary, a new proof, the 'bijective' one, is given for all equinumerous classes of the partition ideals of order 1 from the classical book "The Theory of Partitions" by G.Andrews. Establishing the required bijections involves novel two-directional reductions in the sense that forward and backward application of rewrite rules head for two different normal forms (representing the two combinatorial types). It is well-known that non-overlapping multiset rules are confluent. As for termination, it generally fails even for multiset rewriting systems that satisfy certain natural invariant balance conditions. The main technical development of the paper, which is important for establishing that the mapping yielding the combinatorial bijection is functional, is that the 'restricted' two-directional strong normalization holds for the multiset rewriting systems in question.
机译：组合学的一项基本活动是通过所谓的“双射证明”建立组合身份，这包括在所考虑的两种类型的组合对象之间构造显式双射。对于各种涉及分区的组合问题，我们将说明如何建立这样的双射证明，以及如何通过多集重写来计算双射。特别是，我们用“不相交支持”的补语来充分描述所有等价的分区理想。作为推论，从安德鲁斯（G.Andrews）的经典著作《划分理论》中为所有等价的1级分配理想的所有类给出了一个新的证明，即“双射性”证明。建立所需的双射涉及新颖的双向缩减，即向前和向后应用重写规则将指向两种不同的范式（代表两种组合类型）。众所周知，不重叠的多集规则是融合的。至于终止，即使对于满足某些自然不变平衡条件的多集重写系统，它通常也会失败。本文的主要技术发展对确定产生组合双射的映射是有效的功能非常重要，这是所讨论的多集重写系统的“受限”双向强归一化成立。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号