Jerarquías en idiomas regulares

14

¿Hay alguna jerarquía "agradable" conocida L0L1L2 (puede ser finita) dentro de la clase de lenguajes regulares L ? Por bueno aquí, las clases en cada jerarquía capturan diferente expresividad / poder / complejidad. Además, la membresía de cada clase está "bien" demostrada por algunos elementos (a diferencia del problema de altura de la estrella que puede ser problemático).

¡Gracias!

raja.damanik
fuente
3
Una jerarquía natural es la inducida por el número de estados.
Marzio De Biasi
99
El canónico es la jerarquía de profundidad de puntos, caracterizada por la alternancia del cuantificador en FO (<). Básicamente, la alternancia del cuantificador (cierre booleano de) le brinda clases y jerarquías robustas.
Michaël Cadilhac
Esas dos me parecen respuestas perfectamente buenas ...
Joshua Grochow
44
También hay altura de estrella .
reinierpost
¿Qué quiere decir con una jerarquía "agradable" versus "la membresía de cada clase está" bien "demostrada por algunos elementos"? ". Fuera de los lenguajes regulares, la jerarquía polinómica parece ser considerada una buena jerarquía a pesar de que la membresía y incluso la existencia de una jerarquía real aún no se ha probado.
J.-E. Pin

Respuestas:

15

Aquí hay una lista de varias jerarquías de interés, algunas de las cuales ya se mencionaron en otras respuestas.

  1. Jerarquías de concatenación

Un lenguaje es un producto marcado de L 0 , L 1 , ... , L n si L = L 0 a 1 L 1a n L n para algunas letras a 1 , ... , a n . Las jerarquías de concatenación se definen alternando operaciones booleanas y operaciones polinómicas (= unión y producto marcado). La jerarquía Straubing-Thérien (punto de partida { , A } )LL0,L1,,LnL=L0a1L1anLna1,,an{,A}) y la jerarquía de profundidad de puntos (punto de partida son de este tipo, pero puede tomar otros puntos de partida, especialmente los idiomas de grupo (idiomas aceptados por un autómata de permutación).{,{1},A+,A}) 

  1. Jerarquías de altura de estrella

El patrón general es contar la cantidad mínima de estrellas anidadas necesarias para expresar un idioma a partir de las letras, pero son posibles varias variantes, dependiendo de los operadores básicos que permita. Si solo permite la unión y el producto, define la altura de estrella restringida, si permite la unión, el complemento y el producto, define la altura de estrella (generalizada) y si permite la unión, la intersección y el producto, define la altura de estrella intermedia . Hay idiomas de estrella restringida para cada ny se puede calcular efectivamente la altura de la estrella de un lenguaje regular determinado. Para la altura de estrella, la altura de estrella 0 es decidible ( idiomas libres de estrellas ), existen idiomas de altura de estrella 1nn01, pero no se conoce ningún lenguaje de altura de estrella . No se conoce ningún resultado en la altura de estrella intermedia. Consulte este documento para obtener una descripción general.2

  1. Jerarquías lógicas

Hay muchos de ellos, pero uno de los más importantes es la llamada jerarquía . Una fórmula se dice que es un Σ n fórmula de L si es equivalente a una fórmula de la forma Q ( x 1 , . . . , X k ) φ donde φ es cuantificador libre y Q ( x 1 , . . . , X k ) es una secuencia de nΣnΣnQ(x1,...,xk)φφQ(x1,...,xk)nbloques de cuantificadores de tal manera que el primer bloque contiene sólo cuantificadores existenciales (nota que este primer bloque puede estar vacía), los cuantificadores universales segundo bloque, etc. mismo modo, si se forma de n Alternando bloques de cuantificadores que comienzan con un bloque de cuantificadores universales (que nuevamente podrían estar vacíos), decimos que φ es una fórmula Π n . Denote con Σ n (resp. Π n ) la clase de idiomas que puede definirse mediante una fórmula Σ n (resp. A ΠQ(x1,...,xk)nφΠnΣnΠnΣn fórmula) y por B Σ n el cierre booleano de Σ n- idiomas. Finalmente, dejemos Δ n = Σ nΠ n . La imagen general se ve así. Uno necesita, por supuesto, especificar la firma. Generalmente hay un predicado a para cada letra (y una x significa que hay una letra a en la posición x en la palabra). Entonces uno puede agregar un símbolo binario <ΠnBΣnΣnΔn=ΣnΠnenter image description hereaaxax<(la jerarquía correspondiente es la jerarquía Straubing-Thérien) y también un símbolo sucesor (la jerarquía correspondiente es la jerarquía de profundidad de puntos). Otras posibilidades incluyen un predicado , para contar el módulo n , etc. Consulte nuevamente este documento para obtener una descripción general.Modn

  1. Jerarquías booleanas

El patrón general (que no es específico de los idiomas regulares) se debe a Hausdorff. Sea una clase de idiomas que contiene el conjunto vacío y el conjunto completo, y se cierra bajo intersección finita y unión finita. Sea D n ( L ) la clase de todos los idiomas de la forma X = X 1 - X 2 + ± X n donde X iL y X 1X 2X 3X n . Ya queLDn(L)

X=X1X2+±Xn
XiLX1X2X3Xn, las clases D n ( L ) definen una jerarquía y su unión es el cierre booleano de L . De nuevo, son posibles varios puntos de partida.Dn(L)Dn+1(L)Dn(L)L
  1. Complejidad grupal

Un resultado de Krohn-Rhodes (1966) afirma que cada DFA puede ser simulado por una cascada de autómatas y autómatas de reinicio (también llamados flip-flop) cuyos transiciones en semigrupos son grupos finitos. La complejidad grupal de un lenguaje es el menor número de grupos involucrados en dicha descomposición del mínimo DFA del lenguaje. Los idiomas de complejidad son exactamente los idiomas libres de estrellas y existen idiomas de cualquier complejidad. Sin embargo, no se conoce una caracterización efectiva de los lenguajes de complejidad 1 .01

  1. Jerarquías heredadas de la complejidad del circuito

El punto de partida es el bonito artículo que muestra en particular que la clase A C 0R e g es decidible. Sea A C C ( q ) = { L { 0 , 1 } L A C 0 M O D q } , donde M O D q = { u { 0 , 1 }[1]AC0RegACC(q)={L{0,1}LAC0MODq} . Si q divide q , entonces A C C ( q ) A C C ( q ) . Una pregunta interesante es saber si A C C ( q ) R e g es decidible para cualquier q .MODq={u{0,1}|u|10modq}qqACC(q)ACC(q)ACC(q)Regq

Barrington, David A. Mix; Compton, Kevin; Straubing, Howard; Thérien, Denis. Idiomas regulares en N C 1 . J. Comput. System Sci. 44(1992)[1]NC1

J.-E. Alfiler
fuente
12

Ampliando el comentario: una jerarquía natural es la inducida por el número de estados del DFA.

Podemos definir Ln={L exists an n-states DFA D s.t. L(D)=L}

( , | Q | = n )D={Q,Σ,δ,q0,F}|Q|=n

Claramente (simplemente use estados muertos)LnLn+1

Para mostrar la inclusión adecuada simplemente podemos elegir el idioma: L n + 1 = { a ii n } L n + 1LnLn+1Ln+1={aiin}Ln+1

Muy informalmente: el (mínimo) DFA que reconoce debe ser una "cadena de estado" de longitud n + 1 : q 0 a q 1 a . . . a q n , F = { q n } y q n a q n ( q n tiene un bucle automático). Entonces n + 1 estados son suficientes para aceptar{aiin}n+1q0aq1a...aqnF={qn}qnaqnqnn+1 . Pero cada ruta de aceptación de q 0 a un estado final q f que es estrictamente más corto que n + 1 debe aceptar alguna a i con i < n que no pertenece a L n + 1 , por lo que un DFA con n o menos estados no puede aceptar L n + 1 .Ln+1q0qfn+1aii<nLn+1nLn+1

Marzio De Biasi
fuente
8

Recientemente me encontré con este artículo que puede dar otro ejemplo relevante (cf. la última oración del resumen):

Guillaume Bonfante, Florian Deloup: El género de los idiomas regulares.

Del resumen: el artículo define y estudia el género de los autómatas deterministas de estado finito (FSA) y los lenguajes regulares. De hecho, un FSA puede verse como un gráfico para el cual surge la noción de género. Al mismo tiempo, una FSA tiene una semántica a través de su lenguaje subyacente. Entonces es natural hacer una conexión entre los idiomas y la noción de género. Después de presentar y justificar la noción de género para los idiomas regulares, [...] construimos idiomas regulares de género grande arbitrario: la noción de género define una jerarquía adecuada de idiomas regulares.

Damiano Mazza
fuente
5

Existen varias jerarquías naturales para los idiomas regulares de palabras infinitas, que transmiten una noción de "complejidad del lenguaje", por ejemplo:

  • Número de rangos necesarios en un autómata de paridad determinista
  • ωω

Estas jerarquías se pueden generalizar para lenguajes regulares de árboles infinitos, para los cuales aparecen nuevas jerarquías, vea por ejemplo esta respuesta .

Denis
fuente