4 citations · 7 across the 8 of their papers we have counts for
9 papers
Non-Terminal Complexity of Simple Semi-Conditional Grammars
Henning Fernau, Sanjay Jain, Linus Richter +2
We study the complexity of simple semi-conditional grammars (SSCGs) in terms of the number of their terminals and non-terminals. We show that SSCGs with three non-terminals can gen…
Structural vs. computational complexity
Johanna N. Y. Franklin, Dino Rossegger, Dan Turetsky
We consider highness in the context of computable structure theory and, particularly, the Scott rank of a structure. We define highness for Scott rank and highness for computably d…
Scott Analysis below the Vaught Ordinal
David Gonzalez, Dino Rossegger, Dan Turetsky
We develop new tools for determining the existence of models of specific Scott ranks under countability conditions. Using these, we improve a result of Sacks by showing that any co…
Topology, forcing, and graph colourings
Noam Greenberg, Dominique Lecomte, Dan Turetsky +1
We introduce a family of forcing notions that are helpful in showing that certain graphs do not have countable colourings of (additive) Borel class alpha. We construct graphs that…
An Effective Classification of Borel Wadge Classes
Adam Day, Noam Greenberg, Matthew Harrison-Trainor +1
We give a new and effective classification of all Borel Wadge classes of subsets of Baire space. This relies on the true stage machinery originally developed by Montalbán. We use t…
Iterated Priority Arguments in Descriptive Set Theory
Adam Day, Noam Greenberg, Matthew Harrison-Trainor +1
We present the true stages machinery and illustrate its applications to descriptive set theory. We use this machinery to provide new proofs of the Hausdorff-Kuratowski and Wadge th…
Limit Complexities, Minimal Descriptions, and -Randomness
Rodney Downey, Lu Liu, Keng Meng Ng +1
Let denote prefix-free Kolmogorov Complexity, and denote it relative to an oracle . We show that for any , is definable purely in terms of the…
Martin-Löf reducibility and cost functions
Noam Greenberg, Joseph S. Miller, Andre Nies +1
Martin-Löf (ML)-reducibility compares -trivial sets by examining the Martin-Löf random sequences that compute them. We show that every -trivial set is computable from a c.e.\…
Computing K-Trivial Sets by Incomplete Random Sets
Laurent Bienvenu, Adam R. Day, Noam Greenberg +4
Every K-trivial set is computable from an incomplete Martin-Löf random set, i.e., a Martin-Löf random set that does not compute 0'.