Multiwords are words in which a single symbol can be replaced by a nonempty set of symbols. They extend the notion of partial words. A word w is certain in a multiword M if it occurs in every word that can be obtained by selecting one single symbol among the symbols provided in each position of M. Motivated by a problem on incomplete databases, we investigate a variant of the pattern matching problem which is to decide whether a word w is certain in a multiword M. We study the language CERTAIN(w)...

Multiwords are words in which a single symbol can be replaced by a nonempty set of symbols. They extend the notion of partial words. A word w is certain in a multiword M if it occurs in every word that can be obtained by selecting one single symbol among the symbols provided in each position of M. Motivated by a problem on incomplete databases, we investigate a variant of the pattern matching problem which is to decide whether a word w is certain in a multiword M. We study the language CERTAIN(w)...

We give a partial answer to a question of Carlitz asking for a closed formula for the number of distinct representations of an integer in the Fibonacci base.

We give a partial answer to a question of Carlitz asking for a closed formula for the number of distinct representations of an integer in the Fibonacci base.

Given a groupoid $\langle G,☆\rangle$, and $k\ge 3$, we say that $G$ is antiassociative if an only if for all $x_1,x_2,x_3\in G$, $(x_1☆x_2)☆x_3$ and $x_1☆(x_2☆x_3)$ are never equal. Generalizing this, $\langle G,☆\rangle$ is $k$-antiassociative if and only if for all $x_1,x_2,...,x_k\in G$, any two distinct expressions made by putting parentheses in $x_1☆x_2☆x_3☆\cdots ☆x_k$ are never equal. We prove that for every $k\ge 3$, there exist finite groupoids that are $k$-antiassociative. We then generalize this, investigating when other pairs of groupoid terms can be made never equal.

Nous établissons pour tout nombre sturmien (de développement dyadique sturmien) des propriétés d'approximation diophantienne très précises, ne dépendant que de l'angle de la suite sturmienne, généralisant ainsi des travaux antérieurs de Ferenczi-Mauduit et Bullett-Sentenac.

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...

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...

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...