alfa-ALN: Autômatos Lineares Não-Determinísticos com alfa-Transições

Autores

  • Benjamin Callejas Bedregal

DOI:

https://doi.org/10.5540/tema.2011.012.03.0171

Resumo

Neste trabalho introduziremos a classe dos autômatos lineares não-determinísticos com alfa-transições. Baseados numa nova forma normal para gramáticas lineares, provamos que a classe de linguagens aceita por este tipo de autômato é exatamente a classe das linguagens lineares. Mostramos ainda que, análogo ao que ocorre com os autômatos finitos e com os autômatos com pilhas, a existência das alfa-transições em um autômato linear não-determinístico não significa que não possa ser definido um autômato linear não-determinístico sem alfa-transições que reconheça a mesma linguagem. Ou seja, as alfa-transições não aumentam o poder de aceitação destes autômatos e portanto podem ser dispensadas do modelo. Finalmente, apresentamos uma aplicação destes autômatos no contexto de bioinformática.

Biografia do Autor

Benjamin Callejas Bedregal

Graduado em engenharia da computacao pela universidad de Tarapacá, Arica-Chile, no ano 1986. Mestre em Informatica pela UFPE, em 1987 e doutor em Ciencia da Computacao pela mesma universidade em 1996. Desde 1996 é professor (primeiro como visitante e a partir de 1999 do quadro permanente) da UFRN e lotado no DIMAp. Tem orientado diversos alunos de mestrado e doutorado e é bolsista produtividade do CNPq desde 2007.  Atualmente trabalho na área de lógica fuzzy, matematica intervalar e teoria da computacao, entre outras coisas.

Referências

B. Albert, “Molecular Biology of the Cell”, 4a ed., Garland Science, New York, 2002.

J.A. Anderson, “Automata Theory with Modern Applications”, Cambridge University Press, Cambridge, 2006.

J.M. Autebert, J. Berstel, L. Boasson, Context-free languages and pushdown automata, em “Handbook of Formal Languages, Vol. 1: Word, Language, Grammar” (G. Rozenberg, ed.), pp. 111–174, Springer-Verlag, New York, 1997.

B.C. Bedregal, Pushdown automata free of explicit nondeterminism and an infinite hierarchy of context-free languages, Fundamenta Informaticae, 81 (2007), 367–377.

B.C. Bedregal, B.M. Acióly, A. Lyra, “Introdução à Teoria da Computação: Linguagens Formais, Autômatos e Computabilidade”, Editora UnP, Natal, 2010.

B.C. Bedregal, A.C.R. Costa, G.P. Dimuro, Fuzzy rule-based hand gesture recognition, IFIP Int. Fed. for Information Processing, 217, pp. 285–294, 2006.

J. Carroll, D. Long, “Theory of Finite Automaton With an Introduction to Formal Languages”, Prentice-Hall, Englewood Cliffs, New Jersey, 1989.

D.I.A. Cohen, “Introduction to Computer Theory” (Revised printing), John Wiley & Sons, New York, 1991.

C. De La Higuera, J. Oncina, Inferring Deterministic Linear Languages, em “Proc. of the 15th Annual Conference on Computational Learning Theory (DLT)”(J. Kivinen, R.H. Sloan, eds.), Lectures Notes in Computer Science, Vol. 2375, pp. 185–200, Springer-Verlag, Berlim, 2002.

H.T.A. De Sena, Algumas Evidencias Computacionais da Infinitude dos Números Primos Palindrômicos e Generalizações Destes. Trabalho de Conclusão de Curso. (Graduação em Bach. em Ciências da Computação), Universidade Federal do Rio Grande do Norte, Natal, 2008. (Disponível em http://www.dimap.ufrn.br/∼bedregal/students.html)

Downloads

Publicado

2011-01-08

Como Citar

Bedregal, B. C. (2011). alfa-ALN: Autômatos Lineares Não-Determinísticos com alfa-Transições. Trends in Computational and Applied Mathematics, 12(3), 171–182. https://doi.org/10.5540/tema.2011.012.03.0171

Edição

v. 12 n. 3 (2011)

Seção

Artigo Original

Licença

Direitos Autorais

Autores de artigos publicados no periódico Trends in Computational and Applied Mathematics mantêm os direitos autorais de seus trabalhos. O periódico utiliza a Atribuição Creative Commons (CC-BY) nos artigos publicados. Os autores concedem ao periódico o direito de primeira publicação.

Propriedade Intelectual e Termos de uso

O conteúdo dos artigos é de responsabilidade exclusiva dos autores. O periódico utiliza a Atribuição Creative Commons (CC-BY) nos artigos publicados. Esta licença permite que os artigos publicados sejam reutilizados sem permissão para qualquer finalidade, desde que o trabalho original seja corretamente citado.

O periódico encoraja os Autores a autoarquivar seus manuscritos aceitos, publicando-os em blogs pessoais, repositórios institucionais e mídias sociais acadêmicas, bem como postando-os em suas mídias sociais pessoais, desde que seja incluída a citação completa à versão do website da revista.