Hierarquias em idiomas regulares

14

Existe alguma hierarquia "legal" conhecida (pode ser finito) dentro da classe de idiomas regulares ? Por legal aqui, as classes em cada hierarquia capturam expressividade / poder / complexidade diferentes. Além disso, a composição de cada classe é "bem" demonstrada por alguns elementos (diferentemente do problema de altura da estrela que pode ser problemático).L0L1L2L

Obrigado!

raja.damanik
fonte
3
Uma hierarquia natural é aquela induzida pelo número de estados.
Marzio De Biasi
9
A canônica é a hierarquia de profundidade dos pontos, caracterizada pela alternância do quantificador em FO (<). Basicamente, a alternância (quantificação booleana) de quantificador fornece classes e hierarquias robustas.
Michaël Cadilhac
Aqueles tanto parece perfeitamente boas respostas para mim ...
Joshua Grochow
4
Há também a altura da estrela .
Reinierpost
O que você quer dizer com hierarquia "legal" versus "a associação de cada classe é" bem "demonstrada por alguns elementos"? ". Fora dos idiomas regulares, a hierarquia polinomial parece ser considerada uma hierarquia legal, apesar do fato de a associação e mesmo a existência de uma hierarquia real está ainda a ser provado.
J.-E. Pin

Respostas:

15

Aqui está uma lista de várias hierarquias de interesse, algumas das quais já foram mencionadas em outras respostas.

  1. Hierarquias de concatenação

Uma linguagem é um produto marcado de L 0 , L 1 , , L n se L = L 0 a 1 L 1a n L n para algumas letras a 1 , , a n . As hierarquias de concatenação são definidas alternando operações booleanas e operações polinomiais (= união e produto marcado). A hierarquia de Straubing-Thérien (ponto de partida { , A } )LL0,L1,,LnL=L0a1L1anLna1,,an{,A}) e a hierarquia de profundidade de ponto (ponto inicial é desse tipo, mas você pode usar outros pontos de partida, principalmente os idiomas do grupo (idiomas aceitos por um autômato de permutação).{,{1},A+,A}) 

  1. Hierarquias de altura em estrela

O padrão geral é contar o número mínimo de estrelas aninhadas necessárias para expressar um idioma a partir das letras, mas várias variantes são possíveis, dependendo dos operadores básicos permitidos. Se você permite somente união e produto, define a altura da estrela restrita, se você permite união, complemento e produto, define a altura da estrela (generalizada) e se permite união, interseção e produto, define a altura da estrela intermediária . Existem idiomas de estrela restrita para cada n e efetivamente podem computar efetivamente a altura da estrela de um determinado idioma regular. Para a altura da estrela, a altura da estrela 0 é decidível ( idiomas sem estrelas ), existem idiomas da altura da estrela 1nn01, mas nenhum idioma da altura da estrela é conhecido! Nenhum resultado é conhecido na altura intermediária da estrela. Veja este documento para uma visão geral.2

  1. Hierarquias lógicas

Há muitos deles, mas um dos mais importante é o chamado hierarquia. Uma fórmula é dito ser um Σ n -Fórmula se que é equivalente a uma fórmula da forma de Q ( x 1 , . . . , X k ) φ onde φ é quantificador livre e Q ( x 1 , . . . , X k ) é uma sequência de nΣnΣnQ(x1,...,xk)φφQ(x1,...,xk)nblocos de quantificadores de modo a que o primeiro bloco contém apenas quantificadores existenciais (nota que este primeiro bloco pode estar vazia), o segundo bloco quantificadores universais, etc. Da mesma forma, se é formado de n alternando blocos de quantificadores começando com um bloco de quantificadores universais (que novamente pode estar vazio), dizemos que φ é um Π n -Fórmula. Designam por Σ n (resp. Π n ) a classe de linguagens que podem ser definidas por uma Σ n -Fórmula (resp. Um ΠQ(x1,...,xk)nφΠnΣnΠnΣnfórmula n ) e por B Σ n o fechamento booleano daslínguas Σ n . Finalmente, deixe Δ n = Σ nΠ n . A imagem geral se parece com essa. É claro que é necessário especificar a assinatura. Geralmente, há um predicado um para cada letra (e um x significa que existe uma carta um na posição X na palavra). Então pode-se adicionar um símbolo binário <ΠnBΣnΣnΔn=ΣnΠninsira a descrição da imagem aquiaaxax<(a hierarquia correspondente é a hierarquia Straubing-Thérien) e também um símbolo sucessor (a hierarquia correspondente é a hierarquia de profundidade dos pontos). Outras possibilidades incluem a predicado, a contar modulo n , etc. Veja novamente este papel para uma visão geral.Modn

  1. Hierarquias booleanas

O padrão geral (que não é específico para idiomas regulares) é devido a Hausdorff. Seja uma classe de idiomas que contém o conjunto vazio e o conjunto completo e fechado sob interseção finita e união finita. Deixe- D n ( L ) ser a classe de todas as línguas de forma X = X 1 - X 2 + ± X n em que X iL e X 1X 2X 3X n . Desde aLDn(L)

X=X1-X2+±Xn
XEueuX1X2X3Xn, as classes D n ( L ) definir uma hierarquia e a sua união é o encerramento booleano de L . Novamente, vários pontos de partida são possíveis.Dn(eu)Dn+1(eu)Dn(eu)eu
  1. Complexidade do grupo

Um resultado de Krohn-Rhodes (1966) afirma que todo DFA pode ser simulado por uma cascata de autômatos de redefinição (também chamados de flip-flop) e autómatos cujos semigrupos de transição são grupos finitos. A complexidade do grupo de um idioma é o menor número de grupos envolvidos nessa decomposição do DFA mínimo do idioma. Os idiomas de complexidade são exatamente os idiomas sem estrelas e existem idiomas de qualquer complexidade. No entanto, nenhuma caracterização efetiva das linguagens de complexidade 1 é conhecida.0 01

  1. Hierarquias herdadas da complexidade do circuito

O ponto de partida é o belo artigo que mostra em particular que a classe A C 0R e g é decidível. Deixe Um C C ( q ) = { L { 0 , 1 } * | L Um C 0 M O D q } , em que H S D Q = { u { 0 , 1 }[1]UMAC0 0RegUMACC(q)={eu{0 0,1}euUMAC0 0MODq} . Se q divide q , então A C C ( q ) A C C ( q ) . Uma questão interessante é saber se A C C ( q ) R e g é decidível para qualquer 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. Línguas regulares em N C 1 . J. Comput. Sci do sistema 44(1992)[1]NC1

J.-E. PIN
fonte
12

Expandindo o comentário: uma hierarquia natural é a induzida pelo número de estados do DFA.

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

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

Claramente (basta usar estados mortos)LnLn+1

Para mostrar a inclusão adequada , podemos simplesmente escolher o idioma: L n + 1 = { a ii n } L n + 1LnLn+1Ln+1={aiin}Ln+1

Muito informalmente: o DFA (mínimo) que reconhece deve ser uma "cadeia de estados" de comprimento n + 1 : q 0 a q 1 a . . . a q n , F = { q n } e q n a q n ( q n possui um auto-loop). Portanto, n + 1 estados são suficientes para aceitar{aiin}n+1q0aq1a...aqnF={qn}qnaqnqnn+1 . Mas todo caminho aceitante de q 0 até um estado final q f que é estritamente menor que n + 1 deve aceitar alguns a i com i < n que não pertence a L n + 1 , portanto, um DFA com n ou menos estados não pode aceite L n + 1 .Ln+1q0qfn+1aii<nLn+1nLn+1

Marzio De Biasi
fonte
8

Recentemente, deparei-me com este artigo, que pode dar outro exemplo relevante (cf. a última frase do resumo):

Guillaume Bonfante, Florian Deloup: O gênero das línguas regulares.

Resumo: O artigo define e estuda o gênero de autômatos determinísticos de estado finito (FSA) e linguagens regulares. De fato, uma FSA pode ser vista como um gráfico para o qual surge a noção de gênero. Ao mesmo tempo, um FSA tem uma semântica através de sua linguagem subjacente. É então natural estabelecer uma conexão entre as línguas e a noção de gênero. Depois de introduzir e justificar a noção de gênero para linguagens regulares, [...] construímos linguagens regulares de gênero grande arbitrário: a noção de gênero define uma hierarquia apropriada de linguagens regulares.

Damiano Mazza
fonte
5

Existem várias hierarquias naturais para idiomas regulares de palavras infinitas, que transmitem uma noção de "complexidade do idioma", por exemplo:

  • Número de classificações necessárias em um autômato de paridade determinística
  • Hierarquia de Wadge (ou Wagner): complexidade topológica, níveis de .ωω

Essas hierarquias podem ser generalizadas para idiomas regulares de árvores infinitas, para as quais novas hierarquias aparecem, veja, por exemplo, esta resposta .

Denis
fonte