Separation in Automata Theory: algebraic aspects

Pretende-se obter novos resultados para fragmentos da lógica de predicados de primeira ordem, cujos modelos são palavras finitas e infinitas. O projeto visa questões fundamentais motivadas por considerações práticas para a validação de software e circuitos. Desde o trabalho pioneiro de Büchi, Elgot e Trakthenbrot, as ligações entre os mecanismos de descrição lógica e a teoria dos autómatos é a principal ferramenta para a solução de tais problemas. Trabalho preliminar importante é devido ao responsável português, que foi o primeiro a considerar o problema da separação. O colaborador proposto, Marc Zeitoun, tem colaborado com o proponente no desenvolvimento de técnicas de separação e obteve recentemente, em colaboração com Thomas Place, sucessos notáveis na aplicação de tais técnicas à determinação da capacidade expressiva de fragmentos da lógica de predicados de primeira ordem, nomeadamente no que diz respeito a duas alternâncias de quantificadores. Este projeto é parte da colaboração trilateral envolvendo ainda uma equipa liderada na Universidade de Estugarda por Manfred Kufleitner, que tem estudado intensivamente fragmentos da lógica de primeira ordem. Esperamos conseguir combinar as ideias e métodos de cada parceiro para aprofundar o conhecimento em ambas as áreas.

Observações. Este projeto é coordenado com outro projeto bilateral, constituindo uma rede de cooperação envolvendo três países (Alemanha, França e Portugal). O financiamento indicado é o valor atribuído para o primeiro ano.

Duration: 

24months

Start date: 

Thursday, 1 January, 2015

Area / Group: 

Semigroups, Automata and Languages

Members: 

Jorge Almeida
Hossein Shahzamanian
Célia Borlido
Khadijeh Alibabaei

Other members: 

José Carlos Costa

Financial support: 

1 500EUR