Categoria de grafos parciais com homomorfismos totais teoria e aplicações

Abstract

O conceito de parcialidade e importante em diversas áreas como a Matemática e a Ciência da Computação; ele pode ser utilizado, por exemplo, para expressar computações que não terminam e para definir funções recursivas parciais. Com rela cão a grafos, categorias de homomorfismos parciais são comuns (por exemplo, em gramáticas de grafos com a técnica de single-pushout). Este trabalho propõe uma abordagem diferente: a parcialidade é usada na estrutura interna dos objetos (não nos morfismos).Istoéfeito utilizando uma extensão do conceito de Categoria das Setas, chamada de Categoria das Setas Parciais. E definida entãoa categoria Grp de grafos parciais(tais que arcos podem possuir ou não vértices de origem e/ou destino) e homomorfismos totais.A generalização deste modelo resulta em categorias de grafos parciais internos.Émostrado que Grp é bicompleta e, se C é um topos, a categoria dos grafos parciais internos a C é cocompleta. Grafos parciais podem ser utilizados para definir modelos computacionais tais como autômatos. Uma categoria de Autômatos Parciais, denominada Autp, é construída a partir da categoria de Grafos Parciais. Usando uma extensão de composição de spans de grafos para autômatos, chamada de Composição de Transições, e possível definir as computações de autômatos. Brevemente, uma composição de transi cões de dois autômatos parciais resulta em um autômato parcial onde cada transição representa um caminho de tamanho dois (entre vértices), tal que a primeira metade é uma transição do primeiro autômato e a segunda metade é uma transição do segundo. É possível compor um autômato consigo mesmo diversas vezes; no caso de n sucessivas composições de transições, pode-se obter as palavras da linguagem aceita pelo autômato que necessitam de n+1 passos de computação nos arcos que não possuem origem e nem destino definidos do autômato parcial resultante.