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.
fonte
Respostas:
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.
fonte