We consider positional numeration system with negative base $-\beta$, as introduced by Ito and Sadahiro. In particular, we focus on arithmetical properties of such systems when $\beta$ is a quadratic Pisot number. We study a class of roots $\beta >1$ of polynomials $x^2-mx-n$, $m\ge n\ge 1$, and show that in this case the set $\mathrm{Fin}(-\beta )$ of finite $(-\beta )$-expansions is closed under addition, although it is not closed under subtraction. A particular example is $\beta =\tau =\frac{1}{2}(1+\sqrt{5})$, the golden ratio. For such $\beta$, we determine the exact bound on the number of fractional digits...

Motivated by the Watts-Strogatz model for a complex network, we introduce a generalization of the Erdős-Rényi random graph. We derive a combinatorial formula for the moment sequence of its spectral distribution in the sparse limit.

We determine minimal elements, i.e., atoms, in certain partial orders of factor closed languages under $\subseteq$. This is in analogy to structural Ramsey theory which determines minimal structures in partial orders under embedding.

We determine minimal elements, i.e., atoms, in certain partial orders of factor closed languages under ⊆. This is in analogy to structural Ramsey theory which determines minimal structures in partial orders under embedding.

Let $K$ be a finite field of characteristic $p$. Let $K\left(\right(x\left)\right)$ be the field of formal Laurent series $f\left(x\right)$ in $x$ with coefficients in $K$. That is,$$f\left(x\right)=\sum _{n=n_0}^{\infty }{f}_n{x}^n$$with $n_0\in 𝐙$ and $f_n\in K(n=n_0,n_0+1,\cdots )$. We discuss the distribution of ${\left(\left\{f^m\right\}\right)}_{m=0,1,2,\cdots }$ for $f\in K\left(\right(x\left)\right)$, where$$\left\{f\right\}:=\sum _{n=0}^{\infty }{f}_n{x}^n\in K\left[\left[x\right]\right]$$denotes the nonnegative part of $f\in K\left(\right(x\left)\right)$. This is a little different from the real number case where the fractional part that excludes constant term (digit of order 0) is considered. We give an alternative proof of a result by De Mathan obtaining the generic distribution for $f$ with $f_n\ne 0$ for some $n\<0$. This distribution is...

This note is about functions ƒ : Aω → Bω whose graph is recognized by a Büchi finite automaton on the product alphabet A x B. These functions are Baire class 2 in the Baire hierarchy of Borel functions and it is decidable whether such function are continuous or not. In 1920 W. Sierpinski showed that a function $f:ℝ\to ℝ$ is Baire class 1 if and only if both the overgraph and the undergraph of f are Fσ. We show that such characterization is also true for functions on infinite words if we replace the real...

New compact representations of infinite graphs are investigated. Finite automata are used to represent labelled hyper-graphs which can be also multi-graphs. Our approach consists of a general framework where vertices are represented by a regular prefix-free language and edges are represented by a regular language and a function over tuples. We consider three different functions over tuples: given a tuple the first function returns its first difference, the second one returns its suffix and the last...

New compact representations of infinite graphs are investigated. Finite automata are used to represent labelled hyper-graphs which can be also multi-graphs. Our approach consists of a general framework where vertices are represented by a regular prefix-free language and edges are represented by a regular language and a function over tuples. We consider three different functions over tuples: given a tuple the first function returns its first difference, the second one returns its suffix and...

Le point fixe $u$ d’une substitution injective uniforme de module $\sigma$ sur un alphabet $A$ est examiné du point de vue du nombre $P(u,n)$ de ses blocs distincts de longueur $n$. Lorsque $u$ est minimal et $A$ de cardinal deux, nous construisons un automate pour la suite $n\to P(u,n+1)-P(u,n)$.

Dans quelle mesure la régularité des chiffres d’un nombre réel dans une base entière, celle des quotients partiels du développement en fraction continuée d’un nombre réel, ou celle des coefficients d’une série formelle sont-elles liées à l’algébricité ou à la transcendance de ce réel ou de cette série formelle  ? Nous proposons un survol de résultats récents dans le cas où la régularité évoquée ci-dessus est celle de suites automatiques, substitutives, ou sturmiennes.

This paper studies the descriptional complexity of (i) sequences over a finite alphabet ; and (ii) subsets of $N$ (the natural numbers). If ${\left(s\left(i\right)\right)}_{i\ge 0}$ is a sequence over a finite alphabet $\Delta$, then we define the $k$-automaticity of $s,A_s^k\left(n\right)$, to be the smallest possible number of states in any deterministic finite automaton that, for all $i$ with $0\le i\le n$, takes $i$ expressed in base $k$ as input and computes $s\left(i\right)$. We give examples of sequences that have high automaticity in all bases $k$ ; for example, we show that the characteristic...

In this paper we will deal with the balance properties of the infinite binary words associated to β-integers when β is a quadratic simple Pisot number. Those words are the fixed points of the morphisms of the type $\varphi \left(A\right)=A^{p}B$, $\varphi \left(B\right)=A^q$ for $p\in \mathbb{N}$, $q\in \mathbb{N}$, $p\ge q$, where $\beta =\frac{p+\sqrt{p^2+4q}}{2}$. We will prove that such word is t-balanced with $t=1+\left[(p-1)/(p+1-q)\right]$. Finally, in the case that p < q it is known [B. Adamczewski, Theoret. Comput. Sci.273 (2002) 197–224] that the fixed point of the substitution $\varphi \left(A\right)=A^{p}B$, $\varphi \left(B\right)=A^q$ is not m-balanced for any m. We exhibit an infinite sequence...

A word u defined over an alphabet $𝒜$ is c-balanced (c∈$\mathbb{N}$) if for all pairs of factors v, w of u of the same length and for all letters a∈$𝒜$, the difference between the number of letters a in v and w is less or equal to c. In this paper we consider a ternary alphabet $𝒜$ = {L, S, M} and a class of substitutions ${\varphi }_p$ defined by ${\varphi }_p$(L) = LpS, ${\varphi }_p$(S) = M, ${\varphi }_p$(M) = Lp–1S where p> 1. We prove that the fixed point of ${\varphi }_p$, formally written as ${\varphi }_p^{\infty }$(L), is 3-balanced and that its Abelian complexity is bounded above by...