Trees in Coalgebra from Generalized Reachability

Enunciado do Problema
O artigo aborda as propriedades estruturais fundamentais de sistemas baseados em estados modelados como coalgebras. Embora o conceito de alcance (onde cada estado é acessível a partir de um estado inicial) tenha sido bem caracterizado coalgebricamente via propriedades universais (ausência de subcoalgebras próprias) e construções iterativas (união de estados sucessores), uma caracterização coalgebrática correspondente de estrutura de árvore estava ausente. Especificamente, os autores buscam definir quando uma coalgebra é uma "árvore" de forma a generalizar a noção intuitiva da teoria dos grafos: um sistema onde cada estado é alcançável via um caminho único a partir do estado inicial. O desafio reside em lidar com sistemas onde as transições podem ser parciais, não determinísticas ou envolver compartilhamento, e em fornecer uma caracterização que funcione para uma ampla classe de funtores, incluindo aqueles que não preservam monomorfismos (como o funtor bag).

Metodologia
Os autores empregam uma abordagem categórica baseada em sistemas de fatoração e teoria de coalgebras. Sua metodologia procede através de três etapas principais:

1. Generalização da Minimalidade: Eles primeiro generalizam a noção de "minimalidade" em uma categoria. Indo além da definição clássica onde um objeto minimal possui nenhum subobjeto próprio (exigindo que morfismos sejam isomorfismos), eles introduzem a $M$-minimalidade (Definição 4.1). Um objeto é $M$-minimal se todo morfismo de uma classe $M$ para ele é um epimorfismo fatiado (split epimorphism). Esta generalização permite que $M$ seja a classe de todos os morfismos, não apenas monomorfismos.
2. Conexão com Projetividade e Alcance: Eles estabelecem um elo entre esta minimalidade generalizada e a $M$-projetividade (Teorema 4.7). Eles então instanciam esta teoria na categoria de coalgebras pontuadas para definir o alcance generalizado (Definição 5.1). Uma coalgebra é $M$-alcançável se toda subcoalgebra pontuada de $M$ é um epimorfismo fatiado.
3. Construção Iterativa via Mapas Precisos: Para construir a versão alcançável ou o desenrolamento em árvore de uma coalgebra, os autores utilizam morfismos precisos (Definição 3.1). Diferente de "limites ínfimos" (bases) que dependem de monomorfismos para evitar compartilhamento, mapas precisos garantem que os elementos no codomínio sejam usados exatamente uma vez na definição do mapa. Eles provam que, para funtores analíticos, as fatorações precisas existem e coincidem com limites ínfimos quando restritas a monomorfismos (Proposição 3.27, Corolário 3.22).

Contribuições Principais
O artigo fornece duas caracterizações equivalentes para quando uma coalgebra é uma árvore, espelhando as caracterizações duais de alcance:

• Propriedade Universal (Definição de Árvore): Uma coalgebra pontuada é uma árvore se ela não possui desenrolamentos próprios. Formalmente, uma coalgebra é uma árvore se todo desenrolamento (um homomorfismo de coalgebra pontuada para ela) é um epimorfismo fatiado (Definição 6.1). Isso generaliza a condição de alcance ao permitir que a classe de morfismos $M$ seja a classe de todos os morfismos, em vez de apenas monomorfismos.
• Construção Iterativa (Desenrolamento em Árvore): Os autores apresentam uma construção iterativa (Construção 6.23) que transforma uma coalgebra pontuada arbitrária em uma árvore. Esta construção envolve a tomada do coproduto de níveis, onde cada nível é computado via fatorações precisas do mapa de transição. A coalgebra resultante é o "desenrolamento em árvore" da coalgebra original.
• Unificação: O artigo demonstra que tanto o alcance quanto a propriedade de ser uma árvore são instâncias da mesma noção generalizada de $M$-minimalidade. O alcance corresponde a $M$ sendo uma classe de monomorfismos, enquanto a propriedade de árvore corresponde a $M$ sendo a classe de todos os morfismos.

Resultos
Os autores validam sua teoria recuperando noções esperadas de árvores para vários exemplos padrão:

• Autômatos Determinísticos Parciais: O desenrolamento em árvore corresponde ao "coalgebra de entradas definidas", onde os estados são identificados com as palavras únicas que levam a eles (Lema 6.11, Corolário 6.12).
• Multigrafos (Funtor Bag): Para coalgebras sobre o funtor bag (modelando multigrafos), o desenrolamento em árvore é a "coalgebra de caminhos enraizados". Uma coalgebra bag é uma árvore se, e somente se, existe um caminho único da raiz para cada vértice (Teorema 6.18).
• Funtor Powerset: O artigo destaca uma limitação: para o funtor powerset (modelando grafos simples), a caracterização implica que quase nenhuma coalgebra é uma árvore. Isso ocorre porque o funtor powerset permite "cópia" (ex: $\{x\} = \{x, x\}$), o que impede a existência de mapas precisos para conjuntos não vazios (Proposição 3.3). Consequentemente, árvores neste cenário são triviais (vértice único, sem arestas).

Significância
O artigo reivindica significância ao fornecer um arcabouço teórico unificado que estende a teoria de coalgebras alcançáveis para estruturas de árvore.

• Generalização: Ele generaliza com sucesso o conceito de alcance de sistemas de fatoração próprios (monos) para sistemas de fatoração arbitrários, permitindo o tratamento de estruturas de árvore onde os morfismos não precisam ser injetivos.
• Funtores Analíticos: A construção iterativa mostra-se funcional para todos os funtores de conjunto analíticos (Corolário 3.22), uma classe ampla que inclui funtores polinomiais e o funtor bag, que são centrais para modelar diversos sistemas computacionais.
• Clareza Conceitual: Ao ligar minimalidade à projetividade e fornecer tanto caracterizações universais quanto iterativas, o trabalho oferece uma base categórica robusta para entender o comportamento de tipo árvore em sistemas baseados em estados, distinguindo-o claramente do comportamento de sistemas modelados pelo funtor powerset.

Os autores observam que este trabalho é uma versão estendida de um artigo de conferência, adicionando provas completas e novas generalizações, particularmente a conexão entre minimalidade e projetividade e a análise detalhada de fatorações precisas.