Arnaldo Mandel
IME-USP
Sexta-feira, 1 de março de 2002, 15:00
Sala 267, Bloco A, IME-USP
Resumo: Quando é possível substituir uma chamada do grep por uma do fgrep? Um caso particular dessa questão foi motivado pela idéia de aplicar a teoria de Bases de Gröbner não-comutativas ao estudo de álgebras comutativas. Dado um alfabeto X, tem-se naturalmente o monóide (comutativo) dos monômios, e o monóide livre, de palavras. Fixando-se uma ordem nas variáveis, é possível escrever um monômio como palavra em que as letras aparecem em ordem não-decrescente.
Problema: dado um conjunto finito S de monômios, I(S) consiste das palavras correspondentes a todos os múltiplos de membros de S.
Como é S para que exista uma lista finita de palavras tais que I(S) consista de todas as palavras que contem um segmento na lista? Após responder isso, deixaremos a ordem das variáveis variar para ver se a resposta varia. Isso abre alguns problemas combinatórios, e fez um novo NP-completo aparecer.
(trabalho conjunto com Ed Green, VTU)