Suppose that some polynomial $f$ with rational coefficients takes only natural values at natural numbers, i. e., $L=\left\{f\right(n)\mid n\in \mathbb{N}\}\subseteq \mathbb{N}$. 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.

The seminal theorem of Cobham has given rise during the last 40 years to a lot of work about non-standard numeration systems and has been extended to many contexts. In this paper, as a result of fifteen years of improvements, we obtain a complete and general version for the so-called substitutive sequences. Let $\alpha$ and $\beta$ be two multiplicatively independent Perron numbers. Then a sequence $x\in A^{\mathbb{N}}$, where $A$ is a finite alphabet, is both $\alpha$-substitutive and $\beta$-substitutive if and only if $x$ is ultimately...

CONTENTSPREFACE..........................................................................................................................................................................3INTRODUCTION............................................................................................................................................................. 41. Notation. 2. Subject of the paper.Chapter I. DECOMPOSITION OF Σ INTO ${\Sigma }_1$, ${\Sigma }_2$, ${\Sigma }_3$, ${\Sigma }_4$ INESSENTIAL RESTRICTIONOF GENERALITY ...............................................................................................................................................................

The generalized $k$-connectivity ${\kappa }_k\left(G\right)$ of a graph $G$ was introduced by Chartrand et al. in 1984. As a natural counterpart of this concept, Li et al. in 2011 introduced the concept of generalized $k$-edge-connectivity which is defined as ${\lambda }_k\left(G\right)=min\{\lambda \left(S\right):S\subseteq V\left(G\right)$ and $\left|S\right|=k\}$, where $\lambda \left(S\right)$ denotes the maximum number $\ell$ of pairwise edge-disjoint trees $T_1,T_2,...,T_{\ell }$ in $G$ such that $S\subseteq V\left(T_i\right)$ for $1\le i\le \ell$. In this paper we prove that for any two connected graphs $G$ and $H$ we have ${\lambda }_3(G\square H)\ge {\lambda }_3\left(G\right)+{\lambda }_3\left(H\right)$, where $G\square H$ is the Cartesian product of $G$ and $H$. Moreover, the bound is sharp. We also...

Given a coarse space $(X,ℰ)$ with the bornology $ℬ$ of bounded subsets, we extend the coarse structure $ℰ$ from $X\times X$ to the natural coarse structure on $(ℬ\setminus \{\varnothing \left\}\right)\times (ℬ\setminus \{\varnothing \left\}\right)$ and say that a macro-uniform mapping $f:(ℬ\setminus \{\varnothing \left\}\right)\to X$ (or $f:{\left[X\right]}^2\to X$) is a selector (or 2-selector) of $(X,ℰ)$ if $f\left(A\right)\in A$ for each $A\in ℬ\setminus \left\{\varnothing \right\}$ ($A\in {\left[X\right]}^2$, respectively). We prove that a discrete coarse space $(X,ℰ)$ admits a selector if and only if $(X,ℰ)$ admits a 2-selector if and only if there exists a linear order “$\le$" on $X$ such that the family of intervals $\left\{\right[a,b]:a,b\in X,a\le b\}$ is a base for the bornology $ℬ$.

In this paper we prove the following theorems in incidence geometry. 1. There is $\delta >0$ such that for any $P_1,\cdots ,P_4$, and $Q_1,\cdots ,Q_n\in {ℂ}^2$, if there are $\le n^{(1+\delta )/2}$ many distinct lines between $P_i$ and $Q_j$ for all $i$, $j$, then $P_1,\cdots ,P_4$ are collinear. If the number of the distinct lines is $<c{n}^{1/2}$ then the cross ratio of the four points is algebraic. 2. Given $c>0$, there is $\delta >0$ such that for any $P_1,P_2,P_3\in {ℂ}^2$ noncollinear, and $Q_1,\cdots ,Q_n\in {ℂ}^2$, if there are $\le c{n}^{1/2}$ many distinct lines between $P_i$ and $Q_j$ for all $i$, $j$, then for any $P\in {ℂ}^2\setminus \{P_1,P_2,P_3\}$, we have $\delta n$ distinct lines between $P$ and $Q_j$. 3. Given...