Fibrational perspectives on determinization of finite-state automata
<|reference_start|>Fibrational perspectives on determinization of finite-state automata: Colcombet and Petri\c{s}an argued that automata may be usefully considered from a functorial perspective, introducing a general notion of "$\mathcal{V}$-automaton" based on functors into $\mathcal{V}$. This enables them to recover different standard notions of automata by choosing $\mathcal{V}$ appropriately, and they further analyzed the determinization for \textbf{Rel}-automata using the Kleisli adjunction between \textbf{Set} and \textbf{Rel}. In this paper, we revisit Colcombet and Petri\c{s}an's analysis from a fibrational perspective, building on Melli\`es and Zeilberger's recent alternative but related definition of categorical automata as functors $p : \mathcal{Q} \to \mathcal{C}$ satisfying the finitary fiber and unique lifting of factorizations property. In doing so, we improve the understanding of determinization in three regards: Firstly, we carefully describe the universal property of determinization in terms of forward-backward simulations. Secondly, we generalize the determinization procedure for \textbf{Rel} automata using a local adjunction between \textbf{SpanSet} and \textbf{Rel}, which provides us with a canonical forward simulation. Finally we also propose an alterative determinization based on the multiset relative adjunction which retains paths, and we leverage this to provide a canonical forward-backward simulation.<|reference_end|>
@article{li2024fibrational,
    title={Fibrational perspectives on determinization of finite-state automata},
    author={Thea Li},
    journal={arXiv preprint arXiv:2410.00675},
    year={2024},
    archivePrefix={arXiv},
    eprint={2410.00675},
    primaryClass={math.CT cs.FL cs.LO}
}