autómata ponderado

Máquina de estados finitos donde los bordes soportan pesos.

Diagrama de Hasse de algunas clases de autómatas cuantitativos, ordenados por expresividad. ^{[1] : Fig.1}

En informática teórica y teoría del lenguaje formal , un autómata ponderado o una máquina de estados finitos ponderada es una generalización de una máquina de estados finitos en la que las aristas tienen pesos , por ejemplo números reales o enteros . Las máquinas de estados finitos sólo son capaces de dar respuesta a problemas de decisión ; toman como entrada una cadena y producen una salida booleana , es decir, "aceptar" o "rechazar". Por el contrario, los autómatas ponderados producen un resultado cuantitativo , por ejemplo, un recuento de cuántas respuestas son posibles en una cadena de entrada determinada, o una probabilidad de qué tan probable es la cadena de entrada según una distribución de probabilidad . ^[2] Son uno de los modelos de autómatas cuantitativos más simples estudiados. ^{[1] : Fig.1}

La definición de autómata ponderado generalmente se da sobre un semianillo arbitrario , un conjunto abstracto con una operación de suma y una operación de multiplicación . El autómata consta de un conjunto finito de estados, un alfabeto de entrada finito de caracteres y aristas que están etiquetadas con un carácter y un peso . El peso de cualquier camino en el autómata se define como el producto de los pesos a lo largo del camino, y el peso de una cadena es la suma de los pesos de todos los caminos etiquetados con esa cadena. El autómata ponderado define así una función desde hasta . ^[2] ${\displaystyle R}$ ${\displaystyle +}$ ${\displaystyle \times }$ ${\displaystyle \Sigma }$ ${\displaystyle \Sigma }$ ${\displaystyle R}$ ${\displaystyle \Sigma ^{*}}$ ${\displaystyle R}$

Los autómatas ponderados generalizan los autómatas finitos deterministas (DFA) y los autómatas finitos no deterministas (NFA), que corresponden a autómatas ponderados sobre el semiring booleano , donde la suma es una disyunción lógica y la multiplicación es una conjunción lógica . En el caso de DFA, solo hay una ruta de aceptación para cualquier cadena de entrada, por lo que no se aplica la disyunción. Cuando los pesos son números reales y los pesos salientes para cada estado suman uno, los autómatas ponderados pueden considerarse un modelo probabilístico y también se conocen como autómatas probabilísticos . Estas máquinas definen una distribución de probabilidad sobre todas las cadenas y están relacionadas con otros modelos probabilísticos como los procesos de decisión de Markov y las cadenas de Markov .

Los autómatas ponderados tienen aplicaciones en el procesamiento del lenguaje natural donde se utilizan para asignar pesos a palabras y oraciones, ^{[3] [2] : 571–596} así como en la compresión de imágenes . ^{[2] : 453–480} Fueron introducidos por primera vez por Marcel-Paul Schützenberger en su artículo de 1961 Sobre la definición de una familia de autómatas. ^[4] Desde su introducción, se han propuesto muchas extensiones, por ejemplo, autómatas ponderados anidados, ^[5] autómatas de registro de costos, ^[6] y transductores ponderados de estado finito . ^[7] Los investigadores han estudiado los autómatas ponderados desde la perspectiva de aprender una máquina a partir de su comportamiento de entrada-salida ^[8] (ver teoría del aprendizaje computacional ) y estudiar cuestiones de decidibilidad . ^[9]

Definición

Un semiring conmutativo (o rig ) es un conjunto R equipado con dos elementos distinguidos y operaciones de suma y multiplicación , y que es conmutativo y asociativo con identidad , es conmutativo y asociativo con identidad , se distribuye sobre y 0 es un elemento absorbente para . ${\displaystyle 0\neq 1}$ ${\displaystyle \oplus }$ ${\displaystyle \otimes }$ ${\displaystyle \oplus }$ ${\displaystyle 0}$ ${\displaystyle \otimes }$ ${\displaystyle 1}$ ${\displaystyle \otimes }$ ${\displaystyle \oplus }$ ${\displaystyle \otimes }$

Un autómata ponderado ${\displaystyle R}$ es una tupla donde: ${\displaystyle {\mathcal {A}}=(Q,\Sigma ,\Delta ,I,F)}$

• ${\displaystyle Q}$es un conjunto finito de estados.
• ${\displaystyle \Sigma }$es un alfabeto finito.
• ${\displaystyle \Delta \subseteq Q\times \Sigma \times R\times Q}$es un conjunto finito de transiciones , donde se llama carácter y se llama peso . ${\displaystyle (q,\sigma ,w,q')}$ ${\displaystyle \sigma }$ ${\displaystyle w}$
• ${\displaystyle I:Q\to R}$es una función de peso inicial.
• ${\displaystyle F:Q\to R}$es una función de peso final.

Una ruta de entrada es una ruta finita en el gráfico, donde la concatenación de las etiquetas de caracteres es igual a . El peso del camino es el producto ( ) de los pesos a lo largo del camino, multiplicado adicionalmente por los pesos inicial y final . El peso de la palabra es la suma ( ) de los pesos de todas las rutas de entrada (o 0 si no hay rutas de aceptación). De esta manera la máquina define una función . ${\displaystyle w\in \Sigma ^{*}}$ ${\displaystyle w}$ ${\displaystyle q_{0},q_{1},\ldots ,q_{n}}$ ${\displaystyle \otimes }$ ${\displaystyle I(q_{0})\otimes I(q_{n})}$ ${\displaystyle w}$ ${\displaystyle \oplus }$ ${\displaystyle w}$ ${\displaystyle [\![{\mathcal {A}}]\!]:\Sigma ^{*}\to R}$

Ambigüedad y determinismo

Dado que es un conjunto de transiciones, los autómatas ponderados permiten múltiples transiciones (o rutas) en una única cadena de entrada. Por lo tanto, un autómata ponderado puede considerarse análogo a un autómata finito no determinista (NFA). Al igual que en los AFN, se consideran restricciones de autómatas ponderados que corresponden a los conceptos de autómata finito determinista y autómata finito inequívoco (autómatas ponderados deterministas y autómatas ponderados inequívocos, respectivamente). ${\displaystyle \Delta }$

Primero, una definición preliminar: el NFA subyacente de es un NFA formado eliminando todas las transiciones con peso y luego borrando todos los pesos en las transiciones , de modo que el nuevo conjunto de transiciones se encuentre en . Los estados iniciales y finales son el conjunto de estados tales que y , respectivamente. ${\displaystyle {\mathcal {A}}}$ ${\displaystyle 0}$ ${\displaystyle \Delta }$ ${\displaystyle Q\times \Sigma \times Q}$ ${\displaystyle q}$ ${\displaystyle I(q)\neq 0}$ ${\displaystyle F(q)\neq 0}$

Un autómata ponderado es determinista si el NFA subyacente es determinista e inequívoco si el NFA subyacente es inequívoco. Todo autómata ponderado determinista es inequívoco.

Tanto en el caso determinista como en el caso inequívoco, siempre hay como máximo una ruta de aceptación, por lo que la operación nunca se aplica y puede omitirse de la definición. ${\displaystyle \oplus }$

Variaciones

• A veces se omite el requisito de que haya un elemento cero para ; en este caso la máquina define una función parcial desde hasta en lugar de una función total. ${\displaystyle \oplus }$ ${\displaystyle \Sigma ^{*}}$ ${\displaystyle R}$

• Es posible ampliar la definición para permitir transiciones épsilon , donde está la cadena vacía. En este caso, se debe exigir que no haya ciclos de transiciones épsilon. Esto no aumenta la expresividad de los autómatas ponderados. ^{[2] [10]} Si se permiten transiciones épsilon, los pesos iniciales y finales pueden reemplazarse por conjuntos de estados iniciales y finales sin pérdida de expresividad. ${\displaystyle (q,\epsilon ,w,q')}$ ${\displaystyle \epsilon }$

• Algunos autores omiten las funciones de peso inicial y final y . ^[1] En cambio, y son reemplazados por un conjunto de estados inicial y final. Si las transiciones épsilon no están presentes, esto técnicamente disminuye la expresividad, ya que obliga a depender únicamente del número de estados que son tanto iniciales como finales. ${\displaystyle I}$ ${\displaystyle F}$ ${\displaystyle I}$ ${\displaystyle F}$ ${\displaystyle [\![{\mathcal {A}}]\!](\varepsilon )}$

• La función de transición se puede dar como una matriz con entradas para cada uno , en lugar de un conjunto de transiciones. La entrada de la matriz en es la suma de todas las transiciones etiquetadas . ^{[2] [11]} ${\displaystyle \Delta _{\sigma }\in R^{Q\times Q}}$ ${\displaystyle R}$ ${\displaystyle \sigma }$ ${\displaystyle (q,q')}$ ${\displaystyle (q,\sigma ,q')}$

• Algunos autores se limitan a semirings específicos, como o , particularmente cuando estudian resultados de decidibilidad. ^{[1] [9] [4]} ${\displaystyle \mathbb {N} }$ ${\displaystyle \mathbb {Z} }$

Ver también

• autómata probabilístico
• Autómata finito no determinista
• transductor de estado finito
• Serie racional
• semirremolque
• Anillo de matriz
• autómata cronometrado
• Lógica difusa
• cadena de markov

Referencias

1. Chatterjee, Krishnendu; Henzinger, Thomas A.; Otop, enero (2016). "Autómatas de monitorización cuantitativa". En Rival, Xavier (ed.). Análisis estático . Apuntes de conferencias sobre informática. vol. 9837. Berlín, Heidelberg: Springer. págs. 23–38. doi :10.1007/978-3-662-53413-7_2. ISBN 978-3-662-53413-7.
2. Droste, Manfred; Kuich, Werner; Vogler, Heiko, eds. (2009). Manual de autómatas ponderados. Monografías en Informática Teórica. Una serie EATCS. Código Bib : 2009hwa..libro.....D. doi :10.1007/978-3-642-01492-5. ISBN 978-3-642-01491-8. ISSN  1431-2654.Capítulos 1-4, páginas 3-26, 69-71, 122-126.
3. Chiang, David. "Autómatas ponderados" (PDF) . Procesamiento del lenguaje natural (CSE 40657/60657), notas del curso, otoño de 2019 . Consultado el 9 de noviembre de 2021 .
4. Schützenberger, diputado (1 de septiembre de 1961). "Sobre la definición de familia de autómatas". Información y Control . 4 (2): 245–270. doi :10.1016/S0019-9958(61)80020-X. ISSN  0019-9958.
5. Chatterjee, Krishnendu; Henzinger, Thomas A.; Otop, enero (14 de diciembre de 2017). "Autómatas ponderados anidados". Transacciones ACM sobre lógica computacional . 18 (4): 31:1–31:44. arXiv : 1504.06117 . doi :10.1145/3152769. ISSN  1529-3785. S2CID  15070803.
6. Alur, Rajeev; D'Antoni, Loris; Deshmukh, Jyotirmoy; Raghothaman, Mukund; Yuan, Yifei (2013). "Autómatas de registro de costos y funciones regulares". 2013 28º Simposio anual ACM/IEEE sobre lógica en informática. págs. 13-22. doi :10.1109/LICS.2013.65. ISBN 978-1-4799-0413-6. S2CID  1286659.
7. Mohri, Mehryar; Pereira, Fernando; Riley, Michael (1 de enero de 2002). "Transductores ponderados de estados finitos en reconocimiento de voz". Habla y lenguaje informático . 16 (1): 69–88. doi :10.1006/csla.2001.0184. ISSN  0885-2308.
8. Balle, Borja; Mohri, Mehryar (2015). "Aprendizaje de autómatas ponderados". En Maletti, Andreas (ed.). Informática Algebraica . Apuntes de conferencias sobre informática. vol. 9270. Cham: Editorial Internacional Springer. págs. 1–21. doi :10.1007/978-3-319-23021-4_1. ISBN 978-3-319-23021-4.
9. Almagor, Shaull; Bóker, Udi; Kupferman, Orna (2011). "¿Qué es lo que se puede decidir acerca de los autómatas ponderados?". En Bultan, Tevfik; Hsiung, Pao-Ann (eds.). Tecnología Automatizada para Verificación y Análisis . Apuntes de conferencias sobre informática. vol. 6996. Berlín, Heidelberg: Springer. págs. 482–491. doi :10.1007/978-3-642-24372-1_37. ISBN 978-3-642-24372-1. S2CID  10159261.
10. Mohri, Mehryar (2009), Droste, Manfred; Kuich, Werner; Vogler, Heiko (eds.), "Algoritmos de autómatas ponderados", Manual de autómatas ponderados , Monografías de informática teórica. Una serie EATCS, Berlín, Heidelberg: Springer, págs. 213–254, Bibcode :2009hwa..book..213M, doi :10.1007/978-3-642-01492-5_6, ISBN 978-3-642-01492-5, recuperado el 11 de noviembre de 2021
11. Droste, Manfred; Gastín, Paul (21 de junio de 2007). "Autómatas ponderados y lógicas ponderadas". Informática Teórica . Autómatas, Lenguajes y Programación. 380 (1): 69–86. doi : 10.1016/j.tcs.2007.02.055 . ISSN  0304-3975.