Definimos un lenguaje de árbol regular como en el libro TATA : es el conjunto de árboles aceptado por un autómata de árbol finito no determinista (Capítulo 1) o, de manera equivalente, el conjunto de árboles generado por una gramática de árbol regular (Capítulo 2). Ambos formalismos se parecen mucho a los conocidos análogos de cuerdas.
¿Existe un lenguaje de árbol normal en el que la altura promedio de un árbol de tamaño no sea ni ?
Obviamente, hay lenguajes de árbol de modo que la altura de un árbol es lineal en su tamaño; y en el libro Analytic Combinatorics se muestra, por ejemplo, que los árboles binarios de tamaño tienen una altura promedio de . Si entiendo correctamente la Proposición VII.16 (p.537) del libro mencionado, entonces hay un amplio subconjunto de lenguajes de árbol regulares que tienen una altura promedio de , es decir, aquellos en los que el lenguaje de árbol También es una variedad simple de árboles que cumplen algunas condiciones adicionales.
Entonces, me preguntaba si hay un lenguaje de árbol regular que muestre una altura promedio diferente o si existe una verdadera dicotomía para los lenguajes de árbol regulares.
Nota: Esta pregunta se ha hecho anteriormente en Ciencias de la Computación , pero no ha recibido respuesta durante más de tres meses. Me gustaría volver a publicarlo aquí porque la pregunta es demasiado antigua para migrar y porque todavía hay un interés en la pregunta. Aquí hay un enlace a la publicación original.
Respuestas:
Creo que la respuesta es como usted sugiere que no son posibles otras asintóticas que no sean , y . Una ruta prometedora para demostrar esto podría ser aplicar las técnicas del documento que deriva las asintóticas a los árboles de ejecución del lenguaje regular. Tenga en cuenta que se acepta un árbol si existe un árbol de ejecución, por lo que debería ser posible obtener primero (usando loc.cit. ) La altura promedio de un árbol de ejecución generado aleatoriamente y tomarlo desde allí, es decir, mostrar que proyectar los estados sí No cambia la altura media.Θ(1) Θ(n−−√) Θ(n) Θ(n−−√)
fuente