EUDML

Advanced Search

Currently displaying 1 – 5 of 5

Order by Relevance | Title | Year of publication

Combinatorial necklace splitting.

Pálvölgyi, Dömötör — 2009

The Electronic Journal of Combinatorics [electronic only]

Deciding soccer scores and partial orientations of graphs.

Pálvölgyi, Dömötör — 2009

Acta Universitatis Sapientiae. Mathematica

Bounded-degree graphs can have arbitrarily large slope numbers.

Pach, János; Pálvölgyi, Dömötör — 2006

The Electronic Journal of Combinatorics [electronic only]

Asymptotically optimal pairing strategy for tic-tac-toe with numerous directions.

Mukkamala, Padmini; Pálvölgyi, Dömötör — 2010

The Electronic Journal of Combinatorics [electronic only]

The range of non-linear natural polynomials cannot be context-free

Dömötör Pálvölgyi — 2020

Kybernetika

Suppose that some polynomial $f$ with rational coefficients takes only natural values at natural numbers, i. e., $L = {f (n) ∣ n \in ℕ} \subseteq ℕ$ . We show that the base- $q$ representation of $L$ is a context-free language if and only if $f$ 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

Download Results (CSV)

Advanced Search

Formula preview

Currently displaying 1 – 5 of 5

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