Trabalho de Formatura Supervisionado - 2004

Proposta inicial para monografia

Aluno: Fabiano Mitsuo Sato

Orientadora: Profa. Nami Kobayashi

Tipo de trabalho: Iniciação Científica

Linguagens e autômatos bidimensionais

Introdução

Uma palavra bidimensional, ou figura (picture), é definida informalmente como uma matriz de símbolos tomados de um alfabeto finito. A um conjunto de figuras, dá-se o nome linguagem bidimensional.

Diversos modelos formais para reconhecer ou gerar objetos bidimensionais foram propostos e estão descritos na literatura. Essas abordagens foram motivadas por problemas relacionados a reconhecimento de padrões, processamento de imagens, autômatos celulares e modelos de computação paralela.

Entre as principais, destacam-se: expressões regulares, autômatos finitos, gramáticas, fórmulas lógicas e tiling systems.

Estudos já realizados mostram que as classes de linguagens bidimensionais descritas por cada uma das abordagens não mantêm todas as propriedades das linguagens unidimensionais.

Os principais textos sobre o assunto que pretendemos estudar estão nas referências.

Objetivos

O objetivo do trabalho é estudar as diferentes abordagens existentes na literatura para as linguagens bidimensionais, bem como as particularidades de cada uma delas e suas aplicações.

Eventualmente, poderemos escolher uma aplicação para estudá-la mais detalhadamente e fazer uma implementação.

Atividades já realizadas

Iniciamos a leitura dos artigos 3 e 4 da referência.

Cronograma de atividades para o segundo semestre

-julho, agosto, setembro: estudo principalmente dos artigos citados nas referências e de outros artigos relacionados; escolha de uma aplicação para possível implementação.

-setembro, outubro: implementação.

-outubro, novembro: conclusão da monografia.

Estrutura esperada da monografia

1. Resumo
2. Primeira parte
   1. Introdução
   2. Objetivos do estudo
   3. Metodologia
   4. Tópicos estudados
   5. Conclusão
   6. Referências
3. Segunda parte
   1. Desafios e frustrações
   2. Disciplinas mais relevantes do BCC
   3. Interação com o orientador
   4. Observações finais
   5. Como aprimoraria meus conhecimentos para continuar na área

Referências

1. Giammarresi, D.; Restivo, A. Recognizable picture languages. International Journal Pattern Recognition and Artificial Intelligence, Vol.6, págs.241-256. 1992.

2. Giammarresi, D.; Restivo, A. Two-dimensional finite state recognizability. Fundamenta Informaticae, págs.399-422. 1996.

3. Giammarresi, D.; Restivo, A. Two-Dimensional Languages. Handbook of Formal Languages, Volume III, págs.215-268. Springer Verlag, 1997.

4. Inoue, K.; Takanami, I. A Survey of two-dimensional automata theory. Lecture Notes in Computer Science 381, págs.72-91. Springer Verlag, 1990.

5. Inoue, K.; Takanami, I. A Characterization of recognizable picture languages. Lecture Notes in Computer Science 654. Springer Verlag, 1993.

6. Latteux, M.; Simplot, D. Simplot Recognizable Picture Languages and Domino Tiling. Theoretical Computer Science, 178, 1-2, págs.275-284, 1997.

7. Matz, O. Regular expressions and Context-free Grammars for picture languages. Lecture Notes in Computer Science 1200, págs.283-294. Springer Verlag, 1997.

8. Matz, O. On Piecewise Testable, Starfree and Recognizable Picture Languages. Lecture Notes in Computer Science 1378, págs.203-210. Springer Verlag, 1998.