Document Open Access Logo

Arboreal Categories and Resources

Authors Samson Abramsky , Luca Reggio

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2021.115.pdf
  • Filesize: 0.78 MB
  • 20 pages

Document Identifiers

Author Details

Samson Abramsky
  • Department of Computer Science, University of Oxford, UK
Luca Reggio
  • Department of Computer Science, University of Oxford, UK

Funding

  • Abramsky, Samson: Research supported by the EPSRC project EP/T00696X/1 "Resources and Co-Resources: a junction between categorical semantics and descriptive complexity".
  • Reggio, Luca: Research supported by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 837724.

Acknowledgements

Feedback from Tomáš Jakl and Dan Marsden is gratefully acknowledged.

Cite AsGet BibTex

Samson Abramsky and Luca Reggio. Arboreal Categories and Resources. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 115:1-115:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ICALP.2021.115

Abstract

We introduce arboreal categories, which have an intrinsic process structure, allowing dynamic notions such as bisimulation and back-and-forth games, and resource notions such as number of rounds of a game, to be defined. These are related to extensional or "static" structures via arboreal covers, which are resource-indexed comonadic adjunctions. These ideas are developed in a very general, axiomatic setting, and applied to relational structures, where the comonadic constructions for pebbling, Ehrenfeucht-Fraïssé and modal bisimulation games recently introduced in [Abramsky et al., 2017; S. Abramsky and N. Shah, 2018; Abramsky and Shah, 2021] are recovered, showing that many of the fundamental notions of finite model theory and descriptive complexity arise from instances of arboreal covers.

Subject Classification

ACM Subject Classification
  • Theory of computation → Categorical semantics
  • Theory of computation → Finite Model Theory
Keywords
  • factorisation system
  • embedding
  • comonad
  • coalgebra
  • open maps
  • bisimulation
  • game
  • resources
  • relational structures
  • finite model theory

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. S. Abramsky, A. Dawar, and P. Wang. The pebbling comonad in finite model theory. In 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pages 1-12, 2017. Google Scholar
  2. S. Abramsky, R. Jagadeesan, and P. Malacaria. Full abstraction for PCF. Information and computation, 163(2):409-470, 2000. Google Scholar
  3. S. Abramsky and D. Marsden. Comonadic semantics for guarded fragments. Preprint available at https://arxiv.org/abs/2008.11094, 2020.
  4. S. Abramsky and L. Reggio. Arboreal categories: An axiomatic theory of resources. Extended version. Preprint available at https://arxiv.org/abs/2102.08109, 2021.
  5. S. Abramsky and N. Shah. Relating structure and power: Comonadic semantics for computational resources. In 27th EACSL Annual Conference on Computer Science Logic, CSL, September 4-7, 2018, Birmingham, UK, pages 2:1-2:17, 2018. Google Scholar
  6. S. Abramsky and N. Shah. Relating structure and power: Comonadic semantics for computational resources. Extended version to appear in Journal of Logic and Computation. Preprint available at https://arxiv.org/abs/2010.06496, 2021.
  7. J. Adámek, H. Herrlich, and G.E. Strecker. Abstract and concrete categories. The joy of cats. Online edition, 2004. Google Scholar
  8. P. Blackburn, M. De Rijke, and Y. Venema. Modal Logic, volume 53 of Cambridge Tracts in Theoretical Computer Science. Cambridge University Press, 2002. Google Scholar
  9. A. Ó Conghaile and A. Dawar. Game comonads & generalised quantifiers. In 29th EACSL Annual Conference on Computer Science Logic, CSL, volume 183 of LIPIcs, pages 16:1-16:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. Google Scholar
  10. P.J. Freyd and G.M. Kelly. Categories of continuous functors, I. Journal of Pure and Applied Algebra, 2(3):169-191, 1972. Google Scholar
  11. J.M.E. Hyland and C.-H.L Ong. On full abstraction for PCF: I, II, and III. Information and computation, 163(2):285-408, 2000. Google Scholar
  12. A. Joyal, M. Nielsen, and G. Winskel. Bisimulation from open maps. Information and Computation, 127(2):164-185, 1996. Google Scholar
  13. A. Joyal, M. Nielson, and G. Winskel. Bisimulation and open maps. In Proceedings of 8th Annual IEEE Symposium on Logic in Computer Science, pages 418-427, 1993. Google Scholar
  14. T. Kloks. Treewidth: computations and approximations, volume 842 of Springer Lecture Notes in Computer Science. Springer Science & Business Media, 1994. Google Scholar
  15. L. Libkin. Elements of finite model theory. Texts in Theoretical Computer Science. An EATCS Series. Springer-Verlag, Berlin, 2004. Google Scholar
  16. S. Mac Lane. Categories for the working mathematician, volume 5 of Graduate Texts in Mathematics. Springer-Verlag, New York, second edition, 1998. Google Scholar
  17. J. Nešetřil and P. Ossona de Mendez. Tree-depth, subgraph coloring and homomorphism bounds. European Journal of Combinatorics, 27(6):1022-1041, 2006. Google Scholar
  18. E. Riehl. Factorization systems. Notes available at URL: http://www.math.jhu.edu/~eriehl/factorization.pdf.
  19. B. Rossman. Homomorphism preservation theorems. J. ACM, 55(3):15:1-15:53, 2008. Google Scholar
  20. ACM SIGLOG. Alonzo Church Award, 2017. URL: https://siglog.org/winners-of-the-2017-alonzo-church-award/.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact