Dado un NFA y su DFA equivalente que resulta de la determinación total de (usando la construcción del conjunto de potencia, por ejemplo), las siguientes propiedades se mantienen para , y para cualquier palabra :
- lee w en tiempo de ejecución como máximo O ( | w | . | N | 2 ) .
- lee w en tiempo de ejecución como máximo O ( | w | ) y su tamaño puede ser O ( 2 | N | ) (en la cantidad de estados necesarios para representar D ).
Me pregunto si existe algún algoritmo de determinación parcial que garantice una compensación entre el tamaño del resultado y el tiempo de ejecución.
Por ejemplo, este algoritmo de determinación parcial podría convertir un NFA en un autómata parcialmente determinista modo que D ′ garantiza que la palabra w se lee en O ( | w | . | N | x ) donde 0 ≤ x ≤ 2 sin exceder el tamaño | D ′ | ≤ 2 f ( x ) donde f ( x ) es una función decreciente continua definida en el rango tal que f ( 0 ) = | N | y f ( 2 ) = l o g | N | .
No encontré ningún método para determinar parcialmente un NFA de esa manera. En todos los documentos: se evita cualquier determinación porque el NFA es demasiado grande, cualquiera de las determinaciones está completa y el NFA se convierte en un DFA (con una posible explosión exponencial). No hay compromiso ...
Realmente agradecería cualquier referencia o respuesta con respecto a este problema. Muchas gracias Luz.
Respuestas:
El artículo [HP06] está en el espíritu de su idea, aunque en una dirección diferente, en el contexto de infinitas palabras. Se puede adaptar más fácilmente a palabras finitas.
En la construcción del conjunto de potencia, simultáneamente hacemos un seguimiento de todas las ejecuciones posibles del autómata state, moviendo n tokens. Pero podríamos decidir seguir solo k < n carreras y hacer una construcción parcial del conjunto de potencia. En general, esto producirá un autómata no determinista, que en realidad no es más útil que el original.norte norte k < n
Pero podría ser que construir funcione con una determinada estrategia determinista siempre es suficiente para obtener una aceptable, si existe. Piense, por ejemplo, en un gran autómata donde el único no determinismo es adivinar si la última letra es una a o una b , y luego bifurcarse hacia dos autómatas deterministas. Luego son suficientes dos tokens, y funciona una construcción de 2 conjuntos de potencia, donde los subconjuntos tienen un tamaño máximo de 2 , es decir, el autómata resultante tienek una si 2 2 estadosn ( n + 1 )2
Podemos definir el "ancho" de un autómata no determinista como el número de tokens necesarios para construir determinísticamente una ejecución de aceptación. La construcción del conjunto de potencia realmente supone que estamos en el peor de los casos, es decir, ancho igual al número de estados. El caso donde el ancho es corresponde a la noción de autómata bueno para juegos (GFG), introducido en [HP06], y estudiado en [BKKS13, KS15].1
Tenemos que un NFA tiene un ancho máximo de si y solo si su construcción k- powerset es GFG. En palabras finitas, está en P detectar si un autómata es GFG, y en este caso en realidad significa que es determinista con algunas transiciones inútiles adicionales. Esto significa que podríamos incrementar k hasta que la construcción resultante de k- powerset sea GFG, pode las transiciones inútiles y obtengamos un autómata determinista. Esto corresponde a enfatizar el ahorro de espacio, ya que en lugar de construir el gran autómata determinista y luego minimizarlo, tratamos de abordarlo "desde abajo", con la esperanza de que no tengamos que hacer la construcción completa del conjunto de potencia.k k k k
[HP06] Resolviendo juegos sin determinación , Henzinger, Piterman, en CSL 2006
[BKKS13] No determinismo en presencia de un futuro diverso o desconocido , Boker, Kuperberg, Kupferman, Skrzypczak, en ICALP 2013
[KS15] Sobre la determinación de autómatas buenos para juegos , Kuperberg, Skrzypczak, en ICALP 2015
fuente