1 citations · 1 across the 3 of their papers we have counts for
5 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…
Chains and Antichains inside Many-One Degrees and Variants
Linus Richter, Frank Stephan, Xiaoyan Zhang
The relations between many-one degrees and one-one degrees have been studied since the beginning of recursion theory; early results from the 1960s include that many-one degrees alw…
Languages of Words of Low Automatic Complexity Are Hard to Compute
Joey Chen, Bjørn Kjos-Hanssen, Ivan Koswara +2
The automatic complexity of a finite word (string) is an analogue for finite automata of Sipser's distinguishing complexity (1983) and was introduced by Shallit and Wang (2001). Fo…
All Borel Group Extensions of Finite-Dimensional Real Space Are Trivial
Linus Richter
For , we study the structure of definable abelian group extensions of the additive group by countable abelian (Borel) groups . Given an extension $H…
Co-analytic Counterexamples to Marstrand's Projection Theorem
Linus Richter
Assuming , we construct a plane set of Hausdorff dimension whose every orthogonal projection onto straight lines through the origin has Hausdorff dimension . This i…