Back to Search
Start Over
Loopless algorithms to generate maximum length gray cycles wrt. k-character substitutions.
- Source :
-
Theoretical Computer Science . Oct2023, Vol. 977, pN.PAG-N.PAG. 1p. - Publication Year :
- 2023
-
Abstract
- Given a binary word relation τ onto A ⁎ and a finite language X ⊆ A ⁎ , a τ -Gray cycle over X consists in a permutation (w [ i ]) 0 ≤ i ≤ | X | − 1 of X such that each word w [ i ] is an image under τ of the previous word w [ i − 1 ]. We define the complexity measure λ A , τ (n) , equal to the largest cardinality of a language X having words of length at most n , and st. some τ -Gray cycle over X exists. The present paper is concerned with τ = σ k , the so-called k -character substitution, st. (u , v) ∈ σ k holds if, and only if, the Hamming distance of u and v is k. We present loopless (resp., constant amortized time) algorithms for computing specific maximum length σ k -Gray cycles. [ABSTRACT FROM AUTHOR]
- Subjects :
- *HAMMING distance
*ALGORITHMS
Subjects
Details
- Language :
- English
- ISSN :
- 03043975
- Volume :
- 977
- Database :
- Academic Search Index
- Journal :
- Theoretical Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 172974792
- Full Text :
- https://doi.org/10.1016/j.tcs.2023.114175