Multiset rewriting over Fibonacci and Tribonacci numbers

作者：Kanovich Max^*

来源：Journal of Computer and System Sciences, 2014, 80(6): 1138-1151.

DOI：10.1016/j.jcss.2014.04.006

• Multiset rewriting
• Church-Rosser property
• Confluence
• Termination
• Integer partitions
• Partition identities
• Fibonacci numbers
• Tribonacci numbers
• kappa-Step Fibonacci numbers

We show how techniques from the formal logic, can be applied directly to the problems studied completely independently in the world of combinatorics, the theory of integer partitions. We characterize equinumerous partition ideals in terms of the minimal elements generating the complementary order filters. Here we apply a general rewriting methodology to the case of filters having overlapping minimal elements. In addition to a 'bijective proof' for Zeckendorf-like theorems - that every positive integer is uniquely representable within the Fibonacci, Tribonacci and k-Bonacci numeration systems, we establish 'bijective proofs' for a new series of partition identities related to Fibonacci, Tribonacci and k-step Fibonacci numbers. The main result is proved with the help of a multiset rewriting system such that the system itself and the system consisting of its reverse rewriting rules, both have the Church-Rosser property, which provides an explicit bijection between partitions of two different types (represented by the two normal forms).

• 出版日期2014-9