¿Reducciones para idiomas regulares?

Question

La razón acerca de si un idioma es R, RE, o co-RE, podemos utilizar muchos-una reducción de mostrar cómo la dificultad (R, RE, o co-RE-ness) de una lengua influye en la dificultad de la otra. La razón acerca de si un idioma es en P, NP, o co-NP, podemos utilizar el polinomio de tiempo de muchos-una reducción de mostrar cómo la dificultad (P, NP, o co-NP-ness) de una lengua influye en la dificultad de la otra.

Es que hay un tipo similar de reducción se puede utilizar para regular idiomas? Por ejemplo, ¿hay algún tipo de reducción de la $\le_R$ que si $L_1 \le_R L_2$ $L_2$ es regular, a continuación, $L_1$ es regular? Claramente podemos arbitrariamente definir una clase muy específica de las reducciones de tal forma que éste posee propiedad, pero hay un tipo conocido de la reducción con esta propiedad?

Gracias!

Answer 1

Es muy natural el modelo de estado finito de la reducción, es decir, la mayoría de los generales de estado finito transductor -- una entrada de cinta de salida de la cinta, no determinista, las transiciones pueden ser etiquetados con diferentes conjuntos regulares (con cadenas vacías), tanto en la entrada y salida lateral. Esto puede ser mostrado equivalente a Henning único símbolo de operaciones, pero permite de manera mucho más intuitiva reducciones, aún en el estado finito reino. La ambigüedad Henning habla de que es sólo el no-determinismo.

Usted puede incluso permitir un transductor de tener almacenamiento secundario (como una Máquina de Turing, pushdown autómatas, etc) siempre hay una constante y uniforme límite en el tamaño del almacenamiento secundario.

Tomando pasos adicionales, puede utilizar transformaciones que hacer cálculos arbitrarios, pero una vez más demuestran que el tamaño de la memoria necesaria sobre todos los insumos es uniformemente acotada, es decir, hay un $k$, dependiendo de la entrada que limita el tamaño de la memoria utilizada. Por lo tanto usted puede utilizar el pseudo-código, Java o lo que sea formalismo te gusta, incluidas las que se bifurcan, que es, el no-determinismo, siempre y cuando usted tiene:

• uno de entrada y uno de salida de la cinta/stream
• ambas corrientes se procesan en un solo paso
• total de memoria es uniformemente acotada en todos los tenedores/subprocesos

En otras palabras, usted no tiene que modelo de estado finito de transformaciones con las transiciones en un número finito de gráfico, que es muy frágil y meticuloso modelo de programación. Usted puede utilizar cualquier conveniente la programación de formalismo o con cualquier modelo de estructuración de la memoria que te gusta, siempre que cumplan con los criterios.

De hecho, propongo que, como en una especie de estado finito equivalente de Turing de la Iglesia de la tesis. No es tan nítida como la de Turing de la Iglesia de la Tesis en el mundo de las funciones recursivas, pero muy útil.

Answer 2

En general, para las reducciones de ser un razonamiento concepto, tenemos que exigir que la función de reducción es bastante fácil de calcular que se puede hacer dentro de la misma las limitaciones de recursos como la complejidad de la clase que estamos en última instancia de interesado. Porque la clase de regular idiomas corresponden a la muy débil modelo computacional de estado finito máquinas, cualquier permitido reducciones tendrían que ser igual de débil.

Más precisamente, tendríamos que considerar la posibilidad de reducciones que puede ser expresado como máquinas de estado finito en sí: algo así como una máquina con un estado dibujado a partir de un conjunto finito, donde cada transición (determinado por el estado actual y el escaneado de símbolo de entrada) puede ser para pasar a la siguiente símbolo de entrada o salida de un resultado determinado símbolo.

Otra forma de expresar estas transformaciones es que son las funciones que se pueden programar utilizando sólo un número finito de variables globales de cada uno de los cuales tiene un valor finito, con un "leer un símbolo" comando "imprimir un símbolo" de comandos, y un conjunto básico de estructuras de control (if, ir, mientras que, interruptor, do-while, y no recursivo subrutinas).

Argumentando a través de tales reducciones claramente el trabajo, pero ya que son tan restringido, creo que será igual de duro para convencer a sí mismo que la reducción de uno tiene en mente es admisible como iba a ser para argumentar a partir de los primeros principios que la inicial del lenguaje es regular.

Esto podría ser diferente si hubiera una forma más natural de modelo para el FSM transformaciones -- tal vez algún tipo de salida-anotado expresiones regulares. Pero no me queda claro exactamente que iba a funcionar, dado que las expresiones regulares pueden ser ambiguos. Tal vez hablar de "uno-muchos reducciones" podría hacer el trabajo, sin embargo.

Answer 3

La importante propiedad de que las garantías de que esas reducciones sentido es la composición: un polinomio de la reducción de tiempo de las obras debido a la composición de un P/NP/co-NP máquina de Turing con una P de la máquina es de nuevo un P/NP/co-NP máquina.

Podemos definir la composición de autómatas de estado finito: ver Wikipedia en transductores de estados finitos. A continuación, $L_1\le_R L_2$ fib no es un estado finito transductor de asignación de palabras a partir de las $L_1$ a las palabras de $L_2$ y las palabras de $\Sigma_1^*\setminus L_1$ a las palabras de $\Sigma_2^*\setminus L_2$. Esta reducción se adapte a sus necesidades.

Por supuesto, usted puede hacer cosas similares con todos los otros tipos de autómatas, o en realidad cualquier cosa en la que puede definir la composición. Para la composición de existir, debe ser capaz de representar las funciones de las palabras, es por ello que se necesita para trabajar con transductores en lugar de los clásicos autómatas finitos.