Affordable Access

Publisher Website

Cool-lex order andk-ary Catalan structures

Authors
Journal
Journal of Discrete Algorithms
1570-8667
Publisher
Elsevier
Volume
16
Identifiers
DOI: 10.1016/j.jda.2012.04.015
Keywords
  • Catalan Structures
  • Cool-Lex Order
  • Bubble Langauges
  • Loopless Algorithms
  • Ranking
  • K-Ary Dyck Words
  • K-Ary Trees
Disciplines
  • Computer Science
  • Linguistics
  • Mathematics

Abstract

Abstract For any given k, the sequence of k-ary Catalan numbers, Ct,k=1kt+1(ktt), enumerates a number of combinatorial objects, including k-ary Dyck words of length n=kt and k-ary trees with t internal nodes. We show that these objects can be efficiently ordered using the same variation of lexicographic order known as cool-lex order. In particular, we provide loopless algorithms that generate each successive object in O(1) time. The algorithms are also efficient in terms of memory, with the k-ary Dyck word algorithm using O(1) additional index variables, and the k-ary tree algorithm using O(t) additional pointers and index variables. We also show how to efficiently rank and unrank k-ary Dyck words in cool-lex order using O(kt) arithmetic operations, subject to an initial precomputation. Our results are based on the cool-lex successor rule for sets of binary strings that are bubble languages. However, we must complement and reverse 1/k-ary Dyck words to obtain the stated efficiency.

There are no comments yet on this publication. Be the first to share your thoughts.

Statistics

Seen <100 times
0 Comments

More articles like this

Binary bubble languages and cool-lex order

on Journal of Combinatorial Theor... Jan 01, 2012

Reduced decompositions of permutations in terms of...

on Discrete Mathematics Jan 01, 1999

Sums andk-sums in abelian groups of orderk

on Journal of Number Theory Jan 01, 2006

Analysis of internally cooled structures using a h...

on Computers & Structures Jan 01, 2004
More articles like this..