Existe um livro / documento de pesquisa descrevendo hierarquias de classe de idioma, propriedades de fechamento, etc.

12

Atualmente, estou fazendo uma pesquisa em Linguagem Formal envolvendo classes de idiomas acima do Regular, mas abaixo do Contexto Livre. Estou olhando para coisas como máquinas multicounter com limite de reversão, máquinas de balcão de pilha única, CFLs determinísticas, etc.

Gostaria de saber se alguém conhece um bom livro ou artigo de pesquisa que descreva as propriedades desses idiomas. A maior parte do que estou vendo é muito obscura ou nova demais para constar no meu livro de Hopcroft-Ullman, até na edição de 1979.

Principalmente, estou procurando quais classes de idiomas estão contidas uma na outra, as propriedades de fechamento dessas linguagens e a decidibilidade de problemas básicos (problemas-F) nessas linguagens.

Alguns exemplos de coisas que eu procuraria nesta referência:

  • Todos os idiomas aceitos pelas máquinas de contadores múltiplos com limite de reversão também são aceitos por máquinas de contador único sem limite de reversão?
  • Os idiomas determinísticos do MultiCounter com limite de reversão são fechados sob a concatenação esquerda e direita?
  • A universalidade é decidível para máquinas de balcão único.

Essas são apenas perguntas exemplares. Tenho muitas outras que surgem no meu dia-a-dia.

Como ponto de partida, tentei traçar quais documentos citam as "Máquinas multicounters com limite de reversão e seus problemas de decisão", de Oscar Ibarra, mas não encontrei muito.

jmite
fonte
3
Crossposted em CS.SE .
Juho 28/05
2
Para uma análise detalhada das máquinas multicounter um estado ver hierarquias e caracterizações de Stateless Multicounter Machines
Marzio De Biasi
2
... e eu acho que um monte de referências / materiais podem ser encontrados em recentes (> 2000) papéis de Ibarra
Marzio De Biasi
2
Você pediu para Oscar Ibarra?
Abuzer Yakaryilmaz
2
@ jmite Não há mal nenhum em tentar :-) Como estudante, sempre recebi uma resposta de um pesquisador quando os enviei por e-mail. Na minha experiência, as pessoas ficam felizes em ajudar alguém que esteja interessado em suas pesquisas.
Juho 31/05

Respostas:

5

Tópicos não padrão, não. E desculpe, não tenho uma visão geral.

No entanto, eu daria uma olhada na tese de doutorado de Klaus Reinhardt para pelo menos uma imagem das várias famílias que moram nessa área. Veja a página 64 para um diagrama do zoológico. Motivado pelas redes de Petri com arcos inibidores, Reinhardt estuda multicounters prioritários com restrições sobre quando fazer zero testes. Não trivial.

A propósito, sua última pergunta de exemplo foi discutida neste fórum pelo usuário Sam Jones. Outra referência de Ibarra.

Hendrik Jan
fonte