• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Article

Multiset rewriting over Fibonacci and Tribonacci numbers

Journal of Computer and System Sciences. 2014. No. 80. P. 1138-1151.

Highlights


Abstract

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).

Keywords

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

• Bridging formal logic and combinatorics. • Formal logic techniques are applied directly to the problems in pure combinatorics. • Church–Rosser property for both rewriting systems and their inverse counterparts. • Bijective proofs for partition identities over k-step Fibonacci numbers. • A new series of partition identities over k-step Fibonacci numbers.