Por que os autômatos com limites lineares não são tão populares quanto outros autômatos?

9

Na minha experiência, linguagens sensíveis ao contexto e autômatos limitados lineares são freqüentemente ignorados ou ignorados nos cursos de teoria da computabilidade e são deixados de fora de alguns livros de texto notáveis, embora os autômatos finitos e pushdown recebam muita atenção. Certamente deve haver uma boa razão para que os LBAs tenham menos foco do que seus colegas?

computability fl.formal-languages automata-theory goric
fonte
Veja esta pergunta: A hierarquia de Chomsky está desatualizada?
Kaveh 27/01
Você poderia elaborar como a pergunta vinculada se relaciona, Kaveh? (Porque eu não acho que o seu tom é útil aqui, mas respostas individuais pode ser)
Raphael
2
@Raphael: As respostas para a pergunta que Kaveh ligou para explicar por que as linguagens sensíveis ao contexto não são consideradas tão importantes quanto antes: em suma, existem outros modelos mais interessantes a serem considerados. (mais)
Tsuyoshi Ito
2
(continuação) O mesmo motivo se aplica aos “autômatos limitados lineares”. É engraçado que eu nunca tinha ouvido falar desse nome. Para mim, elas são apenas máquinas de Turing determinísticas / não determinísticas do espaço O (n), e não consigo entender por que devemos destacar unidades O (n) do espaço (em vez de espaço polinomial ou espaço O (log n) ou qualquer outra coisa), embora deva ter havido uma razão histórica. Além disso, nem a classe DSPACE (O (n)) nem NSPACE (O (n)) são fechadas sob chamadas de sub-rotina .
Tsuyoshi Ito 27/01
11
Tsuyoshi, minha interpretação da pergunta é que FA, PDA e o resto da Hierarquia de Chomsky (pelo seu raciocínio / as respostas são igualmente entediantes) são ensinados, mas o LBA não é.
Raphael

Respostas:

13

NC1

Agora deve ficar bem claro por que estamos interessados ​​nos dois primeiros mais do que no LBA. Os dois primeiros se encaixam naturalmente na definição usual de computação viável. Mas o PSPACE não.

V Vinay
fonte
11
transformar um LBA em PSPACE soa quase como espaço linear é tudo o que você precisa para capturar o PSPACE, o que claramente não pode ser verdade. Então, qual é o meu erro de pensar?
Suresh Venkat
2
@ Suresh: Existem as seguintes conexões. A classe de problemas (NC1-) redutível para idiomas regulares é NC1, a classe de problemas (log-espaço-) redutível para CFL é LogCFL e a classe de problemas (NC1- ou espaço de log-) redutível para LBA é PSPACE. Não tenho certeza se podemos usar a mesma noção de redutibilidade em todos esses três casos.
Tsuyoshi Ito 27/01
AC0
3

Bem, pergunte ao seu professor por que ele fez isso. Eu posso apenas adivinhar.

Eles não são tão interessantes quanto os modelos completos de Turing e o PDA, porque estão no vazio da inutilidade *, eles compartilham, é claro, com seu idioma equivalente: não tão poderoso quanto possível, mas já muito intratável.

Outra razão pode ser que não se saiba tanto (supondo aqui) sobre eles, mas isso pode se resumir a um problema de ovo de galinha.

NLBA=DLBA

(*) exagero deliberado

Rafael
fonte
2

Parece que não apenas o CSG, mas também o CFG ... estão fora de moda atualmente. Acho que hoje em dia os autômatos e o PDA são geralmente considerados nos cursos de teoria da computabilidade / complexidade (se é que existem) e aí eles são incluídos não por si mesmos, mas para introduzir as Máquinas de Turing.

As gramáticas são provavelmente interessantes para a teoria dos compiladores, mas não tanto para que a computabilidade / complexidade seja incluída em um curso de graduação introdutório. Há muitos tópicos que gostaríamos de abordar, mas um curso de um semestre é muito curto e precisamos selecionar e muitos desses tópicos que não podemos abordar devido às restrições de tempo serem muito mais interessantes do que o LBA.

Kaveh
fonte
11
Eu queria que você fosse universalmente verdade! A aula de introdução ao TCS ensinada no meu univ é meio autômato / CFL. Estou ministrando essa aula e os alunos parecem muito longe de se interessar. Essa pode ser outra razão pela qual a CFL / CSL não é mais apresentada: há tópicos muito mais interessantes.
Michaël Cadilhac
11
Bem, a teoria da CS não é apenas complexidade. Em particular, o CFG e os modelos de autômatos relacionados são muito importantes (pelo menos como fundações) em muitos ramos do CS. Um curso introdutório deve prepará-lo para todos os ramos. Desculpe, mas esta resposta cheira a ignorância. Além disso, ele não responde à pergunta.
Raphael
@ Rafael, eu estou falando sobre cursos de teoria da computabilidade / complexidade , que é onde a teoria dos autômatos está sendo pensada nas universidades que conheço agora. Ninguém disse nada sobre os cursos de teoria em geral. Acho que você deveria ler as postagens cuidadosamente antes de acusar outras pessoas de ignorância. Meu post responde à pergunta: por que o LBA não é considerado nos cursos de teoria da computabilidade / complexidade? Essa é a razão, e é por isso que os livros de teoria da computabilidade e da complexidade não incluem muito sobre o LBA, quer você goste ou não.
Kaveh
Então você é privado das razões pessoais de todos os autores e conferencistas do mundo inteiro? Sim, certo. De qualquer forma, observe que a palavra "complexidade" não ocorre na pergunta publicada. Observe também que, pelo comentário da empresa acima e edite, você não respondeu à pergunta. Fato, quer você goste ou não.
Raphael
11
@Raphael, você ainda não lê atentamente e continua a interpretar o que eu escrevo da maneira que você preferir, parece-me que você só quer argumentar, acho que meu ponto é claro o suficiente, portanto, sinta-se à vontade para pensar como quiser. :)
Kaveh 27/01
2

Expressões regulares e CFGs são usados ​​na prática para analisar código (ou seja, linguagens de programação). A razão é que existem algoritmos muito eficientes para analisá-los. Os LBAs, por outro lado, são poderosos demais para serem realmente usados ​​nesse contexto.

Uma origem histórica da teoria dos autômatos é o assunto da construção do compilador. Pelo motivo mencionado acima, apenas linguagens regulares e CFGs são úteis para a construção de compiladores (apesar de as gramáticas atribuíveis não serem realmente CFGs e os algoritmos de análise de CFGs não analisarem toda a classe de CFGs). Os LBAs podem ter sido inventados por Chomsky como um nível intermediário de complexidade entre o mundano e o "inglês". Então, talvez o lugar certo para ensiná-los seja nos cursos de lingüística, e não nos de ciência da computação!

Yuval Filmus
fonte
Como os LBAs são equivalentes à classe bastante natural de gramáticas sensíveis ao contexto, não acho que elas tenham sido inventadas apenas por diversão. ;)
Raphael
@Raphael: Yuval não implicava isso.
Reinierpost