Gao, Ziyuan ;
Jain, Sanjay ;
Khoussainov, Bakhadyr ;
Li, Wei ;
Melnikov, Alexander ;
Seidel, Karen ;
Stephan, Frank
Random Subgroups of Rationals
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 modeltheoretic and recursiontheoretic 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 semidecidable, one can build a generating sequence beta such that the word problem for G with respect to beta is corecursively enumerable (assuming that the set of generators of G is limitrecursive). In regard to the second question, it is proven that there is a generating sequence beta for G such that every nontrivial finitely generated subgroup of G is recursively enumerable and the class of all such subgroups of G is behaviourally correctly learnable, that is, every nontrivial finitely generated subgroup can be semantically identified in the limit (again assuming that the set of generators of G is limitrecursive). On the other hand, the class of nontrivial 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:125:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771177},
ISSN = {18688969},
year = {2019},
volume = {138},
editor = {Peter Rossmanith and Pinar Heggernes and JoostPieter Katoen},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10969},
URN = {urn:nbn:de:0030drops109693},
doi = {10.4230/LIPIcs.MFCS.2019.25},
annote = {Keywords: MartinL{\"o}f randomness, subgroups of rationals, finitely generated subgroups of rationals, learning in the limit, behaviourally correct learning}
}
20.08.2019
Keywords: 

MartinLö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: 

20.08.2019 