Red de transición recursiva con filtrado y extracción

Una red de transición recursiva de extracción filtrada ( FPRTN ), ^{[ 1 ]} o simplemente red de extracción filtrada ( FPN ), es una red de transición recursiva ( RTN ) ^{[ 2 ]} extendida con un mapa de estados a claves donde el retorno de un salto de subrutina requiere que los estados de aceptación y retorno se asignen a la misma clave. Las RTN son máquinas de estados finitos que pueden verse como autómatas de estados finitos extendidos con una pila de estados de retorno; así como transiciones de consumo y${\displaystyle \varepsilon }$Las transiciones RTN pueden definir transiciones de llamada. Estas transiciones realizan un salto de subrutina al insertar el estado de destino de la transición en la pila y llevar la máquina al estado llamado. Cada vez que se alcanza un estado de aceptación, se extrae el estado de retorno de la parte superior de la pila, siempre que esta no esté vacía, y la máquina pasa a dicho estado.

A lo largo de este artículo, nos referimos a las redes de transición recursivas con filtrado como FPN , aunque este acrónimo es ambiguo (por ejemplo, redes de Petri difusas ). Las redes con filtrado y las FPRTN son alternativas inequívocas.

Una FPN es una estructura${\displaystyle (Q,K,\Sigma ,\delta ,\kappa ,Q_{I},F)}$dónde

• ${\displaystyle Q}$es un conjunto finito de estados,
• ${\displaystyle K}$es un conjunto finito de claves,
• ${\displaystyle \Sigma }$es un alfabeto de entrada finito,
• ${\displaystyle \delta :Q\times (\Sigma \cup \{\varepsilon \}\cup Q)\to Q}$es una función de transición parcial,${\displaystyle \varepsilon }$siendo el símbolo vacío,
• ${\displaystyle \kappa :Q\to K}$es un mapa de estados a claves,
• ${\displaystyle Q_{I}\subsetequ Q}$es el conjunto de estados iniciales, y
• ${\displaystyle F\subseteq Q}$es el conjunto de estados de aceptación.

Las transiciones representan la posibilidad de llevar la FPN desde un estado fuente.${\displaystyle q_{s}}$a un estado objetivo${\displaystyle q_{t}}$posiblemente realizando una acción adicional. Dependiendo de esta acción, distinguimos los siguientes tipos de transiciones definidas explícitamente :

• ${\displaystyle \varepsilon }$-Las transiciones son transiciones de la forma${\displaystyle \delta (q_{s},\varepsilon )\to q_{t}}$y no realizar ninguna acción adicional,
• Las transiciones de consumo son transiciones de la forma${\displaystyle \delta (q_{s},\sigma )\to q_{t}}$y consumir un símbolo de entrada${\displaystyle \sigma }$, y
• Las transiciones de llamada son transiciones de la forma${\displaystyle \delta (q_{s},q_{c})\to q_{t}}$y realizar un salto de subrutina al estado llamado${\displaystyle q_{c}}$antes de llegar${\displaystyle q_{t}}$.

El comportamiento de las transiciones de llamadas se rige por dos tipos de transiciones definidas implícitamente :

• para cada transición de llamada${\displaystyle \delta (q_{s},q_{c})\to q_{t}}$La FPN define implícitamente una transición de empuje que lleva a la máquina desde${\displaystyle q_{s}}$a${\displaystyle q_{c}}$empujando${\displaystyle q_{t}}$en la pila y
• para cada par de estados${\displaystyle (q_{f},q_{r})\in F\times Q}$La FPN define implícitamente una transición pop que lleva a la máquina desde${\displaystyle q_{f}}$a${\displaystyle q_{r}}$al estallar${\displaystyle q_{r}}$desde la pila si${\displaystyle q_{r}}$es el estado en la parte superior de la pila y${\displaystyle \kappa (q_{f})=\kappa (q_{r})}$.

Las transiciones push inicializan los saltos de subrutina y las transiciones pop son equivalentes a las instrucciones return .

Un texto ( en lenguaje natural ) puede enriquecerse con metainformación mediante la aplicación de una RTN con salida ; por ejemplo, una RTN que inserta etiquetas XML puede usarse para transformar un texto plano en un documento XML estructurado. Una RTN con salida que representa una gramática de lenguaje natural delimitaría y agregaría la estructura sintáctica de cada oración de texto (ver análisis ). Otras RTN con salida podrían simplemente marcar segmentos de texto que contienen información relevante (ver extracción de información ). La aplicación de una RTN con salida que representa una gramática ambigua da como resultado un conjunto de posibles traducciones o interpretaciones de la entrada. El cálculo de este conjunto tiene un costo exponencial en el peor de los casos , incluso para un analizador Earley para RTN con salida, ^{[ 3 ]} debido a casos en los que el número de traducciones aumenta exponencialmente con respecto a la longitud de la entrada; por ejemplo, el número de interpretaciones de una oración de lenguaje natural aumenta exponencialmente con respecto al número de adjuntos de frases preposicionales no resueltos : ^{[ 4 ] [ 5 ]}

• En la oración la niña vio al mono con el telescopio , se desconoce si la niña usó el telescopio o si el mono lo sostenía (2 ¹ interpretaciones),
• En la oración la niña vio al mono con el telescopio en el jardín , también se desconoce si el mono estaba en el jardín o si la acción tuvo lugar en el jardín (2 ² interpretaciones),
• En la oración la niña vio al mono con el telescopio en el jardín debajo del árbol , también se desconoce si el mono estaba debajo del árbol o si la acción tuvo lugar debajo del árbol (2 ³ interpretaciones),
• etc.

Las FPN sirven como una representación compacta de este conjunto de traducciones, lo que permite calcularlo en tiempo cúbico mediante un analizador tipo Earley. ^{[ 1 ]} Los estados de la FPN corresponden a estados de ejecución (ver pasos de instrucción ) de un analizador Earley para RTN sin salida, y las transiciones de la FPN corresponden a posibles traducciones de símbolos de entrada.${\displaystyle \kappa }$El mapa de la FPN resultante proporciona la correspondencia entre los segmentos de salida representados y los segmentos de entrada reconocidos: dada una secuencia de entrada reconocida${\displaystyle \sigma _{1}\ldots \sigma _{l}}$y una ruta FPN${\displaystyle p}$comenzando en un estado${\displaystyle q}$y terminando en un estado${\displaystyle q^{\prime }}$,${\displaystyle p}$representa una posible traducción del segmento de entrada${\displaystyle \sigma _{\kappa (q)+1}\ldots \sigma _{\kappa (q^{\prime })}}$La función de filtrado de salida es necesaria para evitar que las rutas FPN representen traducciones de segmentos de entrada desconectados o superpuestos : una llamada FPN puede contener varias rutas de traducción desde el estado llamado a un estado de aceptación, donde los segmentos de entrada a los que corresponden comparten el mismo punto de inicio, pero no necesariamente tienen la misma longitud. Solo los estados de retorno que corresponden al mismo punto de entrada que el estado de aceptación que finaliza la llamada son estados de retorno válidos .