4 citations · 7 across the 8 of their papers we have counts for
4 papers · 1 filter
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…