2 citations · 5 across the 8 of their papers we have counts for
15 papers · 1 filter
A minimal set low for speed
Rod Downey, Matthew Harrison-Trainor
An oracle is low-for-speed if it is unable to speed up the computation of a set which is already computable: if a decidable language can be decided in time using as…
An introduction to the Scott complexity of countable structures and a survey of recent results
Matthew Harrison-Trainor
Every countable structure has a sentence of the infinitary logic which characterizes that structure up to isomorphism among countable structures. Such a sente…
Computing sets from all infinite subsets
Noam Greenberg, Matthew Harrison-Trainor, Ludovic Patey +1
A set is introreducible if it can be computed by every infinite subset of itself. Such a set can be thought of as coding information very robustly. We investigate introreducible se…
Relationships between computability-theoretic properties of problems
Rod Downey, Noam Greenberg, Matthew Harrison-Trainor +2
A problem is a multivalued function from a set of \emph{instances} to a set of \emph{solutions}. We consider only instances and solutions coded by sets of integers. A problem admit…
Characterizations of Cancellable Groups
Matthew Harrison-Trainor, Meng-Che "Turbo" Ho
An abelian group is said to be cancellable if whenever is isomorphic to , is isomorphic to . We show that the index set of cancellable rank 1 to…
Which Classes of Structures Are Both Pseudo-elementary and Definable by an Infinitary Sentence?
Will Boney, Barbara F. Csima, Nancy A. Day +1
When classes of structures are not first-order definable, we might still try to find a nice description. There are two common ways for doing this. One is to expand the language, le…