0_mafw3hh31nvg5pel-algoritmo

Seminário de Lógica Matemática

Local

Sala 6.2.33, CIÊNCIAS ULisboa

Eventos•12 Janeiro, 2026, 15:00 - 16:00

Bisimilaridade gramatical simples, com uma aplicação à equivalência de tipo de sessão

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).

Comunicados

Trajetórias de Descoberta: Inês Fragata, a bióloga que estuda como as espécies evoluem em conjunto.