Fibrational Perspectives on Determinization of Finite-State Automata
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909805265813504 |
|---|---|
| author | Li, Thea |
| author_facet | Li, Thea |
| contents | Colcombet and Petrişan argued that automata may be usefully considered from a functorial perspective, introducing a general notion of "V-automaton" based on functors into V. This enables them to recover different standard notions of automata by choosing V appropriately, and they further analyzed the determinization for Rel-automata using the Kleisli adjunction between Set and Rel. In this paper, we revisit Colcombet and Petrişan's analysis from a fibrational perspective, building on Melliès and Zeilberger's recent alternative but related definition of categorical automata as functors 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 Rel automata using a local adjunction between SpanSet and Rel, which provides us with a canonical forward simulation. Finally, we also propose an alternative determinization based on the multiset relative adjunction which retains paths, and we leverage this to provide a canonical forward-backward simulation. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_00675 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Fibrational Perspectives on Determinization of Finite-State Automata Li, Thea Category Theory Formal Languages and Automata Theory Logic in Computer Science Colcombet and Petrişan argued that automata may be usefully considered from a functorial perspective, introducing a general notion of "V-automaton" based on functors into V. This enables them to recover different standard notions of automata by choosing V appropriately, and they further analyzed the determinization for Rel-automata using the Kleisli adjunction between Set and Rel. In this paper, we revisit Colcombet and Petrişan's analysis from a fibrational perspective, building on Melliès and Zeilberger's recent alternative but related definition of categorical automata as functors 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 Rel automata using a local adjunction between SpanSet and Rel, which provides us with a canonical forward simulation. Finally, we also propose an alternative determinization based on the multiset relative adjunction which retains paths, and we leverage this to provide a canonical forward-backward simulation. |
| title | Fibrational Perspectives on Determinization of Finite-State Automata |
| topic | Category Theory Formal Languages and Automata Theory Logic in Computer Science |
| url | https://arxiv.org/abs/2410.00675 |