Trees in Coalgebra from Generalized Reachability

Probleemstelling
Het artikel behandelt de fundamentele structurele eigenschappen van toestandsgebaseerde systemen die als coalgebren worden gemodelleerd. Hoewel het concept van bereikbaarheid (waarbij elke toestand toegankelijk is vanuit een initiële toestand) via universele eigenschappen (de afwezigheid van de juiste subcoalgebren) en iteratieve constructies (de vereniging van opvolgerstoestanden) goed is gekarakteriseerd binnen de coalgebra, ontbrak een overeenkomstige coalgebraische karakterisering van de boomstructuur. Specifiek zoeken de auteurs naar een definitie van wanneer een coalgebra een "boom" is op een manier die de intuïtieve graaftheoretische notie generaliseert: een systeem waarbij elke toestand via een unieke pad bereikbaar is vanuit de initiële toestand. De uitdaging ligt in het omgaan met systemen waar transities partieel, niet-deterministisch of betrokken kunnen zijn bij delen (sharing), en in het bieden van een karakterisering die werkt voor een brede klasse functoren, inclus\nuit functoren die geen monomorfismen behouden (zoals de bag-functor).

Methodologie
De auteurs hanteren een categorische benadering gebaseerd op factorisatiesystemen en coalgebratheorie. Hun methodologie verloopt via drie hoofdfasen:

1. Generalisatie van Minimaliteit: Zij generaliseren eerst het begrip "minimaliteit" in een categorie. Voorbij de klassieke definitie waarbij een minimaal object geen deugdelijke subobjecten heeft (wat vereist dat morfismen isomorfismen zijn), introduceren zij $M$-minimaliteit (Definitie 4.1). Een object is $M$-minimaal als elke morfisme uit een klasse $M$ naar het object een gesplitst epimorfisme is. Deze generalisatie staat toe dat $M$ de klasse van alle morfismen is, niet alleen de monomorfismen.
2. Verbinding met Projectiviteit en Bereikbaarheid: Zij leggen een verband tussen deze gegeneraliseerde minimaliteit en $M$-projectiviteit (Stelling 4.7). Vervolgens instantiëren zij deze theorie in de categorie van gepunte coalgebren om gegeneraliseerde bereikbaarheid (Definitie 5.1) te definiëren. Een coalgebra is $M$-bereikbaar als elke gepunte $M$-subcoalgebra een gesplitst epimorfisme is.
3. Iteratieve Constructie via Precieze Afbeeldingen: Om de bereikbare of boom-ontrafelde versie van een coalgebra te construeren, maken de auteurs gebruik van precieze morfismen (Definitie 3.1). In tegen tegenstelling tot "kleinste grenzen" (bases), die steunen op monomorfismen om sharing te vermijden, zorgen precieze afbeeldingen ervoor dat elementen in het codomein exact één keer worden gebruikt in de definitie van de afbeelding. Zij bewijzen dat voor analytische functoren precieze factorisaties bestaan en samenvallen met kleinste grenzen wanneer zij worden beperkt tot monomorfismen (Propositie 3.27, Corolarium 3.22).

Belangrijkste Bijdragen
Het artikel biedt twee equivalente karakteriseringen voor wanneer een coalgebra een boom is, wat de duale karakteriseringen van bereikbaarheid weerspiegelt:

• Universele Eigenschap (Boomdefinitie): Een gepunte coalgebra is een boom als deze geen deugdelijke ontrafelingen heeft. Formeel gezien is een coalgebra een boom als elke ontrafeling (een gepunte coalgebramorfisme naar de coalgebra) een gesplitst epimorfisme is (Definitie 6.1). Dit generaliseert de bereikbaarheidsvoorwaarde door de morfismeklasse $M$ toe te staan de klasse van alle morfismen te zijn, in plaats van alleen de monomorfismen.
• Iteratieve Constructie (Boom-ontrafeling): De auteurs presenteren een iteratieve constructie (Constructie 6.23) die een willekeurige gepunte coalgebra transformeert naar een boom. Deze constructie omvat het nemen van de coproduct van niveaus, waarbij elk niveau wordt berekend via precieze factorisaties van de transitiefunctie. De resulterende coalgebra is de "boom-ontrafeling" van het oorspronkelijke systeem.
• Unificatie: Het artikel toont aan dat zowel bereikbaarheid als de eigenschap van een boom beide instanties zijn van dezelfde gegeneraliseerde notie van $M$-minimaliteit. Bereikbaarheid komt overeen met $M$ als een klasse van monomorfismen, terwijl de boom-eigenschap overeenkomt met $M$ als de klasse van alle morfismen.

Resultaten
De auteurs valideren hun theorie door de verwachte concepten van bomen te herstellen voor diverse standaardvoorbeelden:

• Partiële Deterministische Automaten: De boom-ontrafeling komt overeen met de "coalgebra van gedefinieerde inputs", waarbij toestanden worden geïdentificeerd met de unieke woorden die naar hen leiden (Lemma 6.11, Corolarium 6.12).
• Multigrafen (Bag Functor): Voor coalgebren over de bag-functor (die multigrafen modelleren), is de boom-ontrafeling de "coalgebra van gewortelde paden". Een bag-coalgebra is een boom dan ook en slechts dan als er een uniek pad van de wortel naar elke vertex is (Stelling 6.18).
• Powerset Functor: Het artikel benadrukt een beperking: voor de powerset-functor (die eenvoudige grafen modelleert), impliceert de karakterisering dat bijna geen enkele coalgebra een boom is. Dit komt doordat de powerset-functor "kopiëren" toestaat (bijv. $\{x\} = \{x, x\}$), wat de existentie van precieze afbeeldingen voor niet-lege verzamelingen verhindert (Propositie 3.3). Bijgevolg zijn bomen in deze setting triviaal (enkele vertex, geen randen).

Betekenis
Het artikel claimt betekenis door een verenigd theoretisch kader te bieden dat de theorie van bereikbare coalgebren uitbreidt naar boomstructuren.

• Generalisatie: Het slaagt erin het concept van bereikbaarheid te generaliseren van deugdelijke factorisatiesystemen (monos) naar willekeurige factorisatiesystemen, wat de behandeling van boomstructuren mogelijk maakt waarbij morfismen niet injectief hoeven te zijn.
• Analytische Functoren: De iteratieve constructie wordt getoond te werken voor alle analytische set-functoren (Corolarium 3.22), een brede klasse inclusief polynomiale functoren en de bag-functor, die centraal staan bij het modelleren van diverse computationele systemen.
• Conceptuele Helderheid: Door minimaliteit te koppelen aan projectiviteit en zowel universele als iteratieve karakteriseringen te bieden, biedt het artikel een robuuste categorische basis voor het begrijpen van boom-achtig gedrag in toestandsgebaseerde systemen, waarbij het duidelijk onderscheid maakt met het gedrag van systemen die gemodelleerd worden door de powerset-functor.

De auteurs merken op dat dit werk een uitgebreide versie is van een conferentiepaper, waarbij volledige bewijzen en verdere generalisaties zijn toegevoegd, met name de verbinding tussen minimaliteit en projectiviteit en de gedetailleerde analyse van precieze factorisaties.