Palestra: Topological graphs and the Four Color Theorem

 

Durante a visita da Profª. Daniele Nantes ao Grupo de Estrututras Formais, Fundamentos e Aplicações (EFFA), será ministrada uma palestra sobre um trabalho desenvolvido sob sua supervisão no Grupo de Teoria da Computação (GTC/UnB).

 

Título: Topological graphs and the Four Color Theorem

Palestrante: Daniele Nantes (MAT - UnB)

 

Resumo: λ-terms can be syntactically represented in different ways than the usual term strings; for example, one can use combinators, string diagrams and for the linear case Zeilberger's trivalent maps. The main purpose of this paper is to study the relation between arbitrary λ-terms and maps over orientable surfaces contained in ℝ³. For this reason,  topological graphs are introduced. These graphs include free-edges and hyper-edges to represent, respectively, free and multiple occurrences of variables. Arbitrary λ-terms without clashes are represented by a subclass of these graphs, called ω-graphs, that include trivalent maps. A translation from λ-terms into topological graphs is given. The converse of the translation provides a decomposition algorithm that outputs a λ-term in the class of α-equivalent terms associated to each topological graph given as input. This translation provides different names for free-variables.  As an application in graph theory, a version of the Four Color Theorem for ω-graphs, which are not necessarily planar, is presented  extending in this manner a previous result restricted to a subclass of trivalent maps.

Bio: Daniele Nantes fez doutorado em matemática na Universidade de Brasília, com intercâmbio científico de um ano no Departamento de Informática da  universidade King's College London, em temas relacionados a métodos formais, provadores de teoremas e análise lógica de segurança de protocolos criptográficos. No pós doutorado, também em matemática, pela Universidade de Brasília/King's College London, abordou temas mais teóricos, como unificação em sistemas nominais. Atualmente, é professora do Departamento de Matemática da Universidade de Brasília, e tem cooperações com a universidade King's College London (Inglaterra) e com o Instituto Bernoulli/Groningen University (Holanda). Com a primeira, faz parte do grupo Software Modelling and Applied Logic (SMAL) com pesquisa em temas relacionados com lógica equacional, análise de segurança  via unificação nominal ou de primeira ordem. Com Bernoulli Institute - Groningen University, sua pesquisa tem se desenvolvido em temas relacionados a comunicação assíncrona multipartida expressa por processos em cálculo pi, com correção analisada via "session types". A professora faz parte do programa de pós-graduação em matemática da Universidade de Brasília, e orienta alunos de mestrado.

 

 

Data: 7 de junho (sexta-feira)

Horário: 14h15

 

Local:  Miniauditório Luiz Palacin

Faculdade de História