Gray code orders for q-ary words avoiding a given factor

DOI10.1007/S00236-015-0225-2zbMATH Open1330.68230arXiv1404.0823OpenAlexW2033729551MaRDI QIDQ748433FDOQ748433

D. Kharzeev

Publication date: 29 October 2015

Published in: Acta Informatica (Search for Journal in Brave)

Abstract: Based on BRGC inspired order relations we give Gray codes and a generating algorithm for $q$-ary words avoiding a prescribed factor. These generalize an early 2001 result and a very recent one published by some of the present authors, and can be seen as an alternative to those of Squire published in 1996. Among the involved tools, we make use of generalized BRGC order relations, ultimate periodicity of infinite words, and word matching techniques.

Full work available at URL: https://arxiv.org/abs/1404.0823

Recommendations

• More restrictive Gray codes for necklaces and Lyndon words
• scientific article; zbMATH DE number 5279410
• Gray codes for \(A\)-free strings
• Gray codes for necklaces and Lyndon words of arbitrary base
• scientific article; zbMATH DE number 2154107

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Cites Work

• Title not available (Why is that?)
• Combinatorics of Compositions and Words
• Fast Pattern Matching in Strings
• Title not available (Why is that?)
• Combinatorial Gray Codes
• Restricted compositions and permutations: from old to new Gray codes
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On Generating the N-ary Reflected Gray Codes
• Periods in strings
• Gray codes for reflectable languages
• Gray codes for \(A\)-free strings
• More restricted growth functions: Gray codes and exhaustive generation
• Pattern \(1^{j+1}0^{j}\) avoiding binary words
• A trace partitioned Gray code forq-ary generalized Fibonacci strings
• Title not available (Why is that?)

Cited In (11)

• Title not available (Why is that?)
• Title not available (Why is that?)
• Flip-swap languages in binary reflected Gray code order
• Title not available (Why is that?)
• Gray codes for Fibonacci \(q\)-decreasing words
• A Construction for Variable Dimension Strong Non-Overlapping Matrices
• More restricted growth functions: Gray codes and exhaustive generation
• Strings from linear recurrences and permutations: a gray code
• Strings from linear recurrences: a Gray code
• Title not available (Why is that?)
• Combinatorial families that are exponentially far from being listable in Gray code sequence

This page was built for publication: Gray code orders for \(q\)-ary words avoiding a given factor

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q748433)