É claro que alguns resultados de complexidade podem entrar em colapso para idiomas unários, mas eu me pergunto se existe em algum lugar uma pesquisa resumindo os resultados conhecidos nesse caso: uma espécie de zoológico de complexidade para idiomas unários. Você saberia de tal referência?
cc.complexity-theory
reference-request
big-list
J.-E. PIN
fonte
fonte
Respostas:
Ainda não existe uma referência no estilo zoológico, mas uma recente pesquisa teórica de autômatos de Giovanni Pighizzini foi útil para mim, especialmente os slides de sua palestra.
fonte
Uma pergunta interessante sobre classes de complexidade em um alfabeto unário que não está nas referências acima é a força da classe #P 1 da Valiant , a classe de contagem de problemas em um alfabeto unário (consulte http://epubs.siam.org/doi/ abs / 10.1137 / 0208032 ). Não se sabe muito sobre seu poder, embora tenha problemas naturais completos e, como linguagens unárias, possua circuitos de tamanho polinomial.
fonte