una operación en cadenas binarias

Question

Recientemente, como parte de la investigación conjunta, Tom Roby fue llevado a una curiosa operación de las cadenas de L y R a la que él llama "error de lectura": Podemos empezar por la lectura de la cadena a la izquierda. Cuando el símbolo que acabamos de leer es una L, el siguiente símbolo que leer es el de la izquierda no leídos símbolo; pero cuando el símbolo que acabamos de leer es una R, el siguiente símbolo que leer es el de más a la derecha no leídos símbolo. Por ejemplo, si nuestra cadena de L y R es LLRRLRLR, leemos las posiciones en el orden 1,2,3,8,7,4,6,5, la obtención de la despedida de lectura LLRRLRRL.

Puede ser más natural que pensar en esto como una acción en la circular de palabras; cuando leemos una carta, la borramos, cerrar el círculo, y se mueve a la izquierda o a la derecha de la eliminación de punto.

Ha esta operación se ha estudiado antes?

Answer 1

Bien, ahora, ya que simplemente se hundió mi mañana en su estudio. Estoy seguro que soy un tonto para un ingenuo combinatoria problema. Aquí es lo que yo sé, o puede conjetura:

• El mapa que usted describe es un bijection en palabras de longitud $n$, debido a que es fácil de escribir su inversa. He incluido el código de python a continuación.
• Deje $B_L$ ser el rebote de lectura de algoritmo. Deje $B_R$ ser el rebote de lectura algoritmo con el siguiente cambio: sustituir la frase "tenemos que empezar por la lectura de la cadena a la izquierda" con "comenzamos la lectura de la cadena de la derecha". A continuación, $B_LB_R^{-1}(w)$ parece desplazarse $w$ cíclicamente por una letra. A veces el cambio es la izquierda, y a veces a la derecha; que de estas cosas sucede, depende de $w$ en una manera que no entiendo. Me di cuenta de esto porque el máximo de la órbita de los tamaños de $B_LB_R^{-1}(w)$ por cada $n$ parecen coincidir con la secuencia OEIS https://oeis.org/A027375.
• Deje $S_n$ el conjunto de palabras $w$ de la longitud de la $n$ para que $B_L(w) = B_R(w)$. A continuación, la secuencia $\{|S_{n+1}| - |S_n|\}$ parece ser que los números de Fibonacci, al menos para $n\geq 2$. Esto probablemente significa $S_n$ tiene una agradable estructura.

Ninguno de los otros evidente estadísticas que describen este mapa está en la OEIS todavía.

Aquí están ingenuo python implementaciones de $B_L, B_R, B_L^{-1}, B_R^{-1}$ si desea comprobar estas afirmaciones.

def bounce_left(w):
    if len(w) == 1:
        return w
    leftchar = w[0]
    x = w[1:]
    if(leftchar == "L"):
        return leftchar + bounce_left(x)
    else:
        return leftchar + bounce_right(x)

def bounce_right(w):
    if len(w) == 1:
        return w
    last_index = len(w) - 1
    rightchar = w[last_index]
    x = w[:last_index]
    if(rightchar == "L"):
        return rightchar + bounce_left(x)
    else:
        return rightchar + bounce_right(x)


def unbounce(w):
    if w == "":
        return ""
    output = ""
    n = len(w) - 1
    for index in reversed(range(n)):
        if w[index] == "L":
            output = w[index+1] + output
        else:
            output = output + w[index+1]
    return output

def unbounce_left(w):
    return unbounce("L" + w) 

def unbounce_right(w):
    return unbounce("R" + w)

Answer 2

Puede ser conveniente considerar la posibilidad de una extensión del mapa de palabras en un doble alfabeto $A=\{L,R\}\times \{L,R\}$ o, de manera equivalente, los pares de palabras en $\{L,R\}$ de la longitud de la misma. (Su situación se obtiene cuando se considera un par: una palabra y el reverso de la palabra.) La ventaja de la extensión es que el mapa está dada por un autómata de Mealy. Aunque no sé si exactamente esta transformación se ha estudiado, los grupos generados por tales transformaciones han sido de curso estudiado como "autómata grupos". Ver los papeles y libros de la Grigorchuk, Nekrashevych y otros.

Answer 3

Sospecho que no ha sido estudiado, ¡pero debería serlo! Baso esto en el hecho de que varias estadísticas que uno podría esperar estar asociadas con él no aparecen en el OEIS (incluso con una apelación a superseeker@oeis.org). Por ejemplo,$$2, 3, 6, 7, 19, 27, 36, 79, 130, 384, 473, 710, 2903, 4197$ $ proporciona la órbita de tamaño máximo para cadenas de longitudes de hasta$16.$

Resulta que$RRRRRLRLLLLLL$ tiene una órbita de tamaño$473$ y esa es la órbita más larga para cualquier cadena de longitud 13.