Abstract
Some length-preserving operations on strings only permute the symbol positions in strings; such an operation $X$ gives rise to a family $\{X_n\}_{n\geq 2}$ of similar permutations. We investigate the structure and the order of the cyclic group generated by $X_n$. We call an integer $n$ $X$-prime if $X_n$ consists of a single cycle of length $n$ ($n\geq 2$). Then we show some properties of these $X$-primes, particularly, how $X$-primes are related to $X^\prime$-primes as well as to ordinary prime numbers. Here $X$ and $X^\prime$ range over well-known examples (reversal, cyclic shift, shuffle, twist) and some new ones based on the Archimedes spiral and on the Josephus problem.
Original language | English |
---|---|
Pages (from-to) | 1915-1932 |
Number of pages | 18 |
Journal | Discrete applied mathematics |
Volume | 159 |
Issue number | 17 |
DOIs | |
Publication status | Published - 28 Oct 2011 |
Keywords
- Operation on strings
- prime number
- MSC-68R15
- HMI-SLT: Speech and Language Technology
- MSC-11A07
- MSC-12E20
- Twist
- Queneau number
- Shuffle
- Josephus problem