DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2024.65

Punctual Presentability in Certain Classes of Algebraic Structures

Authors: Dariusz Kalociński, Luca San Mauro, and Michał Wrocławski

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Abstract

Punctual structure theory is a rapidly emerging subfield of computable structure theory which aims at understanding the primitive recursive content of algebraic structures. A structure with domain ℕ is punctual if its relations and functions are (uniformly) primitive recursive. One of the fundamental problems of this area is to understand which computable members of a given class of structures admit a punctual presentation. We investigate such a problem for a number of familiar classes of algebraic structures, paying special attention to the case of trees, presented both in a relational and functional signature.

Cite as

Dariusz Kalociński, Luca San Mauro, and Michał Wrocławski. Punctual Presentability in Certain Classes of Algebraic Structures. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 65:1-65:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{kalocinski_et_al:LIPIcs.MFCS.2024.65,
  author =	{Kaloci\'{n}ski, Dariusz and San Mauro, Luca and Wroc{\l}awski, Micha{\l}},
  title =	{{Punctual Presentability in Certain Classes of Algebraic Structures}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{65:1--65:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.65},
  URN =		{urn:nbn:de:0030-drops-206212},
  doi =		{10.4230/LIPIcs.MFCS.2024.65},
  annote =	{Keywords: fully primitive recursive structures, punctual presentability, trees, injection structures}
}

Search Results

Documents authored by San Mauro, Luca

Punctual Presentability in Certain Classes of Algebraic Structures

Abstract

Cite as

Thanks for your feedback!

Could not send message