A CEMS.UL convida para a participação na palestra de apresentação de um algoritmo para decidir a bisimilaridade de gramáticas simples cuja complexidade é polinomial na valorização da gramática (seminorma máxima entre as regras de produção).
Como a valorização é, no máximo, exponencial no tamanho da gramática, isto resulta num tempo de execução exponencial (simples).
Anteriormente, apenas era conhecido um algoritmo de complexidade exponencial dupla.
Como aplicação, fornecemos uma conversão de tipos de sessão livres de contexto para gramáticas simples cuja valorização é linear no tamanho do tipo. Desta forma, fornecemos o primeiro algoritmo de tempo polinomial para decidir a equivalência de tipos de sessão livres de contexto.
Apresentação por Diogo Poças (Instituto Superior Técnico).