12 citations · 14 across the 9 of their papers we have counts for
11 papers
Quasi-Isometric Reductions Between Infinite Strings
Karen Frilya Celine, Ziyuan Gao, Sanjay Jain +3
This paper studies the recursion-theoretic aspects of large-scale geometries of infinite strings, a subject initiated by Khoussainov and Takisaka (2017). We investigate several not…
A Computation Model with Automatic Functions and Relations as Primitive Operations
Ziyuan Gao, Sanjay Jain, Li Zeyong +2
Prior work of Hartmanis and Simon (Hartmanis and Simon, 1974) and Floyd and Knuth (Floyd and Knuth, 1990) investigated what happens if a device uses primitive steps more natural th…
Alternating Automatic Register Machines
Ziyuan Gao, Sanjay Jain, Zeyong Li +2
This paper introduces and studies a new model of computation called an Alternating Automatic Register Machine (AARM). An AARM possesses the basic features of a conventional registe…
Ordered Semiautomatic Rings with Applications to Geometry
Ziyuan Gao, Sanjay Jain, Ji Qi +3
The present work looks at semiautomatic rings with automatic addition and comparisons which are dense subrings of the real numbers and asks how these can be used to represent geome…
Learnability and Positive Equivalence Relations
David Belanger, Ziyuan Gao, Sanjay Jain +2
Prior work of Gavryushkin, Khoussainov, Jain and Stephan investigated what algebraic structures can be realised in worlds given by a positive (= recursively enumerable) equivalence…
The teaching complexity of erasing pattern languages with bounded variable frequency
Ziyuan Gao
Patterns provide a concise, syntactic way of describing a set of strings, but their expressive power comes at a price: a number of fundamental decision problems concerning (erasing…
Random Subgroups of Rationals
Ziyuan Gao, Sanjay Jain, Bakhadyr Khoussainov +4
This paper introduces and studies a notion of \emph{algorithmic randomness} for subgroups of rationals. Given a randomly generated additive subgroup of rationals, two main…
The Cop Number of the One-Cop-Moves Game on Planar Graphs
Ziyuan Gao, Boting Yang
Cops and robbers is a vertex-pursuit game played on graphs. In the classical cops-and-robbers game, a set of cops and a robber occupy the vertices of the graph and move alternately…
Preference-based Teaching
Ziyuan Gao, Christoph Ries, Hans Ulrich Simon +1
We introduce a new model of teaching named "preference-based teaching" and a corresponding complexity parameter---the preference-based teaching dimension (PBTD)---representing the…
Classifying the Arithmetical Complexity of Teaching Models
Achilles A. Beros, Ziyuan Gao, Sandra Zilles
This paper classifies the complexity of various teaching models by their position in the arithmetical hierarchy. In particular, we determine the arithmetical complexity of the inde…
Combining Models of Approximation with Partial Learning
Ziyuan Gao, Frank Stephan, Sandra Zilles
In Gold's framework of inductive inference, the model of partial learning requires the learner to output exactly one correct index for the target object and only the target object…