Greedy Gray Codes for Dyck Words and Ballot Sequences

Vincent Vajnovszki, Dennis Wong

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

Abstract

We present a simple greedy algorithm for generating Gray codes for Dyck words and fixed-weight Dyck prefixes. Successive strings in our listings differ from each other by a transposition, that is, two bit changes. Our Gray codes are both homogeneous and suffix partitioned. Furthermore, we use our greedy algorithm to produce the first known homogeneous 2-Gray code for ballot sequences, which are Dyck prefixes of all weights. Our work extends a previous result on combinations by Williams [Conference proceedings: Workshop on Algorithms and Data Structures (WADS), LNTCS 8037:525-536, 2013].

Original languageEnglish
Title of host publicationComputing and Combinatorics - 29th International Conference, COCOON 2023, Proceedings
EditorsWeili Wu, Guangmo Tong
PublisherSpringer Science and Business Media Deutschland GmbH
Pages29-40
Number of pages12
ISBN (Print)9783031491924
DOIs
Publication statusPublished - 2024
Event29th International Computing and Combinatorics Conference, COCOON 2023 - Hawaii, United States
Duration: 15 Dec 202317 Dec 2023

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume14423 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference29th International Computing and Combinatorics Conference, COCOON 2023
Country/TerritoryUnited States
CityHawaii
Period15/12/2317/12/23

Keywords

  • Dyck word
  • balanced parentheses
  • ballot sequence
  • greedy algorithm
  • homogeneous Gray code
  • lattice path

Fingerprint

Dive into the research topics of 'Greedy Gray Codes for Dyck Words and Ballot Sequences'. Together they form a unique fingerprint.

Cite this