We present a CAT (constant amortized time) algorithm for generating those partitions of that are in the (), a generalization of the (). More precisely, for any fixed integer , we show that the negative lexicographic ordering naturally identifies a tree structure on the lattice (): this lets us design an algorithm which generates all the ice piles of () in amortized time (1) and in space ().
We present a CAT (constant amortized time) algorithm for generating those partitions of that are in the (), a generalization of the (). More precisely, for any fixed integer , we show that the negative lexicographic ordering naturally identifies a tree structure on the lattice (): this lets us design an algorithm which generates all the ice piles of () in amortized time (1) and in space ().
Given a finite alphabet and a language , the centralizer of is defined as the maximal language commuting with it. We prove that if the primitive root of the smallest word of (with respect to a lexicographic order) is prefix distinguishable in then the centralizer of is as simple as possible, that is, the submonoid . This lets us obtain a simple proof of a known result concerning the centralizer of nonperiodic three-word languages.
Page 1