Subsemigrupos automáticos

A noção de grupo automático foi recentemente generalizada para semigrupos, obtendo-se uma classe natural e com propriedades computacionais interessantes. Uma estrutura automática para um semigrupo é constituída por diversos autómatos os quais em particular nos dão um algoritmo para resolver o problema da palavra em tempo quadrático. Nesta apresentação vamos considerar subsemigrupos de semigrupos automáticos que também são automáticos. Em particular vamos mostrar como se podem obter estruturas automáticas para subsemigrupos de produtos livres a partir do conjunto gerador. Como consequência vamos ver que, qualquer subsemigrupo finitamente gerado de um produto livre em que cada factor é finito ou livre, é automático. Em particular todos os subsemigrupos finitamente gerados de produtos livres de semigrupos monogénicos são automáticos.