Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Gao, Ziyuan; Jain, Sanjay; Khoussainov, Bakhadyr; Li, Wei; Melnikov, Alexander; Seidel, Karen; Stephan, Frank http://www.dagstuhl.de/lipics License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-109693
URL:

; ; ; ; ; ;

Random Subgroups of Rationals

pdf-format:


Abstract

This paper introduces and studies a notion of algorithmic randomness for subgroups of rationals. Given a randomly generated additive subgroup (G,+) of rationals, two main questions are addressed: first, what are the model-theoretic and recursion-theoretic properties of (G,+); second, what learnability properties can one extract from G and its subclass of finitely generated subgroups? For the first question, it is shown that the theory of (G,+) coincides with that of the additive group of integers and is therefore decidable; furthermore, while the word problem for G with respect to any generating sequence for G is not even semi-decidable, one can build a generating sequence beta such that the word problem for G with respect to beta is co-recursively enumerable (assuming that the set of generators of G is limit-recursive). In regard to the second question, it is proven that there is a generating sequence beta for G such that every non-trivial finitely generated subgroup of G is recursively enumerable and the class of all such subgroups of G is behaviourally correctly learnable, that is, every non-trivial finitely generated subgroup can be semantically identified in the limit (again assuming that the set of generators of G is limit-recursive). On the other hand, the class of non-trivial finitely generated subgroups of G cannot be syntactically identified in the limit with respect to any generating sequence for G. The present work thus contributes to a recent line of research studying algorithmically random infinite structures and uncovers an interesting connection between the arithmetical complexity of the set of generators of a randomly generated subgroup of rationals and the learnability of its finitely generated subgroups.

BibTeX - Entry

@InProceedings{gao_et_al:LIPIcs:2019:10969,
  author =	{Ziyuan Gao and Sanjay Jain and Bakhadyr Khoussainov and Wei Li and Alexander Melnikov and Karen Seidel and Frank Stephan},
  title =	{{Random Subgroups of Rationals}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{25:1--25:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Peter Rossmanith and Pinar Heggernes and Joost-Pieter Katoen},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10969},
  URN =		{urn:nbn:de:0030-drops-109693},
  doi =		{10.4230/LIPIcs.MFCS.2019.25},
  annote =	{Keywords: Martin-L{\"o}f randomness, subgroups of rationals, finitely generated subgroups of rationals, learning in the limit, behaviourally correct learning}
}

Keywords: Martin-Löf randomness, subgroups of rationals, finitely generated subgroups of rationals, learning in the limit, behaviourally correct learning
Seminar: 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Issue date: 2019
Date of publication: 2019


DROPS-Home | Imprint | Privacy Published by LZI