Combinatorial necklace splitting.
Deciding soccer scores and partial orientations of graphs.
Bounded-degree graphs can have arbitrarily large slope numbers.
Asymptotically optimal pairing strategy for tic-tac-toe with numerous directions.
The range of non-linear natural polynomials cannot be context-free
Suppose that some polynomial with rational coefficients takes only natural values at natural numbers, i. e., . We show that the base- representation of is a context-free language if and only if is linear, answering a question of Shallit. The proof is based on a new criterion for context-freeness, which is a combination of the Interchange lemma and a generalization of the Pumping lemma.
Page 1