@inproceedings{74a5b3c2457e4d37aaf8a367ffab56ef,
title = "Greedy Gray Codes for Dyck Words and Ballot Sequences",
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].",
keywords = "Dyck word, balanced parentheses, ballot sequence, greedy algorithm, homogeneous Gray code, lattice path",
author = "Vincent Vajnovszki and Dennis Wong",
note = "Publisher Copyright: {\textcopyright} The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.; 29th International Computing and Combinatorics Conference, COCOON 2023 ; Conference date: 15-12-2023 Through 17-12-2023",
year = "2024",
doi = "10.1007/978-3-031-49193-1_3",
language = "English",
isbn = "9783031491924",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Science and Business Media Deutschland GmbH",
pages = "29--40",
editor = "Weili Wu and Guangmo Tong",
booktitle = "Computing and Combinatorics - 29th International Conference, COCOON 2023, Proceedings",
address = "Germany",
}