A Motzkin filter in the Tamari lattice

The Tamari lattice of order n can be defined on the set T n of binary trees endowed with the partial order relation induced by the well-known rotation transformation. In this paper, we restrict our attention to the subset M n of Motzkin trees. This set appears as a filter of the Tamari lattice. We prove that its diameter is 2 n - 5 and that its radius is n - 2 . Enumeration results are given for join and meet irreducible elements, minimal elements and coverings. The set M n endowed with an order relation based on a restricted rotation is then isomorphic to a ranked join-semilattice recently defined in Baril and Pallo (2014). As a consequence, we deduce an upper bound for the rotation distan…

A distance metric on binary trees using lattice-theoretic measures

A so called height function which is a strictly antitone supervaluation is defined on binary trees. Via lattice-theoretic results and using the height function, we can define a distance metric on binary trees of size n which can be computed in expected time O(n 3/2 )

On the listing and random generation of hybrid binary trees

We consider in this paper binary trees whose internal nodes are either associative or non-associative. Hybrid binary trees are equivalence classes with respect to the associative property. We count, list and generate randomly hybrid binary trees using Fibonacci numbers.

Motzkin subposets and Motzkin geodesics in Tamari lattices

The Tamari lattice of order n can be defined by the set D n of Dyck words endowed with the partial order relation induced by the well-known rotation transformation. In this paper, we study this rotation on the restricted set of Motzkin words. An upper semimodular join semilattice is obtained and a shortest path metric can be defined. We compute the corresponding distance between two Motzkin words in this structure. This distance can also be interpreted as the length of a geodesic between these Motzkin words in a Tamari lattice. So, a new upper bound is obtained for the classical rotation distance between two Motzkin words in a Tamari lattice. For some specific pairs of Motzkin words, this b…

An efficient upper bound of the rotation distance of binary trees

A polynomial time algorithm is developed for computing an upper bound for the rotation distance of binary trees and equivalently for the diagonal-flip distance of convex polygons triangulations. Ordinal tools are used.

Parallel Algorithms for Listing Well-Formed Parentheses Strings

We present two cost-optimal parallel algorithms generating the set of all well-formed parentheses strings of length 2n with constant delay for each generated string. In our first algorithm we generate in lexicographic order well-formed parentheses strings represented by bitstrings, and in the second one we use the representation by weight sequences. In both cases the computational model is based on an architecture CREW PRAM, where each processor performs the same algorithm simultaneously on a different set of data. Different processors can access the shared memory at the same time to read different data in the same or different memory locations, but no two processors are allowed to write i…

Efficient lower and upper bounds of the diagonal-flip distance between triangulations

There remains today an open problem whether the rotation distance between binary trees or equivalently the diagonal-flip distance between triangulations can be computed in polynomial time. We present an efficient algorithm for computing lower and upper bounds of this distance between a pair of triangulations.

The pruning-grafting lattice of binary trees

AbstractWe introduce a new lattice structure Bn on binary trees of size n. We exhibit efficient algorithms for computing meet and join of two binary trees and give several properties of this lattice. More precisely, we prove that the length of a longest (resp. shortest) path between 0 and 1 in Bn equals to the Eulerian numbers 2n−(n+1) (resp. (n−1)2) and that the number of coverings is (2nn−1). Finally, we exhibit a matching in a constructive way. Then we propose some open problems about this new structure.

The Phagocyte Lattice of Dyck Words

We introduce a new lattice structure on Dyck words. We exhibit efficient algorithms to compute meets and joins of Dyck words.

The Rotation χ-Lattice of Ternary Trees

This paper generalizes to k-ary trees the well-known rotation transformation on binary trees. For brevity, only the ternary case is developped. The rotation on ternary trees is characterized using some codings of trees. Although the corresponding poset is not a lattice, we show that it is a χ-lattice in the sense of Leutola–Nieminen. Efficient algorithms are exhibited to compute meets and joins choosen in a particular way.

Right-arm rotation distance between binary trees

We consider a transformation on binary trees, named right-arm rotation, which is a special instance of the well-known rotation transformation. Only rotations at nodes of the right arm of the trees are allowed. Using ordinal tools, we give an efficient algorithm for computing the right-arm rotation distance between two binary trees, i.e., the minimum number of rightarm rotations necessary to transform one tree into the other.

Short notes: Some Properties of the Rotation Lattice of Binary Trees

Root-restricted Kleenean rotations

We generalize the Kleene theorem to the case where nonassociative products are used. For this purpose, we apply rotations restricted to the root of binary trees.

Weak associativity and restricted rotation

A restricted rotation induced by a weak associative law is introduced. The corresponding equivalence relation is identical to the Glivenko congruence on Tamari lattices, i.e. lattices of binary trees endowed by the well-known rotation operation.

A decidable word problem without equivalent canonical term rewriting system

We present a weak associative single-axiom system having the following property: the word problem is decidable with an efficient algorithm even though there does not exist any finite equivalent canonical term rewriting system.

Coding Binary Trees by Words over an Alphabet with Four Letters

Abstract We propose a new encoding scheme to represent binary trees with n leaves by words of length n over an alphabet with four letters. We give a characterization of these codewords.

Matchings in three Catalan lattices

In this note we consider a series of lattices that are enumerated by the well-known Catalan numbers. For each of these lattices, we exhibit a matching in a constructive way.