Recursive and iterative approaches to generate rotation Gray codes for stamp foldings and semi-meanders

Research output: Contribution to journalArticlepeer-review

Abstract

We first present a simple recursive algorithm that generates cyclic rotation Gray codes for stamp foldings and semi-meanders, where consecutive strings differ by a stamp rotation. These are the first known Gray codes for stamp foldings and semi-meanders, and we thus solve an open problem posted by Sawada and Li (2012) [17]. We then introduce an iterative algorithm that generates the same rotation Gray codes for stamp foldings and semi-meanders. Both the recursive and iterative algorithms generate stamp foldings and semi-meanders in constant amortized time and O(n)-amortized time per string respectively, using a linear amount of memory.

Original languageEnglish
Article number115053
JournalTheoretical Computer Science
Volume1031
DOIs
Publication statusPublished - 21 Mar 2025

Keywords

  • Binary reflected Gray code
  • CAT algorithm
  • Gray code
  • Meanders
  • Reflectable language
  • Semi-meanders
  • Stamp foldings

Fingerprint

Dive into the research topics of 'Recursive and iterative approaches to generate rotation Gray codes for stamp foldings and semi-meanders'. Together they form a unique fingerprint.

Cite this