Autómata finito autoverificable

En la teoría de autómatas , un autómata finito autoverificador ( SVFA ) es un tipo especial de autómata finito no determinista (NFA) con un tipo simétrico de no determinismo introducido por Hromkovič y Schnitger. ^[1] Generalmente, en el no determinismo autoverificador, cada camino de cálculo concluye con cualquiera de las tres posibles respuestas: sí , no y no sé . Para cada cadena de entrada, no pueden existir dos caminos que den respuestas contradictorias, es decir, no son posibles ambas respuestas sí y no en la misma entrada. Al menos un camino debe dar la respuesta sí o no , y si es sí , la cadena se considera aceptada. Los SVFA aceptan la misma clase de lenguajes que los autómatas finitos deterministas (DFA) y los NFA, pero tienen una complejidad de estado diferente .

Definición formal

Un SVFA se representa formalmente mediante una 6-tupla , A =( Q , Σ, Δ, q ₀ , F _a , F _r ) tal que ( Q , Σ, Δ, q ₀ , F _a ) es un NFA y F _a , F _r son subconjuntos disjuntos de Q . Para cada palabra w = a ₁ a ₂ … a _n , un cálculo es una secuencia de estados r ₀ ,r ₁ , …, r _n , en Q con las siguientes condiciones:

1. r0 = q0_​​
2. r _i+1 ∈ Δ( r _i , a _i+1 ), para i = 0, …, n−1 .

Si r _n ∈ F _a entonces el cálculo es de aceptación, y si r _n ∈ F _r entonces el cálculo es de rechazo. Existe un requisito de que para cada w haya al menos un cálculo de aceptación o al menos un cálculo de rechazo, pero no ambos.

Resultados

Cada DFA es un SVFA, pero no viceversa. Jirásková y Pighizzini ^[2] demostraron que para cada SVFA de n estados, existe un DFA equivalente de estados. Además, para cada entero positivo n , existe un SVFA de n estados tal que el DFA equivalente mínimo tiene exactamente estados. ${\displaystyle g(n)=\Theta (3^{n/3})}$ ${\displaystyle g(n)}$

Jirásková y sus colegas obtuvieron otros resultados sobre la complejidad estatal de SVFA. ^{[3] [4]}

Referencias

1. Hromkovič, Juraj; Schnitger, Georg (2001). "Sobre el poder de Las Vegas para la complejidad de la comunicación unidireccional, los OBDD y los autómatas finitos". Información y computación . 169 (2): 284–296. doi : 10.1006/inco.2001.3040 . ISSN  0890-5401.
2. Jirásková, Galina; Pighizzini, Giovanni (2011). "Simulación óptima de autómatas autoverificantes mediante autómatas deterministas". Información y Computación . 209 (3): 528–535. doi :10.1016/j.ic.2010.11.017. ISSN  0890-5401.
3. Jirásková, Galina (2016). "Automata finito autoverificador y complejidad descriptiva" (PDF) . Complejidad descriptiva de sistemas formales . Apuntes de clase en informática. Vol. 9777. págs. 29–44. doi :10.1007/978-3-319-41114-9_3. ISBN 978-3-319-41113-2. ISSN  0302-9743.
4. Jirásek, Jozef Štefan; Jirásková, Galina; Szabari, Alejandro (2015). "Operaciones sobre autómatas finitos autoverificables". Ciencias de la Computación - Teoría y Aplicaciones . Apuntes de conferencias sobre informática. vol. 9139, págs. 231–261. doi :10.1007/978-3-319-20297-6_16. ISBN 978-3-319-20296-9. ISSN  0302-9743.