Arbol de rosas

En informática , un árbol de rosas es un término para el valor de una estructura de datos de árbol con un número variable e ilimitado de ramas por nodo. ^[1] El término se utiliza principalmente en la comunidad de programación funcional , por ejemplo, en el contexto del formalismo de Bird-Meertens . ^[2] Aparte de la propiedad de ramificación múltiple, la característica más esencial de los árboles de rosas es la coincidencia de bisimilaridad con identidad : dos árboles de rosas distintos nunca son bisimilares.

Nombramiento

El nombre "rosal" fue acuñado por Lambert Meertens para evocar el rododendro común , de nombre similar y estructura similar . ^[3]

A estos árboles los llamaremos rosales , traducción literal de rododendro (griego ῥόδον = rosa, δένδρον = árbol), por su parecido con el hábito de este arbusto, salvo que este último no crece al revés en el hemisferio norte.

Definición recursiva

Los rosales bien fundados pueden definirse mediante una construcción recursiva de entidades de los siguientes tipos:

Una entidad base es un elemento de un conjunto básico predefinido $V$ de valores (los valores de "punta" ^[3] ).
Una entidad ramificada (alternativamente, una entidad bifurcada o una entidad forestal ) es cualquiera de los siguientes subtipos:
1. Un conjunto de entidades.
2. Una secuencia de entidades.
3. Un mapa parcial de un conjunto predefinido $Σ$ de nombres a entidades.
Cualquiera de (a)(b)(c) puede estar vacío. Nótese que (b) puede verse como un caso especial de (c): una secuencia es simplemente una función de un segmento inicial del conjunto de números naturales. $\mathbb {N}$
Una entidad de emparejamiento es un par ordenado $(F, x)$ tal que $F$ es una entidad de ramificación y $x$ es un elemento de un conjunto predefinido $L$ de valores de "etiqueta". Dado que una entidad de emparejamiento solo puede contener una entidad de ramificación como su componente, existe una división inducida en subtipos (3a), (3b) o (3c) correspondientes a subtipos de entidades de ramificación.

Por lo general, solo se utilizan algunas combinaciones de tipos de entidad para la construcción. El artículo original ^[3] solo considera 1+2b (árboles de rosas con bifurcación de secuencias) y 1+2a (árboles de rosas con bifurcación de conjuntos). En la literatura posterior, la variante 1+2b suele introducirse mediante la siguiente definición:

Árbol de datos a = Hoja a | Nodo [Árbol a]

Un rosal [...] es una hoja que contiene un valor o un nodo que puede tener una lista arbitraria de subárboles .^[4]

La definición más común utilizada en programación funcional (particularmente en Haskell ) combina 3+2b:

datos Rosa α = Nodo α [Rose α]

Un elemento de Rose α consiste en un nodo etiquetado junto con una lista de subárboles .^[1] Es decir, un árbol de rosas es una entidad de emparejamiento (tipo 3) cuya entidad de ramificación es una secuencia (por lo tanto de tipo 2b) de árboles de rosas.

A veces incluso se considera la combinación 1+3b. ^[5]^[6] La siguiente tabla proporciona un resumen de las combinaciones de entidades más establecidas.

Notas:

^ ab Para las combinaciones (2a)(3) y (3)(2b), el segundo tipo de entidad enunciado es solo intermedio: se utiliza solo para la definición de la entidad "final", que es del primer tipo enunciado. Además, los tipos son estrictamente alternantes, es decir, una entidad ramificada solo puede contener una entidad de emparejamiento como su miembro.

Definición general

Los árboles de rosas generales se pueden definir a través de la bisimilitud de multidígrafos apuntados accesibles con el etiquetado apropiado de nodos y flechas. Estas estructuras son una generalización de la noción de grafo apuntado accesible (abreviado como apg ) a partir de una teoría de conjuntos no bien fundada . Usaremos el acrónimo apq para las estructuras multidígrafo descritas a continuación. Esto se entiende como una abreviatura de "accesible pointed quiver" donde quiver es un sinónimo establecido para "multidígrafo".

En correspondencia con los tipos de entidades utilizadas en la definición recursiva, a cada nodo de un apq se le asigna un tipo (1), (2a), (2b), (2c) o (3). Los apq están sujetos a condiciones que imitan las propiedades de las entidades construidas recursivamente.

1. Un nodo de tipo (1) es un elemento del conjunto predefinido $V$ de valores de tierra.
2. Un nodo de tipo (1) no aparece como fuente de una flecha.
1. Un nodo de tipo (3) aparece como la fuente de exactamente una flecha.
2. El objetivo de la flecha mencionada en (a) es un nodo de tipo (2).
Dos flechas distintas con el mismo nodo de origen del tipo (2a) tienen objetivos distintos.
Un nodo se etiqueta solo si es del tipo (3). La etiqueta pertenece al conjunto predefinido $L$ .
1. Una flecha está etiquetada por un índice si su nodo de origen es del tipo (2b). $\mathbb {N}$
2. Una flecha se etiqueta con un nombre de un conjunto predefinido $Σ$ si su nodo de origen es del tipo (2c).
3. De lo contrario, la flecha no estará etiquetada.
Las etiquetas de las flechas con el mismo nodo de origen son distintas.
Las etiquetas de flechas con el mismo nodo de origen del tipo (2b) forman un segmento inicial de . $\mathbb {N}$

Una bisimilaridad entre apqs $𝒳 = (X, ...)$ y $𝒴 = (Y, ...)$ es una relación $R \subseteq X \times Y$ entre nodos tales que las raíces de $𝒳$ y $𝒴$ están $R$ -relacionadas y para cada par $(x, y)$ de nodos $R$ -relacionados, se satisface lo siguiente:

Los nodos $x$ $e$ y tienen el mismo tipo.
Si $x$ e $y$ son del tipo (1) entonces son idénticos.
Si $x$ e $y$ son del tipo (3) entonces tienen la misma etiqueta.
Para cada flecha a de 𝒳 cuyo nodo fuente es x existe una flecha b de 𝒴 cuya fuente es y y
1. Los nodos objetivo de $a$ y b están relacionados con $R$ ,
2. Las etiquetas de $a$ y b , si están definidas, son idénticas.
Se satisface una condición simétrica con $𝒳$ y $𝒴$ intercambiados.

Se dice que dos apqs $𝒳$ y $𝒴$ son bisimilares si existe una relación de bisimilaridad $R$ para ellos. Esto establece una relación de equivalencia en la clase de todos los apqs.

Un árbol de rosas es entonces una representación fija de la clase $𝒞$ de apqs que son bisimilares a algún apq $𝒳$ dado . Si el nodo raíz de $𝒳$ es de tipo (1) entonces $𝒞 = {𝒳$ }, por lo tanto $𝒞$ puede ser representado por este nodo raíz. De lo contrario, $𝒞$ es una clase propia – en este caso la representación puede ser proporcionada por el truco de Scott para ser el conjunto de aquellos elementos de $𝒞$ que tienen el rango más bajo.

Como resultado de la construcción de teoría de conjuntos anterior, se define la clase $ℛ de todos los árboles de rosas, dependiendo de los conjuntos$ $V$ (valores de base), $Σ$ (nombres de flechas) y $L$ (etiquetas de nodos) como constituyentes definitorios. Posteriormente, la estructura de apqs se puede trasladar a una estructura multidígrafo etiquetada sobre $ℛ$ . Es decir, los elementos de $ℛ$ pueden considerarse en sí mismos como "nodos" con asignación de tipo inducida, etiquetado de nodos y flechas. La clase $𝒜$ de flechas es una subclase de $\mathbb {N}$ , es decir, las flechas son parejas fuente-objetivo o triples fuente-etiqueta-objetivo según el tipo de la fuente.

Para cada elemento $r$ de $ℛ$ existe un apq inducido $𝒳 = (X, A, r, ...)$ tal que $r$ es el nodo raíz de $𝒳$ y los respectivos conjuntos $X$ y $A$ de nodos y flechas de $𝒳$ están formados por aquellos elementos de $ℛ$ y $𝒜$ que son accesibles a través de un camino de flechas que comienza en $r$ . El apq inducido $𝒳$ es bisimilar a los apq utilizados para la construcción de $r$ .

Mapas de nombres de rutas

Los árboles de rosas que no contienen nodos de ramificación de conjuntos (tipo 2a) se pueden representar mediante mapas de nombres de ruta. Un nombre de ruta es simplemente una secuencia finita de etiquetas de flecha. Para una ruta de flecha $a \to = [a 1, ..., a n]$ (una secuencia finita de flechas consecutivas), el nombre de ruta de $p$ es la secuencia correspondiente $σ (a \to) = [σ (a 1), ..., σ (a n)]$ de etiquetas de flecha. Aquí se supone que cada flecha está etiquetada ( $σ$ denota la función de etiquetado). En general, cada ruta de flecha debe reducirse primero eliminando todas sus flechas provenientes de nodos de emparejamiento (tipo 3).

Una ruta de acceso $p$ se puede resolver si existe una ruta de flecha con origen en la raíz $a \to$ cuyo nombre de ruta es $p$ . Tal $a \to$ se proporciona de forma única hasta una posible última flecha sin etiquetar (obtenida en un nodo de emparejamiento). El nodo de destino de una ruta de acceso resoluble no vacía es el nodo de destino de la última flecha de la ruta de flecha con origen en la raíz correspondiente que no termina con una flecha sin etiquetar. El destino de la ruta vacía es el nodo raíz.

Dado un árbol de rosas $r$ que no contiene nodos de ramificación de conjuntos, el mapa de rutas de $r$ es un mapa $t$ que asigna a cada ruta resoluble $p$ su valor $t (p)$ de acuerdo con el siguiente esquema general:

$\mathbb {N}$ a——— → $(V \cup {⊥} \cup L) \times T$

Recordemos que $\cup$ $Σ$ es el conjunto de etiquetas de flechas ( es el conjunto de números naturales y $Σ$ es el conjunto de nombres de flechas) $L$ es el conjunto de etiquetas de nodos y $V$ es el conjunto de valores de base. Los símbolos adicionales $⊥$ y $T$ significan respectivamente un indicador de un nombre de ruta resoluble y el conjunto de etiquetas de tipo, $T$ $= {'1', '2b', '2c', '3b', '3c'$ }. El mapa $t$ se define mediante la siguiente prescripción ( $x$ denota el objetivo de $p$ ): $\mathbb {N}$ $\mathbb {N}$

Se puede demostrar que los distintos rosales tienen diferentes mapas de rutas de acceso. En el caso de los rosales "homogéneos" no es necesario el etiquetado de tipo, y su mapa de rutas de acceso $t$ se puede definir como se resume a continuación:

En cada caso, existe una axiomatización simple en términos de nombres de ruta:

$dom(t)$ es un subconjunto cerrado por prefijo no vacío de $⁎$ o $Σ$ $⁎$ . En el caso de $⁎$ , $dom($ $t$ $)$ también debe estar "cerrado por hermano izquierdo" para formar un dominio de árbol , consulte Codificación por secuencias . $\mathbb {N}$ $\mathbb {N}$
En el caso de una lista anidada o un valor de diccionario anidado, si $p$ es una ruta de acceso que no es máxima en $dom(t)$ , entonces $t (p) = ⊥$ . ^{[p 2]}

En particular, un árbol de rosas en el sentido más común de "Haskell" es simplemente una función de un conjunto no vacío cerrado por prefijo y cerrado por hermano izquierdo de secuencias finitas de números naturales a un conjunto $L$ . Esta definición se utiliza principalmente fuera de la rama de la programación funcional, véase Árbol (teoría de autómatas) . Por lo general, los documentos que utilizan esta definición no mencionan el término "árbol de rosas" en absoluto.

Notas:

^ ab Si $dom(t) = M ⁎$ para un subconjunto de o $Σ$ entonces el mapa de ruta $t$ es un mapeo de secuencias de símbolos de entrada a símbolos de salida de una máquina de Moore . Específicamente, cada máquina de Moore con el conjunto $M$ de símbolos de entrada siendo un segmento inicial de y con todos los estados alcanzables es bisimilar a un árbol de rosas en el sentido de Haskell, vea el ejemplo de un árbol de rosas no bien fundado. Se puede observar una relación similar entre diccionarios anidados (o listas) y máquinas Mealy , vea Diccionario anidado . $\mathbb {N}$ $\mathbb {N}$
^ Para garantizar que una lista anidada o un diccionario anidado sean, respectivamente, una lista o un diccionario en primer lugar, se debe exigir explícitamente que se cumpla la condición $t (p) = ⊥ para la ruta vacía$ $p$ . Esto afirma que los casos como x = 5no se consideran "valores de árbol".

Ejemplos

Los diagramas que aparecen a continuación muestran dos ejemplos de árboles de rosas junto con el código Haskell correspondiente. En ambos casos, se utiliza el módulo Data.Tree ^[11] tal como lo proporciona el paquete de contenedores Haskell. ^[12] El módulo presenta los árboles de rosas como entidades de emparejamiento mediante la siguiente definición:

datos Árbol a = Nodo { rootLabel :: a , -- ^ etiqueta valor subForest :: [ Árbol a ] -- ^ cero o más árboles secundarios }

Ambos ejemplos están diseñados para demostrar el concepto de "compartir subestructuras" ^[13] , que es una característica distintiva de los rosales. En ambos casos, la función de etiquetado es inyectiva (de modo que las etiquetas 'a', 'b', 'c'o 'd'identifican de forma única un subárbol/nodo), lo que no necesita satisfacerse en general. Los números naturales (0, 1, 2 o 3) a lo largo de las flechas indican la posición basada en cero en la que aparece un árbol en la subForestsecuencia de un "superárbol" particular. Como consecuencia de posibles repeticiones en subForest, puede haber múltiples flechas entre nodos. En cada uno de los ejemplos, el rosal en cuestión está etiquetado por 'a'y es igual al valor de la avariable en el código. En ambos diagramas, el árbol está señalado por una flecha sin fuente.

Rosal bien fundado

importar Data.Tree main :: IO () main = do let d = Nodo { etiqueta_raíz = 'd' , subBosque = [] } let c = Nodo { etiqueta_raíz = 'c' , subBosque = [ d ] } let b = Nodo { etiqueta_raíz = 'b' , subBosque = [ d , c ] } let a = Nodo { etiqueta_raíz = 'a' , subBosque = [ b , c , c , c ] } print a

Rosal sin fundamento

importar Data.Tree main :: IO () main = do let root x = caso x de 'a' -> ( x ,[ x , 'b' ]) 'b' -> ( x ,[ x , 'c' ]) 'c' -> ( x ,[ x , 'a' ]) let a = unfoldTree root 'a' putStrLn ( take 900 ( show a ) ++ "... (y así sucesivamente)" )

El primer ejemplo presenta un árbol de rosas bien fundado aobtenido mediante una construcción incremental. Primero dse construye , luego cthen by finalmente a. El árbol de rosas se puede representar mediante el mapa de nombres de ruta que se muestra a la izquierda.

El segundo ejemplo presenta un árbol de rosas no bien fundado aconstruido por un constructor en amplitud unfoldTree. El árbol de rosas es una máquina de Moore, véanse las notas anteriores. Su mapa de ruta $t : {0,1} ⁎ \to {'a','b','c'$ } se define por $t (p)$ es respectivamente igual a $'a'$ o $'b'$ o $'c'$ según $n módulo 3$ donde $n$ es el número de ocurrencias de $1$ en $p$ .

Relación con las estructuras de datos de árboles

La definición general proporciona una conexión a las estructuras de datos de árbol:

Los rosales son estructuras arbóreas módulo bisimilaridad.

Asignación de estructuras de datos de árboles a sus valores

Las "estructuras de árbol" son aquellas apqs (multidígrafos etiquetados de la definición general) en las que cada nodo es accesible por un único camino de flecha. Cada árbol de rosas es bisimilar a una estructura de árbol de este tipo (ya que cada apq es bisimilar a su desdoblamiento ) y cada estructura de árbol de este tipo es bisimilar a exactamente un árbol de rosas que, por lo tanto, puede considerarse como el valor de la estructura de árbol.

El diagrama de la derecha muestra un ejemplo de este tipo de mapeo de estructura a valor. En la parte superior del diagrama, se muestra un árbol ordenado $T etiquetado con nodos, que contiene 23 nodos. En la parte inferior, se muestra un árbol de rosas$ $R$ que es el valor de $T.$ (Tanto en $T$ como $en R$ , las flechas hermanas están ordenadas implícitamente de izquierda a derecha). Hay un mapeo inducido de subárbol a subvalor que se muestra parcialmente mediante flechas azules.

Observe que la asignación es de varios a uno: distintas estructuras de datos de árboles pueden tener el mismo valor. Como consecuencia particular, un árbol de rosas en general no es un árbol en términos de la relación de "subvalores" entre sus subvalores, consulte #Controversia_terminológica.

Tipo de datos de árbol

La asignación de valores descrita anteriormente se puede utilizar para aclarar la diferencia entre los términos "estructura de datos de árbol" y "tipo de datos de árbol":

Un tipo de datos de árbol es un conjunto de valores de estructuras de datos de árbol . ^{[dt 1]}

Tenga en cuenta que existen dos grados de discrepancia entre los términos. Esto se hace evidente cuando se compara un tipo de datos de árbol único con una estructura de datos de árbol único . Un tipo de datos de árbol único contiene (infinitamente) muchos valores, cada uno de los cuales está representado por (infinitamente) muchas estructuras de datos de árbol.

Por ejemplo, dado un conjunto $L = {'a','b','c','d'$ } de etiquetas, el conjunto de árboles de rosas en el sentido de Haskell (3b) con etiquetas tomadas de $L$ es un tipo de datos de árbol único. Todos los ejemplos de árboles de rosas anteriores pertenecen a este tipo de datos.

Notas:

^ Sin embargo, no todos los conjuntos de valores de estructuras de datos de árbol son un tipo de datos de árbol.

Controversia terminológica

Como se puede observar en el texto y los diagramas anteriores, el término "rosal" es controvertido. Hay dos cuestiones interrelacionadas:

Significado oscuro de "nodo".
Discrepancia entre “árbol” y “compartir subestructuras”.

Curiosamente, el término "nodo" no aparece en el artículo original ^[3], salvo en una única ocasión en un párrafo informal de la página 20. En la literatura posterior, la palabra se utiliza con profusión. Esto ya se puede observar en los comentarios citados a las definiciones:

Un rosal [...] es una hoja [...] o un nudo [...] .^[4]
Un elemento de Rose α consiste en un nodo etiquetado [...] .^[1]

En particular, la definición de rosales en el sentido más común de Haskell sugiere que (dentro del contexto del discurso) "nodo" y "árbol" son sinónimos. ¿Significa esto que cada rosal coincide con su nodo raíz? Si es así, ¿se considera que esta propiedad es específica de los rosales o se aplica también a otros árboles? Estas preguntas quedan sin respuesta.

El problema (B) se hace evidente al observar los diagramas de los ejemplos anteriores. Ambos diagramas son fieles en el sentido de que cada nodo se dibuja exactamente una vez . Se puede ver inmediatamente que los gráficos subyacentes no son árboles. Usando una cita de Árbol (teoría de grafos)

Los diversos tipos de estructuras de datos a los que en informática se hace referencia como árboles tienen gráficos subyacentes que son árboles en la teoría de grafos [...]

Se puede concluir que los rosales en general no son árboles en el sentido habitual que conocemos en la informática.

Rosal bayesiano

Existe al menos una adopción del término "árbol de rosas" en informática en la que se excluye la "compartición de subestructuras". El concepto de un árbol de rosas bayesiano se basa en la siguiente definición de árboles de rosas:

$T$ es un rosal si $T = {x$ } para algún punto de datos $x$ o $T = {T 1, ... , T n T$ } donde $T i$ son rosales sobre conjuntos disjuntos de puntos de datos. ^[14]

Referencias

^ abc Bird, Richard (1998). Introducción a la programación funcional con Haskell. Hemel Hempstead, Hertfordshire, Reino Unido: Prentice Hall Europe. pág. 195. ISBN 0-13-484346-0.
^ Malcolm, Grant (1990). "Estructuras de datos y transformación de programas". Ciencia de la programación informática . 14 (2): 255–279. doi : 10.1016/0167-6423(90)90023-7 .
^ abcd Meertens, Lambert (enero de 1988). "Primeros pasos hacia la teoría de los rosales" (PDF) . {{cite journal}}: Requiere citar revista |journal=( ayuda )
^ ab Bird, Richard; Gibbons, Jeremy (2020). Diseño de algoritmos con Haskell. Cambridge University Press. ISBN 9781108491617.
^ Skillicorn, David B. (1996). "Implementación paralela de esqueletos de árboles" (PDF) . Journal of Parallel and Distributed Computing . 39 (2): 115–125. doi :10.1006/jpdc.1996.0160.
^ Seemann, Mark. "El rosal codificado por la Iglesia".
^ Morawietz, Frank (2008). Enfoques de dos pasos para el formalismo del lenguaje natural. Walter de Gruyter. ISBN 9783110197259.
^ Kosky, Anthony (1995). Transformación de bases de datos con estructuras de datos recursivas (Tesis).
^ Niwiński, Damian (1997). "Caracterización de punto fijo del comportamiento infinito de sistemas de estados finitos" (PDF) . Ciencias de la Computación Teórica . 189 (1–2): 1–69. doi :10.1016/S0304-3975(97)00039-X.
^ Dagnino, Francesco (2020). "Coaxiomas: definiciones coinductivas flexibles mediante sistemas de inferencia". Métodos lógicos en informática . 15 . arXiv : 1808.02943 . doi :10.23638/LMCS-15(1:26)2019. S2CID 51955443.
^ "Datos.Árbol".
^ "Contenedores: Varios tipos de contenedores de hormigón".
^ Gibbons, Jeremy (1991). Álgebras para algoritmos de árboles (PDF) (Ph.D.). Universidad de Oxford.
^ Blundell, Charles; Whye Teh, Yee; Heller, Katherine A. (2010). Árboles de rosas bayesianos (PDF) . 26.ª Conferencia sobre incertidumbre en inteligencia artificial.