Pratiques funéraires inédites en France : la crémation au Campaniforme

International audience

A note on easy and efficient computation of full abelian periods of a word

Constantinescu and Ilie (Bulletin of the EATCS 89, 167-170, 2006) introduced the idea of an Abelian period with head and tail of a finite word. An Abelian period is called full if both the head and the tail are empty. We present a simple and easy-to-implement $O(n\log\log n)$-time algorithm for computing all the full Abelian periods of a word of length $n$ over a constant-size alphabet. Experiments show that our algorithm significantly outperforms the $O(n)$ algorithm proposed by Kociumaka et al. (Proc. of STACS, 245-256, 2013) for the same problem.

The beaker phenomenon and the Genomic transformations of Northwest Europe

Bell Beaker pottery spread across western and central Europe beginning around 2750 BCE before disappearing between 2200–1800 BCE. The mechanism of its expansion is a topic of long-standing debate, with support for both cultural diffusion and human migration. We present new genome-wide ancient DNA data from 170 Neolithic, Copper Age and Bronze Age Europeans, including 100 Beaker-associated individuals. In contrast to the Corded Ware Complex, which has previously been identified as arriving in central Europe following migration from the east, we observe limited genetic affinity between Iberian and central European Beaker Complex-associated individuals, and thus exclude migration as a signific…

Online Computation of Abelian Runs

Given a word $w$ and a Parikh vector $\mathcal{P}$, an abelian run of period $\mathcal{P}$ in $w$ is a maximal occurrence of a substring of $w$ having abelian period $\mathcal{P}$. We give an algorithm that finds all the abelian runs of period $\mathcal{P}$ in a word of length $n$ in time $O(n\times |\mathcal{P}|)$ and space $O(\sigma+|\mathcal{P}|)$.

Les pratiques funéraires en Lorraine au 2e siècle apr. J.-C. : dépôts de crémation et fosses secondaires. L’exemple des sites de Saint-Julien-lès-Gorze et de Grostenquin (Meurthe-et-Moselle, Moselle, France)

International audience

Trémery, Moselle, ZAC de la Fontaine des Saints, site 19 : rapport de fouille

Le Néolithique ancien est marqué par la présence de fosses allongées. La céramique issue de leur remplissage montre des décors réalisés selon la technique du pointillé-sillonné ainsi que l'utilisation du peigne à deux dents et la forte proportion du motif en chevron simple ou double, permettant d'attribuer l'ensemble du mobilier céramique des fosses à l'horizon IIc du Rubané de la chronologie du Rhin moyen ou de la phase 5 régionale. Si du point de vue de la céramique, les fosses appartiennent au même horizon chronologique, en revanche il n'est pas établi qu'elles aient été associées au même habitat qui n'a d'ailleurs pas été conservé. Au regard du nombre de vestiges, on peut penser que le …

Des tombes privilégiées sur le mont Saint-Vanne (Verdun, citadelle haute)

International audience

Abelian Powers and Repetitions in Sturmian Words

Richomme, Saari and Zamboni (J. Lond. Math. Soc. 83: 79-95, 2011) proved that at every position of a Sturmian word starts an abelian power of exponent $k$ for every $k > 0$. We improve on this result by studying the maximum exponents of abelian powers and abelian repetitions (an abelian repetition is an analogue of a fractional power) in Sturmian words. We give a formula for computing the maximum exponent of an abelian power of abelian period $m$ starting at a given position in any Sturmian word of rotation angle $\alpha$. vAs an analogue of the critical exponent, we introduce the abelian critical exponent $A(s_\alpha)$ of a Sturmian word $s_\alpha$ of angle $\alpha$ as the quantity $A(s_\a…

Farébersviller, Moselle, "La ferme champêtre de Bruskir II" - de l'aire agricole laténienne à l'aire funéraire antique

Der Fundplatz von Farébersviller, Moselle, « La ferme champêtre Bruskir II » : Von der ländlichen Siedlung der Latènezeit zum antiken GräberfeldDer Fundplatz von Farébersviller « La ferme champêtre Bruskir II », etwa 15 km sudwestlich von Saarbrücken im Ostteil des Departements Moselle gelegen, befand sich an einem kleinen nord-west ausgerichteten Hang und war leider durch das lokale Erosionsgeschehen erheblich in Mitleidenschaft gezogen worden. Trotzdem gelang es, im Laufe der vom Institut national de recherches archéologiques préventives (Inrap) durchgeführten Grabung drei verschiedene Besiedlungsphasen nachzuweisen: eine kleine ländliche Besiedlung der Spätlatènezeit, die durch einen Vie…

Fast computation of abelian runs

Given a word $w$ and a Parikh vector $\mathcal{P}$, an abelian run of period $\mathcal{P}$ in $w$ is a maximal occurrence of a substring of $w$ having abelian period $\mathcal{P}$. Our main result is an online algorithm that, given a word $w$ of length $n$ over an alphabet of cardinality $\sigma$ and a Parikh vector $\mathcal{P}$, returns all the abelian runs of period $\mathcal{P}$ in $w$ in time $O(n)$ and space $O(\sigma+p)$, where $p$ is the norm of $\mathcal{P}$, i.e., the sum of its components. We also present an online algorithm that computes all the abelian runs with periods of norm $p$ in $w$ in time $O(np)$, for any given norm $p$. Finally, we give an $O(n^2)$-time offline randomi…

Abelian Repetitions in Sturmian Words

We investigate abelian repetitions in Sturmian words. We exploit a bijection between factors of Sturmian words and subintervals of the unitary segment that allows us to study the periods of abelian repetitions by using classical results of elementary Number Theory. We prove that in any Sturmian word the superior limit of the ratio between the maximal exponent of an abelian repetition of period $m$ and $m$ is a number $\geq\sqrt{5}$, and the equality holds for the Fibonacci infinite word. We further prove that the longest prefix of the Fibonacci infinite word that is an abelian repetition of period $F_j$, $j>1$, has length $F_j(F_{j+1}+F_{j-1} +1)-2$ if $j$ is even or $F_j(F_{j+1}+F_{j-1}…

Grand Est, Meurthe-et-Moselle, Allamont, L’Enfer : une occupation rurale tardo-laténienne et antique dans la plaine de la Woëvre, rapport de diagnostic archéologique, Metz : INRAP GE, 2022, 103 p.

Algorithms for Computing Abelian Periods of Words

Constantinescu and Ilie (Bulletin EATCS 89, 167--170, 2006) introduced the notion of an \emph{Abelian period} of a word. A word of length $n$ over an alphabet of size $\sigma$ can have $\Theta(n^{2})$ distinct Abelian periods. The Brute-Force algorithm computes all the Abelian periods of a word in time $O(n^2 \times \sigma)$ using $O(n \times \sigma)$ space. We present an off-line algorithm based on a $\sel$ function having the same worst-case theoretical complexity as the Brute-Force one, but outperforming it in practice. We then present on-line algorithms that also enable to compute all the Abelian periods of all the prefixes of $w$.