26 citations · 42 across the 11 of their papers we have counts for
14 papers
On the computability of optimal Scott sentences
Rachael Alvir, Barbara Csima, Matthew Harrison-Trainor
Given a countable mathematical structure, its Scott sentence is a sentence of the infinitary logic that characterizes it among all countable structures. We ca…
Scott Complexity of Reduced Abelian -Groups
Rachael Alvir, Barbara F. Csima, Luke MacLean
Given a reduced abelian -group, we give an upper bound on the Scott complexity of the group in terms of its Ulm invariants. For limit ordinals, we show that this upper bound is…
Effectiveness of Walker's Cancellation Theorem
Layth Al-Hellawi, Rachael Alvir, Barbara F. Csima +1
Walker's Cancellation theorem for abelian groups tells us that if is finitely generated and and are such that , then . Michael D…
Degrees of categoricity and treeable degrees
Barbara F. Csima, Dino Rossegger
We give a characterization of the strong degrees of categoricity of computable structures greater or equal to . They are precisely the \emph{treeable} degrees -- the l…
Relations enumerable from positive information
Barbara F. Csima, Luke MacLean, Dino Rossegger
We study countable structures from the viewpoint of enumeration reducibility. Since enumeration reducibility is based on only positive information, in this setting it is natural to…
Some Questions of Uniformity in Algorithmic Randomness
Laurent Bienvenu, Barbara Csima, Matthew Harrison-Trainor
The numbers-the halting probabilities of universal prefix-free machines-are known to be exactly the Martin-L{ö}f random left-c.e. reals. We show that one cannot uniformly produ…
Positive enumerable functors
Barbara Csima, Dino Rossegger, Zhi Ying "Daniel" Yu
We study reductions well suited to compare structures and classes of structures with respect to properties based on enumeration reducibility. We introduce the notion of a positive…
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…
Optimal bounds for single-source Kolmogorov extractors
Laurent Bienvenu, Barbara F. Csima, Matthew Harrison-Trainor
The rate of randomness (or dimension) of a string is the ratio where is the Kolmogorov complexity of . While it is known that a single computable transform…
The reverse mathematics of Hindman's theorem for sums of exactly two elements
Barbara F. Csima, Damir D. Dzhafarov, Denis R. Hirschfeldt +3
Hindman's Theorem (HT) states that for every coloring of with finitely many colors, there is an infinite set such that all nonempty sums of dist…
Degrees of Categoricity Above Limit Ordinals
Barbara F. Csima, Michael Deveau, Matthew Harrison-Trainor +1
A computable structure has degree of categoricity if is exactly the degree of difficulty of computing isomorphisms between isomorphic comput…
Degrees of categoricity on a cone
Barbara Csima, Matthew Harrison-Trainor
We investigate the complexity of isomorphisms of computable structures on cones in the Turing degrees. We show that, on a cone, every structure has a strong degree of categoricity,…
Degrees that are not degrees of categoricity
Bernard A. Anderson, Barbara F. Csima
A computable structure A is x-computably categorical for some Turing degree x, if for every computable structure B isomorphic to A there is an isomorphism f:B -> A with f computabl…
A bounded jump for the bounded Turing degrees
Bernard A. Anderson, Barbara F. Csima
We define the bounded jump of A by A^b = {x | Exists i <= x [phi_i (x) converges and Phi_x^[A|phi_i(x)](x) converges} and let A^[nb] denote the n-th bounded jump. We demonstrate se…