# Evolution and trade-off dynamics of functional load

Erich Round, Rikker Dockum and Robin J. Ryder

(December 2021)

###### Abstract

Function Load (FL) quantifies the contributions by phonological contrasts to
distinctions made across the lexicon. Previous research has linked
particularly low values of FL to sound change. Here we broaden the scope of
enquiry into FL, to its evolution at all values. We apply phylogenetic methods
to examine the diachronic evolution of FL across 90 languages of the Pama-
Nyungan (PN) family of Australia. We find a high degree of phylogenetic signal
in FL. Though phylogenetic signal has been reported for phonological
structures, such as phonotactics, its detection in measures of phonological
function is novel. We also find a significant, negative correlation between
the FL of vowel length and of the following consonant, that is, a deep-time
historical trade-off dynamic, which we relate to known allophony in modern PN
langauges and compensatory sound changes in their past. The finding reveals a
historical dynamic, similar to transphonologization, which we characterize as
a flow of contrastiveness between subsystems of the phonology. Recurring
across a language family which spans a whole continent and many millennia of
time depth, our finding provides one of the most compelling examples yet of
Sapir’s ’drift’ hypothesis, of non-accidentally parallel development in
historically related languages.

Keywords: functional load; linguistics; phonology; phylogenetic signal;
phylogenetic correlation; sound change; Pama-Nyungan; transphonologization;
parallel evolution; Sapir’s drift

##  1 Introduction

Function Load (FL) quantifies the contribution of specific phonological
contrasts to distinctions made in the lexicon of a language [1, 2, 3]. In
English for example, the phonemes /t/ and /d/ contrast, and thus there exist
phonological strings in English, including whole words, which differ only by
virtue of one containing /t/ in a position where the other contains /d/.
Examples include time/dime, welter/welder and hit/hid. At a conceptual level,
the FL of the {/t/,/d/} contrast in English is the degree to which
distinctions in the English lexicon are enabled by that contrast, or
conversely, the degree to which they would be conflated if /t/ and /d/ were
merged into a single category.

A classic operationalization of FL by Hockett [2] is in terms of entropy [4].
Hockett’s definition makes reference to domains, $\mathcal{D}$, which could be
words, morphemes, syllables, or any kind of substring composed of phonemes. In
a language $\mathscr{L}$, the lexicon $\Lambda$ will contain a set
$\mathbf{S}_{\mathcal{D},\Lambda}$ of unique phonological string types, $s$,
which comprise a domain of type $\mathcal{D}$. The entropy of domain
$\mathcal{D}$ in lexicon $\Lambda$ is:

$H_{\mathcal{D},\Lambda}=-\sum_{s\in\mathbf{S}_{\mathcal{D},\Lambda}}\text{P}(s).\log_{2}\text{P}(s)$
(1)

The FL of a phonological contrast $\phi$ in lexicon $\Lambda$ and domain
$\mathcal{D}$ is the difference between two entropy measures: the entropy of
domain $\mathcal{D}$ in lexicon $\Lambda$, and of domain $\mathcal{D}$ in an
altered lexicon $\Lambda^{\prime}_{\phi}$, created by collapsing the contrast
$\phi$ in $\Lambda$:

$f(D,\Lambda,\phi)=H_{\mathcal{D},\Lambda}-H_{\mathcal{D},\Lambda^{\prime}_{\phi}}$
(2)

A phonological contrast, $\phi$, may refer to distinctions between the members
of a single set of phonemes, such as between two phonemes {/t/, /d/} or
between four phonemes {/t/, /d/, /s/, /z/}. Alternatively, it may refer to a
collection of multiple, parallel distinctions, defined by a collection of sets
and the distinctions within each of them. For instance, a contrast between
voiced and voiceless stop consonants could refer to the distinctions within
each of the three sets in the collection {{/p/, /b/}, {/t/, /d/}, {/k/, /g/}}
and a contrast between the places of articulation of stop consonants could
refer to the distinctions within each of the two sets in the collection {{/p/,
/t/, /k/}, {/b/, /d/, /g/}}. In all cases, the altered lexicon
$\Lambda^{\prime}_{\phi}$ is obtained by taking each individual set and
replacing the phonemes within it with a single phonemic symbol which is
distinct from all other phonemic symbols in $\mathscr{L}$.

###  1.1 Functional Load and sound change

Languages undergo mutational changes, known as sound change, in which sounds
may change from one phonemic category to another [5]. The term unconditioned
merger refers to sound changes which cause two or more previously distinct
phonemic categories to become conflated into one. Conditioned mergers are when
conflation affects the phonemes only in certain contexts. FL has attracted
attention as a possible explanatory factor in the incidence of mergers, with
recent evidence supporting a much older conjecture that contrasts with low FL
are more prone to merge than contrasts with high FL [1, 6, 7, 8, 9]. Debate is
ongoing over which operationalizations of FL provide the greatest predictive
power [8] and what kinds of mergers FL predicts [10]. Whether it has used
entropy-based definitions of FL or not, most research to date has focused on
domains $\mathcal{D}$ that are words.

When a contrast undergoes unconditional merger, its FL falls to zero. The fact
that all else equal, contrasts with low FL values are more likely to fall to
zero than contrasts with higher FL values, can be viewed as an expected
outcome of any system in which FL evolves over time according to a stochastic
process in which small changes are more likely than large ones. Such a system
leads to other predictions too. A novel contribution of this study is to test
such predictions, and thus to broaden the scope of research into FL.

Here we examine FL from a phylogenetic perspective, investigating how FL
evolves over time in the large, Pama-Nyungan (PN) language family of
Australia. PN languages extend across 90% of the Australian mainland and the
time depth of the family is estimated at around 5–6,000 years Before Present
[11, 12, 13]. In Study 1, we apply standard techniques to show that FL
contains significant phylogenetic signal, which is to say, the variance in the
FL data across the PN language family is consistent with the hypothesis that
FL has evolved along the PN tree according to stochastic process that is well
approximated by a Brownian motion.

###  1.2 Contrastiveness in Pama-Nyungan VC strings

In many PN languages, an inverse correlation has been observed between
phonemic vowel length and the phonetic duration of a following consonant [14,
15, 16, 17, 18]. This is particularly so for vowels in the first syllable of
words, referred to as tonic vowels. Here we focus on tonic vowels and single,
intervocalic consonants which follow them. Post-tonic single consonants which
follow phonemically short vowels and which have phonetically longer durations
in some language also exhibit additional phonetic properties associated with
long duration, such as more complete closure and passive devoicing of stops,
and pre-stopping of nasals and laterals. Conversely, post-tonic single
consonants which follow phonemically long vowels and which have phonetically
shorter durations may exhibit more voicing and lenition of stops, and the
absence of pre-stopping in laterals and nasals [19, 14, 15, 20, 21]. Examples
of allophonic conditioning of this kind are cited in Table 1.

Table 1: Examples of allophony in post-tonic consonants, conditioned by phonemic length of the tonic vowel. Key: V_ after phonemically short vowel, VV_ after phonemically long vowel. See references for additional details in the conditioning of allophony. Language (subgroup) | Consonants | V_ | VV_
---|---|---|---
Djambarrpuyngu (Yolngu) [18] | Consonants | longer | shorter
Wik (Middle Paman) [22] | Stops | tenser | laxer
Kugu Nganhcara (Middle Paman) [23] | Voiced stops | stop | fricative
Nukunu (Thura-Yura) [24] | Nasals, Laterals | prestopped | plain
Yadhaykenu (Nothern Paman) [25] | Laterals | plain | flapped

A general fact about sound change is that when two phonemes merge, it is
possible for phonetic correlates of the original contrast, which are
manifested in other segments, to remain in place and become contrastive. This
has occurred in multiple branches of PN, as phonemic vowel length is lost
while its erstwhile phonetic correlates on the following consonant remain and
become distinctive. Examples are cited in Table 2.

Table 2: Examples of post-tonic consonant contrasts created upon the loss of length distinctions in tonic vowels of Pama-Nyungan languages. Key: T short stop, TT long stop, D voiced stop, Z spirant, N nasal, NN long nasal, DN prestopped nasal, ND nasal+stop, L lateral, DL prestopped lateral, V_ after erstwhile short vowel, VV_ after erstwhile long vowel. See references for additional details and conditioning of the tabulated sound changes. Language (subgroup) | Original C | V_ | VV_
---|---|---|---
Warumungu (Warunmungic) [26] | T | TT | T
Wik-Muminh (Middle Paman) [22] | T (non-apical) | T | D
Northern Paman subgroup [27, 28, 25] | T (non-apical) | T | Z
Lamalama, Umbuygamu (Lamalamic) [29] | /k/ | /k/ | /h/
Kugu Mumminh (Middle Paman) [26] | N | NN | N
Arandic subgroup [30, 31] | N | DN | N
Walangama (Norman Paman) [32] | N | DN | N
Olgolo (Southwest Paman) [33] | N | DN | N
Lamalama (Lamalamic) [29] | N | ND | N
Rimanggudinhma (Lamalamic) [29] | N | D | N
Thura-Yura subgroup [24] | L | DL | L

In the cases cited in Table 2, the complete loss of vowel length is associated
with an increase in contrastiveness in following consonants. In such cases,
the FL of the vowel length contrast falls (to zero) while the FL of the
following consonant position rises. Consequently, there is a trade-off
relationship between between $FL_{V}$, the FL of vowel length, and $FL_{C}$,
the FL of the manner of articulation (included voicing and fortition) of the
following consonant. This trade-off is of a very specific kind, in which the
complete merger of all short/long vowel pairs reduces $FL_{V}$ to zero. We
will refer to this as a trade-off with contrast collapse. Other trade-offs are
possible, however. If a length contrast is lost only in certain vowels, and/or
only in certain contexts, then $FL_{V}$ would fall (though not to zero) and in
such cases, $FL_{C}$ could be expected to rise if consonants become more
contrastive when they follow the vowels which do merge. This scenario would
give rise to a second kind of trade-off. We will refer to this second kind as
a trade-off with contrast maintenance.

In Study 2, we test the hypothesis that $FL_{V}$ and $FL_{C}$ are negatively
correlated in PN. Recall that $FL_{C}$ relates to post-tonic consonants and is
defined in terms of their manner of articulation. We expect $FL_{C}$ to
correlate negatively with $FL_{V}$ for the phonetic and historical reasons
introduced above. We also examine $FL_{P}$, the FL of post-tonic consonants’
place of articulation. Because research on PN languages has identified no
particular association between vowel length and consonant place, our
hypothesis is that $FL_{P}$ will show no significant correlation with
$FL_{V}$.

##  2 Materials and Methods

###  2.1 Functional load data in Pama-Nyungan

FL was estimated for vowel length ($FL_{V}$), consonant manner ($FL_{C}$) and
consonant place ($FL_{P}$) in domains comprised of a tonic vowel followed by a
single, intervocalic consonant, in a set of $90$ Pama-Nyungan languages listed
in Appendix A. FL estimates were based on lexical datasets, which contained
between 208 and 3215 tokens of the domains of interest (mean 774, median 605).
The $90$ languages studied were selected by taking the $112$ PN lexicons
studied in [34] and removing all whose $FL_{V}$ was zero or which had fewer
than 200 domain tokens. A tree of these $90$ languages is shown in Figure 1.

Figure 1: Pama-Nyungan tree containing the 90 languages used in this study.
Displayed here is a single, maximum clade credibility tree, i.e., the one tree
within the 1000-tree sample which most adequately represents the highest-
probability subgroups in all of the trees of the sample.

When classifying vowels as short or long, we regarded sequences of two
adjacent short vowels as one long vowel, and sequences of /uwu/ and /iji/ as
long vowels, since a tradition followed in some Australianist analysis is to
represent long high vowels [u:] and [i:] as phonemic vowel-glide-vowel
sequences (e.g. [35, p.24], [36, p.91]).

Phonemically long or geminate consonants, and phonemically pre-stopped
sonorants, have been analysed as both mono- and bi-segmental units in the
Australianist literature [37]. Here, we were guided by the kinds of historical
developments that we wish to study, and classed them as single segments.

The FL data obtained for the $90$ PN languages is reported in Appendix A.

###  2.2 Phylogenetic analysis

Because languages are related to one another, it is not statistically valid to
treat cross-linguistic observations as independent [38]. Quantitative
phylogenetic methods [39] take phylogenetic relatedness into account in a
principled and statistically sound manner. Our two studies use phylogenetic
techniques in order to make valid inferences from the cross-linguistic FL data
in PN.

Study 1 assesses the degree of phylogenetic signal in $FL_{V}$, $FL_{C}$ and
$FL_{P}$. Phylogenetic signal is a measure of genealogical structuration in
the variance in the data. Here we measure phylogenetic signal using a widely
employed statistic, Blomberg’s $K$ [40, 34]. Intuitively, Blomberg’s $K$
measures how well the observed distribution of FL values accords with the
hypothesis that they have evolved along the PN family tree according to a
stochastic, Brownian motion process.

To calculate phylogenetic signal, reference must be made to a PN family tree,
however in linguistics there is uncertainty about the details of this tree.
Here we employ a standard approach to accounting for phylogenetic uncertainty
of this kind, by measuring phylogenetic signal with respect to not one tree,
but a sample of 1000 highly-likely family trees [41]. This generates 1000
estimates of $K$, providing a distribution describing its likely value.
Blomberg’s $K$ takes a value of $1$ if the data accord perfectly with the
reference tree and a minimum value of $0$ if the data is perfectly randomly
distributed. Values in excess of $1$ are possible if FL data values are highly
clumped within subgroups of the family.

Study 2 examines the phylogenetic Pearson’s correlation [42] between $FL_{V}$
and $FL_{C}$ and between $FL_{V}$ and $FL_{P}$. This test is conceptually
parallel to a regular Pearson’s correlation, but also takes into account the
specific kinds of non-independence caused by genealogical relationships
between the languages. As with our estimate of phylogenetic signal, we take
into account phylogenetic uncertainty by performing the correlation test in
reference to the sample of 1000 highly-likely trees.

We used 1000 dated phylogenetic trees from the posterior distribution provided
by Bowern [41]; these trees were reconstructed using cognate data. We assume
that $(FL_{V},FL_{C},FL_{p})$ evolves along a phylogeny following a Brownian
motion. We used the phytools R package [43] to estimate the covariance matrix
of the Brownian motion on each tree in the sample, giving a sample from the
posterior distribution of Pearson’s $r$ correlation. The $p$-values reported
were computed using the posterior mean estimates.

##  3 Results

Phylogenetic signal as measured by Blomberg’s $K$ was very close to $1$ for
$FL_{V}$, $FL_{C}$ and $FL_{P}$, as shown in Table 3. To place these $K$
values in context, Macklin-Cordes et al. [34] examine the lexical Markov chain
transition probabilities of biphones (two-segment sequences) in PN and find
mean $K$ values of $0.54$, or mean $K$ of $0.59$ when segments were binned
into groups by place or manner of articulation; Macklin-Cordes and Round [38]
examine relative frequencies of dental versus palatal consonants in word
initial and intervocalic positions in PN and find mean $K$ values from $0.78$
to $1.32$ word-initially and from $0.34$ to $0.70$ intervocalically; Dockum
[44] examines phoneme frequencies and biphone Markov chain transition
probabilities in languages of the Tai family and finds mean $K$ of $0.71$ and
$0.68$ respectively. Further afield, Blomberg et al. [40] examined 121
biological traits of a wide variety of plant and animal organisms, finding
mean $K$ of $0.35$ for behavioral traits, $0.54$ for physiology and $0.83$ for
traits related to body size. Taken in this context, our results suggest that
the evolution of FL is very well modelled by a stochastic, Brownian motion
process along the PN tree.

Table 3: Phylogenetic signal in $FL_{V}$, $FL_{C}$ and $FL_{P}$, measured using Blomberg’s $K$ and a sample of 1000 reference PN trees. Functional load measure | mean $K$ | std.dev of $K$
---|---|---
FL of tonic vowel length ($FL_{V}$) | $0.972$ | $0.036$
FL of post-tonic consonant manner ($FL_{C}$) | $0.956$ | $0.038$
FL of post-tonic consonant place ($FL_{P}$) | $0.960$ | $0.030$

One consequence of the high levels of phylogenetic signal found in FL, is that
statistical analysis, such as the measurement of correlations, should be
carried out using phylogenetic comparative methods [38]. Phylogenetic
Pearson’s correlation (Table 4) was significant and negative between $FL_{V}$
and $FL_{C}$, but did not reach significance between $FL_{V}$ and $FL_{P}$, in
accordance with our hypotheses.

Table 4: Phylogenetic Pearson’s correlation between $FL_{V}$ and $FL_{C}$ and $FL_{P}$. Functional load measures | $r$ | 95% interval | $p$
---|---|---|---
$FL_{V}$ versus $FL_{C}$ | $-0.28$ | $[-0.31\ -0.26]$ | $0.006$
$FL_{V}$ versus $FL_{P}$ | $0.03$ | $[0.001\ 0.055]$ | $0.778$

##  4 Discussion

Our study examines language diachrony at a statistical level. By doing so, it
contributes to a more precise, quantitative characterization of diachronic
typology. Specifically, here we have studied the historical dynamics of FL,
which is a quantitative characterization of the contribution of specific
contrasts to distinctiveness in the lexicon. We have established the potential
for these contributions to be correlated with one another, evolving in a
statistically non-independent fashion across almost a hundred languages and
thousands of years of history. Moreover, we have demonstrated that all values
of FL, not only those close to zero, exhibit interesting historical dynamics
deserving of more investigation. In this discussion section we select three
points that warrant additional emphasis.

###  4.1 High degree of phylogenetic signal in FL

Phylogenetic signal has recently been shown to be present in phonotactic
biphone frequencies, phoneme frequencies, and contextual ratios of places of
articulation [45, 44, 46, 34, 38]. These studies reveal that the frequencies
of phonological structures pattern with genealogy. Here we find a high level
of phylogenetic signal also in FL, that is, in the contrastive function that
phonological structures serve. Interestingly, we find that phylogenetic signal
in the FL measures examined here is very close to $1$, and closer than the
values found in studies of phonological structures. Why this is so, and how
far the finding generalizes, is not yet apparent to us, and deserves further
study.

###  4.2 Transphonologization and the flow of contrastiveness

Transphonologization [47] (see also cheshirization [48]) is a term given to
sound changes in which a contrastive function is preserved, but the locus of
the contrast – the segments or features which instantiate it – changes. Here
we have studied a closely related phenomenon, in which contrasts do not
necessarily disappear or emerge in their entirety, but the relative
contrastive workload of them (their FL) does shift from one to another. One
way to view this phenomenon is in terms of a diachronic flow of FL from one
contrast to another (cf [49]). The fact that we are able to quantitatively
detect the presence of this flow of contrastiveness through a language family
as large and old as PN suggests the potential of new avenues for investigating
the dynamic flow of contrastiveness through phonological systems as they
evolve over time.

One question that arises, is whether our findings in PN might reflect some
strong preference in language for the conservation of contrastiveness, in
which case the flow of FL from one contrast to another might be regarded as an
automatic consequence of one contrast undergoing a significant decrease in FL.
Although our results alone cannot answer this question, we doubt that such a
principle exists in any strong form. Certainly, in many mergers, the overall
contrastive capacity of a language is simply reduced, as the FL of one
contrast falls but no other FL rises to balance it. In the case of PN tonic
vowels and post-tonic consonants, we suggest that the cause of recurrent
historical flow of FL lies in particular phonetic factors that are common
across PN languages: a synchronic correlation between phonetic tonic vowel
duration and phonetic post-tonic consonant manner, even in systems in which
only the vowel-durational aspect is tied to a synchronic phonemic contrast;
when the phonetic vowel-durational differences are neutralized diachronically,
causing the phonemic vowel length contrasts to collapse, the phonetic manner
differences – which still correlate with the same lexical distinctions which
vowel length had signalled – become phonemic. On this view, it is the
phonetics of the vowel-consonant strings that furnish the conditions for a
natural flow of FL from vowel to consonant.

###  4.3 On Sapir’s ’drift’: the non-accidental, parallel evolution of related
languages

It is a century now since the appearance in print of Edward Sapir’s hypothesis
that languages undergo parallel grammatical evolution for several centuries
after they split [50]. Providing anything more than anecdotal evidence in
support of Sapir’s hypothesis has long been difficult [51, 52, 53], and some
apparent cases may be due to language contact [54, 55]. Dunn et al. [56] used
phylogenetic methods to show different language families undergoing different
patterns of word order evolution, however the study did not produce an
identifiable cause for those patterns.

Ideally, evidence in support of Sapir’s drift should not be anecdotal, but
rather be statistically significant across a language family; it should not be
reducible to the effects of language contact; and it should be relatable to an
identifiable cause. The current study meets these three criteria. It detects
parallel changes in FL that are instantiated statistically across $90$
languages, within the PN family whose time depth is estimated at around
5–6,000 years [11, 12, 13], thus the evidence is not anecdotal. The data
pattern tightly with phylogeny, so are unlikely to be due to contact. And we
have identified a causal basis for them, in the common phonetics of PN tonic
vowel-consonant sequences. Thus, we believe our results to be one of the
fullest confirmations yet, that Sapir’s conjecture was essentially correct:
that under the right circumstances, languages can undergo parallel grammatical
evolution, not merely for centuries but for millennia.

It has been suggested by Joseph [57] that drift in phonology may be due to a
narrowing of the range of variation inherited from a proto-language. In the PN
changes described here, however, the flow of FL from vowel length to consonant
manner is not due to any narrowing of variation in FL in proto-PN (indeed it
is not entirely clear what it should mean for FL to have a range of
variation). Nor, when the PN developments are viewed in terms of phonological
substance, are they a matter merely of narrowing variation. Although contrasts
in vowel length are lost, new variation is introduced in the inventory of
contrastive consonant manners and into the set of relationships that can hold
between the length of a tonic vowel and the manner of post-tonic consonants.

In reality, Joseph’s proposal would appear to reduce to a fact, well-
recognised in evolutionary biology, that incomplete lineage sorting (i.e., the
inheritance of variation from a proto-taxon into its descendant) can result in
the appearance of convergent evolution [58]. But this does not entail that all
convergent evolution is due to incomplete lineage sorting (see also [59]).
Another important source can be the existence of dependencies with a system
which are inherited along with its substance [60], and which will favour
certain outcomes over others in descendent systems, as has been observed in
protein evolution for example [61]. In PN, certain phonetic dependencies
between tonic vowel length and post-tonic consonant manners were inherited
alongside the phonological substance itself. In the descendent systems, in the
event that vowel length was lost, the inherited dependencies favoured the rise
of new, contrastive consonant manners.

##  5 Conclusions

This paper joins a growing body of work on the application of computational
phylogenetic methods to phonological data. It also represents the first
phylogenetic study of FL. We show that there is significant phylogenetic
signal in FL, which has implications for a better understanding of the
dynamics of sound change. Further, we show that the FL of tonic vowels and and
post-vowel consonants are negatively correlated in PN, and that this maps
closely to a sample of highly probably PN family trees. We also introduce the
idea of the flow of contrastiveness between subsystems of the phonology in
different languages, which is connected to the concept of
transphonologization, and claim that this represents a concrete example of
Sapir’s drift.

Setting our gaze beyond PN, although not all sound changes are associated with
phonetic conditions that promote the flow of FL, there are many do appear to
be, and it will be valuable to apply the methods we have introduced here to
study them also. In time, this may lead to a more general understanding of how
FL can flow within phonological systems over long time horizons. Promising
future applications of our approach include the investigation of other
suspected diachronic trade-offs such as the rise of phonemic tone and register
(such as contrastive phonation) in Southeast Asia, tied to losses of
consonantal laryngeal distinctions [62, 63, 64, 3].

##  6 Appendix A. Functional load data

Table 5: Functional load estimates and number of observations on which they are based in Pama-Nyungan languages A–M. Language | $FL_{V}$ | $FL_{C}$ | $FL_{P}$ | N
---|---|---|---|---
Adnyamathanha | 0.007 | 2.299 | 1.693 | 1424
Bandjalang | 0.388 | 1.211 | 0.846 | 864
Batyala | 0.153 | 1.205 | 0.840 | 303
Bidyara-Gungabula | 0.020 | 1.044 | 1.439 | 466
Bilinarra | 0.024 | 1.601 | 1.385 | 1071
Biri | 0.011 | 1.047 | 1.308 | 387
Bularnu | 0.010 | 1.814 | 1.532 | 514
Dhangu | 0.537 | 1.306 | 1.204 | 222
Dhayyi | 0.620 | 1.335 | 1.356 | 636
Djabugay | 0.051 | 1.269 | 1.161 | 641
Djapu | 0.552 | 1.426 | 1.456 | 563
Djinang | 0.008 | 1.757 | 1.276 | 1459
Duungidjawu | 0.359 | 0.932 | 0.913 | 340
Dyirbal | 0.019 | 1.207 | 1.226 | 339
Gamilaraay | 0.476 | 1.092 | 0.667 | 619
Githabul | 0.383 | 1.209 | 0.850 | 863
Gumbaynggir | 0.682 | 1.142 | 0.561 | 260
Gunya | 0.086 | 1.675 | 1.879 | 421
Gupapuyngu | 0.703 | 1.660 | 1.390 | 1426
Gurindji | 0.141 | 1.684 | 1.400 | 2783
Guwamu | 0.152 | 0.972 | 1.283 | 284
Jaru | 0.146 | 1.651 | 1.239 | 1459
Jiwarli | 0.107 | 1.500 | 1.545 | 747
Kalkatungu | 0.174 | 1.451 | 1.667 | 937
Karajarri | 0.011 | 1.585 | 1.372 | 1217
Kariyarra | 0.008 | 1.512 | 1.342 | 252
Kartujarra | 0.103 | 1.598 | 1.629 | 526
Kok Nar | 0.024 | 1.025 | 1.038 | 213
Koko Bera | 0.008 | 1.125 | 1.144 | 428
Kugu Nganhcara | 0.231 | 1.201 | 1.524 | 359
Kukatj | 0.492 | 1.371 | 1.262 | 422
Kukatja | 0.177 | 1.692 | 1.556 | 2339
Kuku Yalanji | 0.006 | 1.206 | 1.064 | 1070
Kurrama | 0.157 | 1.475 | 1.333 | 495
Kurtjar | 0.357 | 1.098 | 0.902 | 405
Kuuk Thaayorre | 0.398 | 0.946 | 1.297 | 873
Kuuku Ya’u | 0.822 | 0.968 | 1.827 | 672
Malgana | 0.091 | 1.360 | 1.520 | 208
Mangala | 0.068 | 1.585 | 1.312 | 749
Martuthunira | 0.122 | 1.597 | 1.413 | 633
Mbakwithi | 0.158 | 0.890 | 0.946 | 255
Mirniny | 0.057 | 1.494 | 1.646 | 259
Mudburra | 0.121 | 1.573 | 1.362 | 509
Muruwari | 0.299 | 1.303 | 1.239 | 873
Table 6: Functional load estimates and number of observations on which they are based in Pama-Nyungan languages N–Z. Language | $FL_{V}$ | $FL_{C}$ | $FL_{P}$ | N
---|---|---|---|---
Ngaanyatjarra | 0.308 | 1.657 | 1.544 | 1125
Ngadjumaya | 0.279 | 1.581 | 1.525 | 512
Ngamini | 0.009 | 1.658 | 1.628 | 453
Ngardily | 0.044 | 1.541 | 1.419 | 274
Ngarinyman | 0.050 | 1.609 | 1.371 | 870
Ngarla | 0.054 | 1.650 | 1.522 | 940
Ngarluma | 0.009 | 1.550 | 1.511 | 633
Nhanta | 0.221 | 1.617 | 1.983 | 427
Nukunu | 0.230 | 1.885 | 1.572 | 282
Nyamal | 0.011 | 1.668 | 1.585 | 574
Nyangumarta | 0.056 | 1.637 | 1.530 | 1002
Nyawaygi | 0.448 | 0.917 | 0.847 | 339
Olkola | 0.009 | 1.897 | 1.525 | 992
Paakantyi | 0.482 | 1.310 | 1.586 | 748
Pakanh | 0.482 | 0.757 | 1.702 | 379
Panyjima | 0.033 | 1.526 | 1.537 | 327
Payungu | 0.120 | 1.443 | 1.487 | 514
Pintupi-Luritja | 0.257 | 1.620 | 1.498 | 3065
Purduna | 0.186 | 1.484 | 1.641 | 540
Ritharrngu | 0.528 | 1.594 | 1.285 | 841
Thalanyji | 0.113 | 1.412 | 1.640 | 467
Tharrgari | 0.101 | 1.808 | 1.468 | 371
Umpila | 0.726 | 0.895 | 1.792 | 473
Wailwan | 0.441 | 1.112 | 0.699 | 489
Wajarri | 0.096 | 1.555 | 1.585 | 787
Wakaya | 0.026 | 1.478 | 1.347 | 696
Walmajarri | 0.075 | 1.695 | 1.531 | 2361
Wangkatja | 0.243 | 1.647 | 1.549 | 1290
Wangkumara | 0.037 | 1.784 | 1.492 | 480
Wargamay | 0.466 | 1.166 | 1.224 | 470
Warlmanpa | 0.032 | 1.769 | 1.546 | 603
Warlpiri | 0.078 | 1.717 | 1.549 | 3215
Warluwarra | 0.062 | 1.625 | 1.609 | 731
Warnman | 0.034 | 1.619 | 1.557 | 607
Warriyangga | 0.049 | 1.463 | 1.557 | 273
Wik Mungkan | 0.579 | 0.911 | 1.733 | 1411
Yadhaykenu | 0.118 | 1.390 | 1.474 | 385
Yalarnnga | 0.013 | 1.479 | 1.596 | 397
Yannhangu | 0.527 | 1.621 | 1.351 | 952
Yanyuwa | 0.028 | 1.534 | 1.477 | 1351
Yaygirr | 0.627 | 1.490 | 1.004 | 658
Yidiny | 0.014 | 1.240 | 1.084 | 964
Yindjibarndi | 0.127 | 1.476 | 1.212 | 492
Yinhawangka | 0.080 | 1.654 | 1.678 | 773
Yulparija | 0.078 | 1.657 | 1.582 | 1234
Yuwaalaraay | 0.610 | 1.185 | 0.807 | 1109

## References

  * Martinet [1952] André Martinet.  Function, structure, and sound change.  _Word_ , 8(1):1–32, 1952.
  * Hockett [1967] Charles F Hockett.  The quantification of functional load.  _Word_ , 23(1-3):300–320, 1967.
  * Surendran and Niyogi [2006] Dinoj Surendran and Partha Niyogi.  Quantifying the functional load of phonemic oppositions, distinctive features, and suprasegmentals.  _Amsterdam studies in the theory and history of linguistic science series 4_ , 279:43, 2006.
  * Shannon [1948] Claude Elwood Shannon.  A mathematical theory of communication.  _Bell System Technical Journal_ , 27:379–423, 623–565, 1948.  Publisher: ACM New York, NY, USA.
  * Garrett [2015] Andrew Garrett.  Sound change.  In Claire Bowern and Bethwyn Evans, editors, _The Routledge handbook of historical linguistics_ , pages 227–248. Routledge, London, 2015.
  * Silverman [2010] Daniel Silverman.  Neutralization and anti-homophony in Korean.  _Journal of linguistics_ , 46(2):453–482, 2010\.
  * Bouchard-Côté et al. [2013] Alexandre Bouchard-Côté, David Hall, Thomas L. Griffiths, and Dan Klein.  Automated reconstruction of ancient languages using probabilistic models of sound change.  _Proceedings of the National Academy of Sciences_ , 110(11):4224–4229, 2013.
  * Wedel et al. [2013] Andrew Wedel, Abby Kaplan, and Scott Jackson.  High functional load inhibits phonological contrast loss: A corpus study.  _Cognition_ , 128(2):179–186, 2013.
  * Babinski and Bowern [2018] Sarah Babinski and Claire Bowern.  Mergers in Bardi: Contextual probability and predictors of sound change.  _Linguistics Vanguard_ , 4(s2), 2018.
  * Ceolin [2020] Andrea Ceolin.  On Functional Load and its Relation to the Actuation Problem.  _University of Pennsylvania Working Papers in Linguistics_ , 26(2):Article 6, 2020.  URL https://repository.upenn.edu/pwpl/vol26/iss2/6.
  * McConvell [1996] Patrick McConvell.  Backtracking to Babel: the chronology of Pama-Nyungan expansion in Australia.  _Archaeology in Oceania_ , 31(3):125–144, 1996\.
  * Bowern and Atkinson [2012] Claire Bowern and Quentin Atkinson.  Computational phylogenetics and the internal structure of Pama-Nyungan.  _Language_ , 88(4):817–845, 2012.
  * Bouckaert et al. [2018] Remco R. Bouckaert, Claire Bowern, and Quentin D. Atkinson.  The origin and expansion of Pama–Nyungan languages across Australia.  _Nature ecology & evolution_, 2:741–649, 2018.
  * Butcher [1999] A. R. Butcher.  What speakers of Australian Aboriginal languages do with their velums and why: the phonetics of the nasal/oral contrast.  In J. J. Ohala, Y. Hasegawa, M. Ohala, D. Granville, and A. C. Bailey, editors, _Proceedings of the XIVth International Congress of the Phonetic Sciences_ , pages 479–482. International Congress of the Phonetic Sciences, 1999.
  * Tabain et al. [2004] Marija Tabain, Gavan Breen, and Andrew Butcher.  VC vs CV syllables: a comparison of Aboriginal languages with English.  _Journal of the International Phonetic Association_ , 34(2):175–200, 2004.
  * Butcher [2006] Andrew Butcher.  Australian Aboriginal languages: consonant-salient phonologies and the ’place-of-articulation imperative’.  In J. M. Harrington and M. Tabain, editors, _Speech production: models, phonetic processes and techniques_ , pages 187–210. Psychology Press, New York, 2006.
  * Fletcher and Butcher [2014] Janet Fletcher and Andrew Butcher.  Sound patterns of Australian languages.  In Harold Koch and Rachel Nordlinger, editors, _The languages and linguistics of Australia: A comprehensive guide_ , pages 91–138. Mouton de Gruyter, Berlin, 2014.
  * Jepson and Stoakes [2015] Kathleen Jepson and Hywel Stoakes.  Vowel duration and consonant lengthening in Djambarrpuyngu.  In _Proceedings of the 18th International Congress of Phonetic Sciences_ , Glasgow, 2015. ICPhS.
  * Hercus [1972] Luise Anna Hercus.  The pre-stopped nasal and lateral consonants of Arabana-Wangganguru.  _Anthropological Linguistics_ , 14(8):293–305, 1972.
  * Loakes et al. [2008] Deborah Loakes, Andrew Butcher, Janet Fletcher, and Hywel Stoakes.  Phonetically prestopped laterals in Australian languages: a preliminary investigation of Warlpiri.  In J. Fletcher, D. Loakes, R. Goecke, D. Burnham, and M. Wagner, editors, _Proceedings of the 9th Annual Conference of the International Speech Communication Association (Interspeech 2008), incorporating the 12th Australasian International Conference on Speech Science and Technology (SST2008), Brisbane, Australia, 22-26 September 2008_. Causal Production, Brisbane, 2008.
  * Round [2014] Erich R. Round.  Prestopping of nasals and laterals is only partly parallel.  In Rob Pensalfini, Diana Guillemin, and Myfany Turpin, editors, _Language Description Informed by Theory_ , pages 81–95. John Benjamins, Amsterdam, 2014.
  * Hale [1976a] Kenneth L. Hale.  Wik reflections of Middle Paman phonology.  In Peter Sutton, editor, _Languages of Cape York_ , pages 50–60. AIAS, 1976a.
  * Smith and Johnson [2000] Ian Smith and Steve Johnson.  Kugu Nganhcara.  In R. M. W. Dixon and Barry J. Blake, editors, _Handbook of Australian Languages_ , volume 5, pages 357–507. Oxford University Press, Melbourne, Oxford, 2000.  ISBN 0-19-554998-8.
  * Hercus [1992] Luise A. Hercus.  _A Nukunu dictionary_.  Department of Linguistics, Australian National University, Canberra, 1992\.
  * Crowley [1983] Terry Crowley.  Uradhi.  In R. M. W. Dixon and Barry J. Blake, editors, _Handbook of Australian languages_ , volume 3, pages 307–428. John Benjamins, Amsterdam, 1983\.
  * Alpher [2022] Barry J. Alpher.  Sound change.  In Claire Bowern, editor, _Oxford guide to Australian languages_. Oxford University Press, Oxford, 2022.
  * Hale [1976b] Kenneth L. Hale.  Phonological developments in particular Northern Paman languages.  In Peter Sutton, editor, _Languages of Cape York_ , pages 7–40. AIAS, Canberra, 1976b.
  * Hale [1976c] Kenneth L. Hale.  Phonological developments in a Northern Paman language: Uradhi.  In Peter Sutton, editor, _Languages of Cape York_ , pages 41–49. AIAS, Canberra, 1976c.
  * Verstraete [2018] Jean-Christophe Verstraete.  Lamalamic Root Structure: Erosion and Expansion.  _Australian Journal of Linguistics_ , 38(3):360–394, 2018.
  * Koch [1997] Harold J. Koch.  Pama-Nyungan reflexes in the Arandic languages.  In D. Tryon and M. Walsh, editors, _Boundary rider: essays in honour of Geoffrey O’Grady_ , pages 271–302. Pacific Linguistics, 1997.
  * Koch [2001] Harold Koch.  Basic vocabulary of the Arandic languages: from classification to reconstruction.  In Jane Simpson, David Nash, Mary Laughren, Peter Austin, and Barry Alpher, editors, _Forty years on: Ken Hale and Australian languages_ , pages 71–87. Pacific Linguistics, Canberra, 2001.
  * Black [1980] Paul D. Black.  Norman Pama historical phonology.  In _Papers in Australian Linguistics 13_ , pages 181–239. Pacific Linguistics, Canberra, 1980.
  * Dixon [1970] R. M. W. Dixon.  Olgolo syllable structure and what they are doing about it.  _Linguistic Inquiry_ , 1(2):273–276, 1970.
  * Macklin-Cordes et al. [2021] Jayden L Macklin-Cordes, Claire Bowern, and Erich R. Round.  Phylogenetic signal in phonotactics.  _Diachronica_ , 38(2):210–258, 2021.  doi: 10.1075/dia.20004.mac.
  * Austin [1981] Peter K. Austin.  _A Grammar of Diyari, South Australia_.  Number 32 in Cambridge Studies in Linguistics. Cambridge University Press, Cambridge; New York, 1981.  ISBN 0-521-22849-2.
  * McGregor [1990] William McGregor.  _A Functional Grammar of Gooniyandi_.  Number 22 in Studies in Language. John Benjamins, Amsterdam, Philadelphia, 1990.  ISBN 90-272-3025-0.
  * Round [2022] Erich R. Round.  Phonotactics.  In Claire Bowern, editor, _Oxford Guide to Australian languages_. Oxford University Press, Oxford, 2022.
  * [38] Jayden Macklin-Cordes and Erich R Round.  Challenges of sampling and how phylogenetic comparative methods help: With a case study of the Pama-Nyungan laminal contrast.  URL https://zenodo.org/record/4796981.
  * Garamszegi [2014] László Zsolt Garamszegi.  _Modern phylogenetic comparative methods and their application in evolutionary biology: concepts and practice_.  Springer, Heidelberg, 2014.
  * Blomberg et al. [2003] Simon P. Blomberg, Theodore Garland, and Anthony R. Ives.  Testing for phylogenetic signal in comparative data: behavioral traits are more labile.  _Evolution_ , 57(4):717–745, 2003.  doi: 10.1111/j.0014-3820.2003.tb00285.x/abstract.
  * Bowern [2015] Claire Bowern.  Pama-Nyungan phylogenetics and beyond [plenary address].  In _Lorentz Center workshop on phylogenetic methods in linguistics_ , 2015.  doi: 10.5281/zenodo.3032846.
  * Martins and Garland Jr [1991] Emilia P Martins and Theodore Garland Jr.  Phylogenetic analyses of the correlated evolution of continuous characters: a simulation study.  _Evolution_ , 45(3):534–557, 1991.
  * Revell [2012] Liam J Revell.  phytools: an r package for phylogenetic comparative biology (and other things).  _Methods in ecology and evolution_ , 3(2):217–223, 2012.
  * Dockum [2018] Rikker Dockum.  Phylogeny in phonology: How Tai sound systems encode their past.  In _Annual Meeting on Phonology (AMP)_. Linguistic Society of America, 2018.  doi: 10.3765/amp.v5i0.4238.
  * Macklin-Cordes and Round [2015] Jayden Macklin-Cordes and Erich Round.  High-definition phonotactics reflect linguistic pasts.  In _Proceedings of the 6th Conference on Quantitative Investigations in Theoretical Linguistics_ , Tübingen, 2015.  URL http://dx.doi.org/10.15496/publikation-8609.
  * Dockum [2019] Rikker Dockum.  _The tonal comparative method: Tai tone in historical perspective_.  PhD thesis, Yale University, 2019.
  * Haudricourt [1968] André G Haudricourt.  Les doubles transphonologisations simultanées.  In _Actes du XIIe Congrès International de Linguistique et de Philologie romanes, Bucarest_ , pages 315–317, 1968.
  * Matisoff [1991] James A Matisoff.  Areal and universal dimensions of grammatization in Lahu.  In Elizabeth Traugott and Bernd Heine, editors, _Approaches to grammaticalization_ , pages 383–453. John Benjamins, Amsterdam, 1991.
  * Macklin-Cordes and Round [2020] Jayden L Macklin-Cordes and Erich R Round.  Re-evaluating phoneme frequencies.  _Frontiers in psychology_ , 11:3181, 2020.  doi: 10.3389/fpsyg.2020.570895.
  * Sapir [1921] E. Sapir.  _Language: An Introduction to the Study of Speech_.  Dover Publications, 1921.
  * Grierson [1931] George A. Grierson.  _On the modern Indo-Aryan vernaculars_.  Indian Antiquary, 1931.
  * Fortescue [2006] Michael Fortescue.  Drift and the grammaticalization divide between Northern and Southern Wakashan.  _International Journal of American Linguistics_ , 72(3):295–324, 2006.
  * Croft [2000] William Croft.  _Explaining language change: An evolutionary approach_.  Longman, New York, 2000.
  * Dahl [2004] Östen Dahl.  _The growth and maintenance of linguistic complexity_.  John Benjamins Publishing, Amsterdam, 2004.
  * Heine and Kuteva [2005] Bernd Heine and Tania Kuteva.  _Language contact and grammatical change_.  Cambridge University Press, Cambridge, 2005.
  * Dunn et al. [2011] Michael Dunn, Simon J. Greenhill, Stephen C. Levinson, and Russell D. Gray.  Evolved structure of language shows lineage-specific trends in word-order universals.  _Nature_ , 473(7345):79–82, 2011.
  * Joseph [2013] Brian D. Joseph.  Demystifying drift.  In Martine Robbeets and Hubert Cuyckens, editors, _Shared grammaticalization_ , pages 43–66. John Benjamins, Amsterdam, 2013.
  * Mendes and Hahn [2016] Fábio K. Mendes and Matthew W. Hahn.  Gene Tree Discordance Causes Apparent Substitution Rate Variation.  _Systematic Biology_ , 65(4):711–721, 2016.  doi: 10.1093/sysbio/syw018.
  * Iosad [2021] Pavel Iosad.  Phonological convergence in North-western Europe.  Oslo, 2021.  URL https://www.anghyflawn.net/presentation/2021/icngl12/.  Paper presented at the 12th International Conference of Nordic and General Linguistics.
  * Round [2019] Erich R. Round.  Getting Sapir’s drift: Parallel evolution in linguistic as in biological systems, 2019.  Paper presented at Protolang 5.
  * Storz [2016] Jay F. Storz.  Causes of molecular convergence and parallelism in protein evolution.  _Nature Reviews Genetics_ , 17(4):239–250, 2016\.  ISSN 1471-0056.  doi: 10.1038/nrg.2016.11.
  * Matisoff [1973] James A. Matisoff.  Tonogenesis in Southeast Asia.  In Larry M. Hyman, editor, _Consonant Types and Tone_ , number 1 in Southern California Occasional Papers in Linguistics, pages 71–96. University of Southen California, Los Angeles, 1973.
  * Huffman [1976] Franklin Huffman.  The register problem in fifteen Mon-Khmer languages.  In Phillip N. Jenner, Laurence C. Thompson, and Stanley Starosta, editors, _Austroasiatic Studies_ , pages 575–590. Univ of Hawaii Press, Honolulu, 1976.
  * Dockum and Gehrmann [2021] Rikker Dockum and Ryan Gehrmann.  The East Asian Voicing Shift and its Role in the Origins of Tone and Register.  San Francisco, 2021.  Paper presented at the 95th Annual Meeting of the Linguistic Society of America, San Francisco.


11institutetext: expert.ai, Modena, Via Virgilio, 48/H – Scala 5 41123, Italy
22institutetext: Università degli Studi di Siena, Via Roma, 56, 53100 Siena,
Italy 33institutetext: Université Côte d’Azur, INRIA, Institut 3IA Côte
d’Azur, France 44institutetext: Université Côte d’Azur, Institut 3IA Côte
d’Azur, France

# The WebCrow French Crossword Solver††thanks: Supported by expert.ai,
https://www.expert.ai/

Giovanni Angelini 11 Marco Ernandes 11 Tommaso Iaquinta 22 Caroline Stehlé 33
Fanny Simões 44 Kamyar Zeinalipour 22 Andrea Zugarini 11 Marco Gori 22

###### Abstract

Crossword puzzles are one of the most popular word games, played in different
languages all across the world, where riddle style can vary significantly from
one country to another. Automated crossword resolution is challenging, and
typical solvers rely on large databases of previously solved crosswords. In
this work, we extend WebCrow 2.0, an automatic crossword solver, to French,
making it the first program for crossword solving in the French language. To
cope with the lack of a large repository of clue-answer crossword data,
WebCrow 2.0 exploits multiple modules, called experts, that retrieve candidate
answers from heterogeneous resources, such as the web, knowledge graphs, and
linguistic rules. We compared WebCrow’s performance against humans in two
different challenges. Despite the limited amount of past crosswords, French
WebCrow was competitive, actually outperforming humans in terms of speed and
accuracy, thus proving its capabilities to generalize to new languages.

###### Keywords:

Natural Language Processing Crossword Crossword Solver Artificial intelligence
Linguistic Puzzles Probabilistic Constraint Satisfaction

##  1 Introduction

Crossword puzzles have gained immense popularity as a widely played language
game on a global scale. Daily, millions of individuals engage in the
challenge, requiring a combination of skills. To solve crosswords effectively,
humans need to possess a broad vocabulary, general knowledge across various
subjects, and the ability to decipher wordplay and puns. Human solvers should
master the crossword language, its peculiarities, and specific knowledge
belonging to the country in which it is spoken. They must also excel in
pattern recognition, interpret contextual clues accurately, employ problem-
solving strategies, and demonstrate patience and perseverance. Mastering these
skills enables individuals to tackle crossword puzzles with efficiency,
accuracy, and a higher likelihood of success.
This scientific paper introduces a novel version of WebCrow 2.0, an AI-powered
application specifically designed for efficiently solving French crosswords.
It represents the first of its kind in the realm of French crosswords,
building upon the previous versions developed for Italian and American
crosswords. We will discuss the peculiarities of the French version in section
4 and the underlying architecture in section 5.
Solving crosswords based on clues is widely recognized as an AI-complete
problem[12], owing to its intricate semantics and the extensive breadth of
general knowledge required. Artificial intelligence has recently shown an
increasing interest in crossword solving. [21] Through this work we are
introducing a notable milestone in the literature, the French WebCrow system,
which achieved human-like performance on French crosswords by leveraging
numerous knowledge-specific expert modules.
WebCrow 2.0 can rely on a limited amount of previously solved crosswords and
clue-answers pairs. In the case of French crosswords, WebCrow 2.0 made use of
about 7.000 previously solved crossword puzzles and about 312,000 unique clue-
answers pairs. Studies in American crosswords rely on millions of clue-answers
pairs, 6.4M [21], and on the fact that almost all of the answers are in
previously seen crosswords. This is not the case with French crosswords, for
which the availability of a huge collection is limited, thus a more robust
approach is required.
The primary objective of French WebCrow is to establish its competitiveness
against human crossword solvers by leveraging expert modules, NLP (Natural
Language Processing) technologies, web search, and merging techniques to
efficiently generate candidate answer lists and fill crossword grids
accurately. The goal of the web search source of information is to provide
accurate solutions to crossword puzzles without the burden of maintaining an
up-to-date multitude of domain-specific modules. By tapping into the web as an
extensive source of information, French WebCrow offers the promise of
scalability and adaptability.
The upcoming sections provide information on related works and a comprehensive
overview of the various components of WebCrow 2.0. Detailed explanations will
be given on the French WebCrow version, accompanied by a thorough analysis of
the experimental results. Finally, the paper will conclude by summarizing the
findings and highlighting the significance of this research in the field of
crossword solving.

##  2 Related Works

In the literature, various attempts have been made to solve crossword puzzles.
However, none of these approaches have adequately addressed the specific
challenges posed by French crosswords. In the following, we will delve into a
review of existing works that have tackled the task of solving crosswords.
One of the first works on crossword solving is Proverb[14], which tackles
American crosswords. The system makes use of independent programs that solve
specific types of clues, leveraging information retrieval, database searching,
and machine learning. During the grid filling phase, it tries to maximize the
number of most probable words in the grid, using a loopy belief propagation,
combined with A* search [10].
Taking into account the Proverb experience, WebCrow [1, 7, 2] is the first
crossword solving for Italian crosswords. WebCrow introduces the use of a Web
Search Module (WSM), that extracts and filters potential answers from the Web,
being this an extremely rich and self-updating repository of human knowledge.
Additionally, the system retrieves clues from databases of previously solved
crossword puzzles (CPs). A merging process aims to consolidate the potential
solutions from both web documents and previously solved CPs. Subsequently, the
system employs a probabilistic Constraint Satisfaction Problem (CSP) approach,
similar to the Proverb system [13], to fill the puzzle grid with the most
suitable candidate answers. Both Proverb and WebCrow proved to be better-than-
average cruciverbalists (crossword solvers).
Following these experiences, we can find Dr.Fill work[9], a program designed
to solve American-style crossword puzzles. Dr.Fill converts crosswords into
weighted Constraint Satisfaction Problems (CSPs) and utilizes innovative
techniques, including heuristics for variable and value selection, a variant
of limited discrepancy search, and postprocessing and partitioning ideas. The
program’s performance in the American Crossword Puzzle Tournament suggests it
ranks among the top fifty crossword solvers globally.
In the field of crossword solving, there is also SACRY[3], introduced in 2015,
a system that leverages syntactic structures for clue reranking and answer
extraction. The authors build upon the foundation of WebCrow [1, 7, 2] to
develop SACRY. The system utilizes a database of previously solved crossword
puzzles (CPs) to generate a list of candidate answers. One of the key
contributions of SACRY is its emphasis on exploiting syntactic structures. By
incorporating syntactic analysis, SACRY improves the quality of the answer
list, enhancing the accuracy of crossword puzzle resolution.
Recently, there is the Berkeley Crossword Solver, a cutting-edge approach that
revolutionizes automatic American crossword puzzle solving. The system employs
neural question-answering models to generate answer candidates for each
crossword clue and combines loopy belief propagation with local search
techniques to discover complete puzzle solutions. One of the standout features
of the Berkeley Crossword Solver is its use of neural question-answering
models, which significantly enhances the accuracy of generating answer
candidates.
In the subsequent sections, we will provide a comprehensive and detailed
explanation of the various components comprising our system. We aim to delve
into each part, elucidating its functionalities and intricacies, to offer a
thorough understanding of our system’s architecture and its underlying
mechanisms.

##  3 Overview of WebCrow 2.0

WebCrow 2.0 is based on the previous WebCrow project experience([7]). As shown
in Fig.1, WebCrow has a first phase of clue analysis and clue answering. For
each clue a list of candidate answers, of the suitable length, is generated by
a variable number of experts. Then, all ordered lists are merged into a unique
list for each clue. The merging phase takes into account information like the
expert module’s confidence, the clue type and the answer length. The list
merger module and list filtering module, based on morphological information,
are both trainable on data. Next comes a belief propagation step([13]) which
reorders the candidate lists based on the puzzle constraints. Finally, the
last step is the real-solving mechanism that actually fills the grid with
letters, using a new grid-filling approach, the Char Based Solver algorithm.

Figure 1: WebCrow Overview.

###  3.1 Modularity

WebCrow 2.0 has a modular architecture, based on Redis as a communication
backbone. Redis implements a Publish/Subscribe messaging paradigm which allows
asynchronous communication between agents of nearly every programming language
[19]. The advantage is that with little effort we are able to design expert
modules for new languages or based on state-of-the-art natural language
processing techniques.

Based on our experience, expert modules should cover these three types of
knowledge:

  * •

Lexical and Ontological Knowledge: knowledge about the way we use language to
represent the world and organize information.

  * •

Crossword-specific experiential Knowledge: frequent crossword clue-answer
pairs, specific conventions and rules which recur in crossword puzzles.

  * •

Factual and Common Knowledge: encyclopedic knowledge, common sayings, facts,
and events of a common cultural background. The Web can be viewed as a
repository of this kind of knowledge.

In the next section, we are going to analyze in more detail the most crucial
expert modules that contribute to the creation of candidate answer lists.

###  3.2 The Expert Modules

####  3.2.1 Word Embedding expert

The Word Embedding expert takes into account the idea that crossword puzzles
often contain knowledge that has already been encountered in previously solved
crosswords. Word embeddings [17, 11, 16, 6, 5] offer a way to map individual
words or sequences of words (sentences) to specific vectors within a high-
dimensional geometric space. This mapping ensures that similar words or
sentences are located in close proximity to each other, while sentences with
unrelated meanings are positioned far apart.

Building upon a retrieval and ranking approach for crossword clue answers
[22], this expert employs the Google Universal Sentence Encoder (USE) to embed
each puzzle clue. It then searches for the most similar clues within the clue-
answers dataset, leveraging the capability of word embeddings to discover
linguistic connections between clues.

####  3.2.2 WebSearch expert

The Web Search Module utilizes web documents and search engines to identify
suitable answers for crossword clues. It consists of a web-based list
generator, a statistical filter, and an NLP category-based filter. The module
excels in handling longer word or compound word targets. It is particularly
useful for obtaining up-to-date data that may not be available in other
modules. In our current implementation, we have seamlessly integrated the Bing
API[15], but it is also feasible to utilize alternative search APIs.

####  3.2.3 Knowledge Graph expert

In this paper, we introduce a novel expert that utilizes expert.ai’s
linguistic knowledge graph[8], which provides a domain-independent
representation of the real world through concepts and their related meanings
and the different relationships that exist among concepts. Each linguistic
concept is explained using its similar meanings, its definition, and its
related concepts extracted from the Knowledge Graph. The concept is then
mapped using word embedding, which enables a search similar to the Word
Embedding expert.
By employing word embedding techniques, the concept can be effectively
searched, similar to the functionality of the Word Embedding expert. This new
expert has proven to be invaluable in solving clues that require both lexical
and ontological knowledge, such as “Sick” [ILL] or “Supportive kind of column”
[SPINAL]. Inside expert.ai Knowledge Graph ”sick” and ”ill” are two words
belonging to the same concept, they are synonyms. As far as ”spinal”, there is
a concept ”spinal column” which is a specification (kind of) of the concept
”column”.

####  3.2.4 Other Expert Systems for Language-Specific Crosswords

Expert systems for language-specific crosswords are designed to cater to the
specific nuances of the language. For example, in Italian crosswords, there
are often word plays with 2-letter answers. To address this, a hard-coded
expert system has been developed that encodes many of the possible types of
word plays, resulting in high-confidence answers. A similar approach has been
taken for French solvers, as described in Section 5.3. However, such a
situation is not present in American-style crosswords, where the minimum
number of letters for an answer is 3.

###  3.3 Merging

Once all the experts have produced their outputs, which are lists of candidate
words each one associated with a probability the list is merged together in a
unique list. The merging procedure consisted of a weighted average of the
experts list based on the length of the answer, the weights are picked based
on a specific training phase.

###  3.4 Grid Filling

For the grid-filling phase, we made use of a Char Base Solver. This approach
is more robust in case some candidate lists do not have the correct answers,
which is very likely in French crosswords.
For each slot $s$ we cumulate the probability mass $p^{s}_{d}(c)$ of a letter
$c$, in a given direction $d$ (Across or Down), adding all the probabilities
of words that contain letter $c$ in the slot $s$ with direction $d$. We
compute the probability mass $p^{s}(c)$ as:

$p^{s}(c)=p^{s}_{\mathit{A}}(c)\cdot p^{s}_{\mathit{D}}(c),$ (1)

This can be seen as the probability of the letter $c$ being correctly inserted
in a given cell, considering the constraint network and the answer lists. We
then use two criteria to assign to the given box the letter $c$ and in this
way constrain the grid filling.

$\left(p^{s}(c)>99.99\%\right)and\left(\mathit{best}_{\mathit{A}}(c)==\mathit{best}_{\mathit{D}}(c)\right)\\\
$ (2)
$\left(p^{s}(c)>99.00\%\right)and\left(\mathit{best}_{\mathit{A}}(c)==\mathit{best}_{\mathit{D}}(c)\right)and\\\
\left(p^{s}_{\mathit{A}}(c),p^{s}_{\mathit{D}}(c)>90\%\right)$ (3)

In other terms equation 2 states that a letter $c$ is chosen for a cell if the
confidence on that letter being in that cell is higher than 99.99% and it is
the most likely prediction in both directions. Where
$\mathit{best}_{\mathit{A}}(c)$ is the most likely letter in the across
direction and $\mathit{best}_{\mathit{D}}(c)$ the most likely in down
direction. Obviously this two letter must be the same.

Equation 3 instead states that if the confidence on a given letter being in a
given cell is only 99.00% then it is not enough to be the most likely for both
directions ($\mathit{best}_{\mathit{A}}(c)==\mathit{best}_{\mathit{D}}(c)$)
but that letter must have more than 90% probability for both directions.

If either of these criteria is met, then the character is assigned to that
particular position. Otherwise, it will be filled in a second phase with the
most probable word that does not break any other char-based constraint. In the
unlikely event that no word satisfies the bond, the cell is left unfilled or
could be filled by another post-processing expert, such as an implicit module.

##  4 The French Crosswords

###  4.1 Format and Rules

The French crossword format is similar to Italian crosswords. Unlike American
crosswords, two-letter words and “Blind cells” (cells that belong to only one
word) are allowed. Stacked answers made up of multiple words are less common
in French crosswords and generally correspond to expressions.
French crossword puzzles vary greatly in size and in the type of knowledge
used. In the next sub-sections, we will describe in more detail these aspects.

###  4.2 French Crosswords Dataset

For the French dataset, we collected over 300,000 clue-answer pairs, with the
answer length distribution shown in Figure 2. Additionally, we compiled a
collection of approximately 7,000 solved crossword puzzles from diverse
sources. We owe our success in this endeavor, completed in just a few months,
to the invaluable collaboration of two prolific authors, Serge Prasil and
Michel Labeaume.

Table 1: Dataset of previously seen clue-answers pairs and crosswords. Language |  unique clue-answers pairs |  crosswords
---|---|---
American Crosswords | 3,100K | 50,000
Italian Crosswords | 125K | 2,000
French Crosswords | 300K | 7,000

As we can see in table 1, the French dataset of previously seen clue-answers
pairs and crosswords is comparable to the Italian dataset, while the American
dataset is considerably huger. Moreover, American crosswords are more
standard. Almost all clue answers are present in previous crosswords, which is
not the case with French crosswords.
In figure 2 we show the statistics of the answer length present in French
crosswords. The majority of the answer’s lengths are below 10. Answers with
higher lengths are covered by verb inflections, compound words, or linguistic
expressions.

Figure 2: Statistics on French crosswords dataset.

###  4.3 Linguistic and Cultural Peculiarities

Unlike Italian and American crosswords, French crosswords use a wide range of
verb inflections in their solutions, covering nearly every possible tense and
person. However, the definitions provided in the clues often lead to the
correct inflection.

Furthermore, we have observed that French crossword authors have distinct
individual styles that vary greatly from one another. As in other crossword
languages, the aim of a crossword author is to provide clues that are obscure
enough while keeping solutions that should appear obvious once found [4]. He
must find the right level of difficulty for all the pairs of solutions. When
this level is too high, the risk is to discourage people from trying to solve
the crossword. On the contrary, if the clues are too simple, it is a memory or
patience game, but there is no challenge, and usually, French crossword
players prefer tricky enigmas, with few clues, twisted words, or traps.
French crossword authors inherit from the art of conversation in classical
French culture, which is well represented by the periphrase “la langue de
Molière” to designate French. As a result, French authors take pride in being
witty in the definitions they provide. They must be creative in finding jokes
that make the solver laugh [4], which leads to the development of distinct
individual styles.

###  4.4 Examples of clues in French crosswords

In this section, we categorize the types of clues found in French crosswords
and provide illustrative examples. Some of the examples are very specific to
the French language, in particular the examples given in sections Inflections
or Domain Specific Knowledge, and some other examples related for instance to
rare words or word games can be found in other languages as well.

####  4.4.1 Inflections

French crosswords make extensive use of rare verb tenses and modes, which can
make it challenging to find the correct inflection of the word to be guessed
through a direct web search. For instance, in the following clue answer pair:
Auraient des soucis excessifs [CAUCHEMARDERAIENT], the verb to guess
“cauchemarder”, which means “having a nightmare”, is rarely used at the
conditional present, at the third person plural. In another example, Apitoie
[ATTENDRISSE], the clue can refer to either the first or third person at the
indicative or subjunctive present tense. Depending on the verbal group of the
solution, the inflection can vary significantly at these tenses and persons.

####  4.4.2 Rare words

Some clues may involve words that are rare in French, either because they are
ancient words or foreign words, or these words belong to the literary register
or, conversely, to the colloquial or slang register. For instance, the
solution of the clue Dessiner sans soin [STRAPASSER] is an old verb. As the
frequency of these words is low, they may appear with a very low probability,
and in some cases, they may not appear at all in the candidate solutions list.

####  4.4.3 Domain Specific Knowledge

Some puzzles require domain-specific knowledge, such as very specific
geographical knowledge. For example, a clue may be: Elle habite une commune
située dans le département de l’Isère [SICCIOLANDE], meaning that we need to
search for the name of the female inhabitants of a city in a specific French
department. There is no generic rule in French for determining the name of the
inhabitants from the name of the city, and sometimes the name of the
inhabitants (in this case, “SICCIOLANDE”) can be very different from the city
name; in this example, the city name is “Siccieu-Saint-Julien-et-Carisieu”.
Therefore, solving this type of riddle requires a combination of encyclopedic
knowledge, spelling rules, and potential knowledge of spelling exceptions.

The following example requires specific knowledge of French literature: Le
bleu et le blanc du poète [OE]. This example pertains to the poem “Voyelles”
by the renowned French poet Arthur Rimbaud, where each vowel is linked to a
color. In this poem, the vowel “O” is associated with the color blue (“bleu”),
and the vowel “E” is associated with the color white (“blanc”)

####  4.4.4 Generic Words With Few Indices

On the other hand, some clues may consist of a few generic words such as color
names and adverbs, which can be linked to numerous solutions. In such cases,
the definition is not clearly connected to the answers, making automatic graph
search more challenging. For instance, consider the following clue: Pétales de
rose [ESE]. One may be misled by the words “Pétales” and “rose”, which could
refer to the lexical field of flowers. However, in French crosswords, they
refer to the compass rose, and the solution could be of the type ESE (“Est,
Sud, Est” meaning direction East, South, East), NN, NSN, and so on.

####  4.4.5 Word Games

Word games are a type of clue in which the solver must manipulate the multiple
meanings of the words in order to arrive at the solution. In crossword
puzzles, common word games involve the letters of a single word, which may be
either part of the clue or part of another word that must be guessed. For
example, consider the clue A la sortie de Strasbourg [RG]. The phrase “A la
sortie de” translates to “At the exit of” and suggests that the solution is
composed of the last letters of the word “Strasbourg”. This clue is made more
challenging by the fact that “Strasbourg” is a proper noun, and solvers may be
tempted to look for a solution that is geographically related to the city.

####  4.4.6 Two Steps Clues

Some crossword puzzles can be challenging as they require two or more steps to
arrive at the solution. For instance, consider the clue À l’envers : coût
[FIRAT]. To solve this puzzle, one must first identify a synonym for the word
“coût” (TARIF) and then invert the letters (FIRAT), as indicated by the phrase
“À l’envers :”. Similarly, in the clue Grecque a l’envers [ATE], the solver
must recognize that “Grecque” refers to a Greek letter before inverting the
letters of the word found. In the example Impro de jazz sans voyelle [SCT],
while it may seem straightforward to humans, this could prove to be a
challenging task for a machine. The solver should find the answer to the
definition of “impro de jazz” (“jazz improvisation”) without any information
about the word length before removing the vowels.

####  4.4.7 Multiple Categories

Finally, crossword puzzles often combine multiple difficulties. In this
example: Attaquerai les portugaises [ESSORILLERAI], the author Serge Prasil
used slang expression “les portugaises”, to refer to ears. The verb to guess
is further an ancient word, a medieval torture that means cutting off the
ears, in an unusual form, because it is conjugated at the future.

##  5 The System Architecture

The recent changes in the architecture allowed for easy incorporation of new
agents and modification of existing ones by simply adjusting the parameter
configuration. For example, the web-search expert (see Section 3.2.2) was
ported to French by modifying the query language in the parameter set.

To update the Word Embedding Expert, we required the French crosswords dataset
described in Section 4.2. The clues had to be encoded further with the
Universal Sentence Encoder, as explained in the Word Embedding expert section
(see Section 3.2.1).

After implementing these two expert agents, we analyzed the results to
identify the areas where most errors occurred. We discovered that 29% of
missing answers were due to missing verb inflections, and 8% were due to
adjective or noun inflections. Among all verb forms, the present tense was
used only 20% of the time, while the past simple, a tense rarely used in
everyday life, was used 40% of the time. Among the inflections of adjectives,
the feminine form was used 58% of the time, and the plural form was used 55%
of the time.

###  5.1 Knowledge Graph Expert

As per the analysis of the most common errors, we have enhanced expert.ai’s
French knowledge graph. The results analysis revealed the need to incorporate
inflections of verbs, adjectives, and nouns. To achieve this, we followed the
same approach as described in Section 3.2.3. However, in this case, in
addition to adding the connected concepts with the same description, we also
included the required inflections.

###  5.2 Lexicon

In addition, we identified a need to enhance the lexicon utilized by WebCrow.
To address this, we incorporated Lexique 3.83, a French lexicon database
containing approximately 123K distinct entries of at least 2 letters, as
described in [18]. We combined this dataset with data from a French
dictionary, resulting in a final lexicon comprising approximately 198K words.

###  5.3 Rule-Based Expert

We have developed a Python-based expert module for French crosswords that can
decipher common word games. The module is designed to identify target words in
the clues and provide associated lists of solutions. The target words may
include Arabic number conversions to words, Roman numerals, chemical elements
from Mendeleev’s table, French departments, grammar lists (such as personal
pronouns, conjunctions, and prepositions), and Greek letters.

Furthermore, the Rule-based expert was designed to decipher clues that
indicate the presence of word games in finding the answers, and where the
solution involves either the inversion of a word, a reduced set of letters, or
a mix of letters. The word on which the word game applies may be included in
the clue or not. In the latter case, which we called “two steps clues” in
chapter 4.4, the rule-based expert first searches for a list of possible
solutions by calling the Word Embedding expert and then applies the word game
to the letters of each word in the list.

##  6 Experimental Results

In this section, we present the comprehensive results obtained from our
experimentation. Following the development of the system, as outlined in the
preceding sections, we proceeded to assess its performance on previously
unseen crosswords.

### Test Dataset

To ensure a robust evaluation, we carefully selected a dataset comprising 62
distinct crosswords that were published subsequent to the crosswords used for
constructing the different experts, such as the Word Embedding expert3.2.1.
This selection criterion ensured that there was no overlap between the
crosswords utilized for training and those employed for testing purposes.
To evaluate the performance of our proposed solution, we conducted an
extensive analysis using a diverse set of crossword puzzles sourced from
multiple authors and publications. Our dataset comprises 10 puzzles each from
two renowned creators, Michel Labeaume and Serge Prasil. Furthermore, we
incorporated 40 additional crosswords from established publishers to
facilitate a thorough assessment. Detailed information about the test
crossword can be found in Table 2.

Table 2: Test CrossWords. Source | Number of Puzzles | Dimension
---|---|---
Michel Labeaume | 10 | 10 x 10
Serge Prasil | 10 | 20 x 20
Other Sources | 42 | Variable max 15 x 15

We used diverse crosswords to test the system’s ability to handle different
puzzle styles, author preferences, and construction variations. This approach
helped us understand the system’s performance and adaptability in unseen
crosswords.

### Results

We evaluated the system’s performance using three distinct metrics: percentage
of correct words, which measures the accuracy of inserting the correct target
answers, percentage of correct letters, which evaluates the accuracy of
inserting individual letters, and percentage of inserted letters, which
assesses the system’s ability to fill crossword slots.
For a comprehensive overview of these metrics across different sources of
crosswords, refer to Table 3. It encapsulates the corresponding results
obtained from the test sets of various crossword sources, shedding light on
the overall performance of our system in solving French Crosswords.

Table 3: Performance of the System on the Test CrossWords. Source | Words Accuracy | Letters Accuracy | Inserted Letters
---|---|---|---
Michel Labeaume | 92.97% | 98% | 100%
Serge Prasil | 91.82% | 96.9% | 99.15%
Other Sources | 73.86% | 81.16% | 96.99%

Our crossword solver achieved impressive results in solving French crosswords
from Michel Labeaume and Serge Prasil, with some 100% solved crosswords. On
the other sources, the performance varied a lot, we had some sources with
fully correct solved crosswords, while on other crosswords the system
performed poorly. Based on our analysis some authors use very specific styles
and knowledge, which demonstrates that solving crosswords is an AI-complete
and open-domain problem. In some cases, answers were very domain-specific, see
section 4.4.3.

Overall, these remarkable results demonstrate the robust performance of our
system in solving French crosswords. The accuracy rates obtained highlight the
system’s ability to effectively fill in words and letters, thus confirming its
competence in solving French crossword puzzles.

In table 4, we tested the system by removing some expert modules. These tests
show that each module is necessary to obtain the best results, the Full
version, and that different source of knowledge is required to solve
crosswords. Unlike American crossword studies, there is not a huge dataset of
previously solved crosswords. Moreover, French crosswords are not as standard
as American ones. Each crossword can vary a lot, influenced by the style and
imprint of its author.

Table 4: Ablation test. Configuration | % of correct words | % of correct letters | % word drop
---|---|---|---
Full | 65.71 | 75.22 | -
No Rule based | 65.16 | 74.79 | 0.55
No Websearch | 61.60 | 72.68 | 4.11
No Lexicon | 61.36 | 71.98 | 4.35
No KG | 56.28 | 68.38 | 9.43

To gain insights into our system’s strengths, limitations, and relative
performance compared to human crossword solvers, we conducted challenging
competitions. The subsequent section presents a detailed analysis of these
comparative evaluations.

###  6.1 AI vs Human challenges

We organized an internal challenge at INRIA to evaluate our system’s
performance in a real-world scenario, putting it against human participants.
The challenge included French and American crossword puzzles. Both humans and
WebCrow were allowed to utilize web searches during the challenge.
The challenge included three crosswords: an easy-medium-level French crossword
with a 10-minute time limit (score counted), a medium-hard level French
crossword with a 20-minute time limit (score counted), and an American
crossword with a 10-minute time limit (score counted). The experimental
results, including the performance of WebCrow (Live and Lab), the average
human performance, and the best human performance are presented in Table 5.

Table 5: Results of the Crossword Solving Competition (INRIA). Player | Score | Time (sec.)
---|---|---
WebCrow Live | 296.18 | 419
WebCrow Lab | 313.75 | 556
AVG Human | 50.39 | 2570
Best Human | 104.22 | 2700

Two modes were implemented: “WebCrow Live” where the system ran in real-time
with predetermined configurations, and “WebCrow Lab” where results were
computed in advance in the laboratory. It is important to note that variations
in web information could lead to discrepancies between the results of the two
modes.

We also conducted a public challenge at the World AI Cannes Festival 2023,
evaluating the French version of WebCrow. There were three challenges, one for
each language: French crosswords, Italian crosswords, and American crosswords.
Each challenge had two crosswords valid for the competition with time limits.
The two French crosswords were created specifically for the challenge by
renowned authors Serge Prasil and Michel Labeaume.

The scoring system gave points from 0 to 100 based on the percentage of
correct words (0 to 110 for the second crosswords. Then some additional points
(maximum 15) were added based on the percentage of time not used. We had 15
minutes for the first crossword and 20 minutes for the second. Finally, in
case of a fully correct answer, 15 points were awarded.

Table 6: Results of the French Crossword Solving Competition (WAICF). Player | Score | Time (sec.)
---|---|---
WebCrow Live | 228,90 | 559
WebCrow Lab | 249,86 | 368
AVG Humans | 24.24 | 2570
Best Human | 69,53 | 1493

The detailed experimental outcomes of the WAICF French crossword-solving
challenge can be found in Table 6. This challenge provided insights into
WebCrow’s performance and its cross-lingual capabilities. Humans
cruciverbalist are strong only on one language.
In the French crossword challenge, there was no strong human competitor
present. This leaves space for further challenges with French experts in
crosswords.

##  7 Conclusion and Future Works

In conclusion, this work represents a significant advancement in the field of
crossword solving. By capitalizing on our previous experience in the field we
present a novel version of WebCrow 2.0 and its French WebCrow version, which
represents the first French crossword solver.
In this work we collected a dataset of French crosswords, enabling us to make
some comparisons with crosswords in other languages, Italian and American.
Moreover, we analyzed the peculiarities of French crosswords. French crossword
puzzles vary greatly, they are not standard like the American ones, the size,
the knowledge, and the language games involved are influenced by the style and
imprint of its author.
French WebCrow is an above-human-average crossword solver, but there is still
room for improvements. The potential for French WebCrow to achieve competitive
performance serves as a strong motivation for further research and
development, paving the way for AI-powered crossword solving to reach new
heights.
There are three main branches for future development. First of all, there is
room to improve the performances of both the Italian and French solvers by
working on filters and re-ranking based on systems that can predict the
grammatical type of the answer. Another improvement can be achieved by
leveraging on the output of the Char Based Solver which fills the grid with
the most probable letters, leaving empty the cells which have more
uncertainty. We would like to implement a system that exploits the letters
that are actually fixed to find out the missing ones on the internet or with a
Generative Pre-trained Transformer.
Another branch of development resides in the intrinsic characteristic of
WebCrow 2.0, in which the modularity of its frameworks allows us to add a new
language solver with little effort. Of course, as happened for Italian,
English, and French, language-specific experts have to be developed to obtain
high performances in crossword solving. We are already in touch with German
universities to explore this road.
The last branch regards the inverse task, the crossword generation [20]. The
experience gained, but even more the data collected during the WebCrow 2.0
experience, could represent a launch pad for the complex task of crossword
generation. Consider that, for instance, the New York Times crosswords (one of
the biggest collections of crosswords) contains an average of 96% of already
seen answers, and only the 4% of the answers, on average, are new [21]. This
task is still performed principally through semi-automatic proprietary
software. New approaches should take into account Generative Pre-trained
Transformers, which, at the moment, represent the most advanced approach for
generating text and could be tested on generating crossword clues, which may
also be ambiguous or tricky, covering different kinds of human knowledge.

## Acknowledgements

This research owes its accomplishment to the generous collaboration of
esteemed French crossword authors, Serge Prasil and Michel Labeaume. The
University of Siena, expert.ai, and the 3IA Côte d’Azur Investment in the
Future projects administered by the National Research Agency (ANR), under the
reference number ANR-19-P3IA-0002, provided invaluable support for this
endeavor

## References

  * [1] Giovanni Angelini, Marco Ernandes and Marco Gori  “Solving italian crosswords using the web”  In _AI* IA 2005: Advances in Artificial Intelligence: 9th Congress of the Italian Association for Artificial Intelligence, Milan, Italy, September 21-32, 2005. Proceedings 9_ , 2005, pp. 393–405  Springer
  * [2] Giovanni Angelini, Marco Ernandes and Marco Gori  “Webcrow: A web-based crosswords solver”  In _Intelligent Technologies for Interactive Entertainment: First International Conference, INTETAIN 2005, Madonna di Campiglio, Italy, November 30–December 2, 2005. Proceedings 1_ , 2005, pp. 295–298  Springer
  * [3] Gianni Barlacchi, Massimo Nicosia and Alessandro Moschitti  “SACRY: Syntax-based automatic crossword puzzle resolution system”  In _Proceedings of 53nd Annual Meeting of the Association for Computational Linguistics: System Demonstrations, Beijing, China, July. Association for Computational Linguistics_ , 2015
  * [4] Vincent Berthelier  “L’humour des mots croisés, étude stylistique”, 2018
  * [5] Daniel Cer et al.  “Universal sentence encoder”  In _arXiv preprint arXiv: 1803.11175_ , 2018
  * [6] Jacob Devlin, Ming-Wei Chang, Kenton Lee and Kristina Toutanova  “Bert: Pre-training of deep bidirectional transformers for language understanding”  In _arXiv preprint arXiv:1810.04805_ , 2018
  * [7] Marco Ernandes, Giovanni Angelini and Marco Gori  “Webcrow: A web-based system for crossword solving”  In _AAAI_ , 2005, pp. 1412–1417
  * [8] Expert.ai  “expert.ai Knowledge Graph” [Online; accessed on 2023], https://www.expert.ai/products/expert-ai-platform/knowledge-graph/, 2023
  * [9] Matthew L Ginsberg  “Dr. fill: Crosswords and an implemented solver for singly weighted csps”  In _Journal of Artificial Intelligence Research_ 42, 2011, pp. 851–886
  * [10] Peter Hart, Nils Nilsson and Bertram Raphael  “A Formal Basis for the Heuristic Determination of Minimum Cost Paths”  In _IEEE Transactions on Systems Science and Cybernetics_ 4.2 Institute of ElectricalElectronics Engineers (IEEE), 1968, pp. 100–107  DOI: 10.1109/tssc.1968.300136
  * [11] Yitan Li and Linli Xu  “Word Embedding Revisited: A New Representation Learning and Explicit Matrix Factorization Perspective”  In _Join Conf. on Artificial Intelligence (IJCAI)_ , 2015
  * [12] Michael L Littman  “Computer language games”  In _Computers and Games: Second International Conference, CG 2000 Hamamatsu, Japan, October 26–28, 2000 Revised Papers 2_ , 2001, pp. 396–404  Springer
  * [13] Michael L Littman, Greg A Keim and Noam Shazeer  “A probabilistic approach to solving crossword puzzles”  In _Artificial Intelligence_ 134.1-2 Elsevier, 2002, pp. 23–55
  * [14] Michael L Littman, Greg A Keim and Noam M Shazeer  “Solving crosswords with Proverb”  In _AAAI/IAAI_ , 1999, pp. 914–915
  * [15] Microsoft  “Bing Web Search API” [Online; accessed on 2023], https://www.microsoft.com/en-us/bing/apis/bing-web-search-api, 2023
  * [16] Tomas Mikolov et al.  “Advances in pre-training distributed word representations”  In _International Conference on Language Resources and Evaluation_ , 2018
  * [17] Tomas Mikolov, Kai Chen, Greg Corrado and Jeffrey Dean  “Distributed Representations of Words and Phrases and their Compositionality”  In _arXiv preprint arXiv:1310.4546_ , 2013
  * [18] Boris Pallier  “Openlexicon, GitHub repository”, 2019  URL: https://github.com/chrplr/openlexicon
  * [19] Redis  “Redis Pub/Sub” [Online; in data 22-agosto-2022], 2022  URL: https://redis.io/docs/manual/pubsub/
  * [20] Leonardo Rigutini, Michelangelo Diligenti, Marco Maggini and Marco Gori  “Automatic generation of crossword puzzles”  In _International Journal on Artificial Intelligence Tools_ 21.03 World Scientific, 2012, pp. 1250014
  * [21] Eric Wallace et al.  “Automated Crossword Solving”  In _arXiv preprint arXiv:2205.09665_ , 2022
  * [22] Andrea Zugarini and Marco Ernandes  “A Multi-Strategy Approach to Crossword Clue Answer Retrieval and Ranking.”  In _CLiC-it_ , 2021