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

DOI10.1007/S00236-015-0225-2MaRDI QIDQ748433zbMATH OpenOpenAlexFDO

Authors D. Kharzeev

Publication date 29 October 2015

Published in Acta Informatica (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Combinatorics on words (68R15)

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.

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

Cites work

• scientific article; zbMATH DE number 1665457 (Why is no real title available?)
• scientific article; zbMATH DE number 2040940 (Why is no real title available?)
• scientific article; zbMATH DE number 1506516 (Why is no real title available?)
• scientific article; zbMATH DE number 1792682 (Why is no real title available?)
• scientific article; zbMATH DE number 2183071 (Why is no real title available?)
• A construction for a class of binary words avoiding \(1^j0^i\)
• A trace partitioned Gray code forq-ary generalized Fibonacci strings
• Combinatorial Gray Codes
• Combinatorics of Compositions and Words
• Fast Pattern Matching in Strings
• Gray codes for \(A\)-free strings
• Gray codes for reflectable languages
• More restricted growth functions: Gray codes and exhaustive generation
• On Generating the N-ary Reflected Gray Codes
• Pattern \(1^{j+1}0^{j}\) avoiding binary words
• Periods in strings
• Restricted compositions and permutations: from old to new Gray codes

Cited in

(11)

• Restricting Dyck paths and 312-avoiding permutations
• Gray codes for Fibonacci \(q\)-decreasing words
• Strings from linear recurrences and permutations: a gray code
• A Construction for Variable Dimension Strong Non-Overlapping Matrices
• scientific article; zbMATH DE number 7593859 (Why is no real title available?)
• On the \(q\)-analog of the revolving door algorithm
• Flip-swap languages in binary reflected Gray code order
• scientific article; zbMATH DE number 5279410 (Why is no real title available?)
• Combinatorial families that are exponentially far from being listable in Gray code sequence
• Strings from linear recurrences: a Gray code
• More restricted growth functions: Gray codes and exhaustive generation

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)