Introduction

Suppose that $𝒦$ is the set of all possible lexical entries in a language, $C$ is a set of category labels, and $L$ is the set of all phonotactically valid words in the language. Then suppose $f:𝒦\times C\to L$ is the function that inflects words in the language.

We wish to not only be able to inflect a given lexical entry in a given category but also to perform the reverse task: given an inflected word form, find all lexical entries that it could be derived from, along with the category of the inflected form. That is, we wish to devise an algorithm that computes the preimage $f^{\leftarrow }(\{s\})$ for any $s\in L$.

If we are concerned only with finding matches in a fixed dictionary $K\subseteq 𝒦$, then we can store a mapping for all $k\in K$ and $c\in C$ from $f(k,c)$ to $(k,c)$. This method is conceptually simple and requires no structural knowledge of $f$, but it takes $O(|K|\cdot |C|)$ entries and requires $C$ to be finite, making it space-intensive for highly inflecting languages.

Because Ŋarâþ Crîþ v9’s inflection rules have been complex, this brute-force method has been used for f9i. During the development of sp9 for Project Shiva, however, +merlan #flirora proposed investigating alternative approaches that would not require storing all inflected forms.

The compositionality of linguistic inflection

Many inflection paradigms are not perfectly fusional. That is, we can express $C$ as a Cartesian product of other sets $C_0\times C_1\times \cdots \times C_{r-1}$ and define a sequence of functions $f_i:L_i\times C_i\to L_{i+1}$, where $L_0=𝒦$ and $L_r=L$. Then $f$ involves applying each $f_i$ in succession, passing each category label:

$$\begin{array}{lrlr}& f(k,(c_0,c_1,\dots ,c_{r-1}))& =f_{r-1}(\dots f_1(f_0(k,c_0),c_1),\dots ,c_{r-1})& \end{array}$$

This structure allows us to compute $f^{\leftarrow }(\{s\})$ by inverting each step of the inflection process in reverse order:

$$\begin{array}{lrlr}& S_n& =\{(s,\varnothing )\}& \\ & S_{i-1}& =\bigcup _{(s,c)\in S_i}\{(s^{\prime },(c^{\prime },c))|(s^{\prime },c^{\prime })\in f_{i-1}^{\leftarrow }(\{s\})\}& \\ & f^{\leftarrow }(\{s\})& =S_0& \end{array}$$

Additionally, many parts of speech can be categorized into multiple inflectional classes. In mathematical terms, $𝒦$ can be partitioned into sets $P^0,P^1,\dots ,P^{\pi -1}$, each of which has a function $f^{j.}:P^j\times C\to L=f{|}_{P^j\times C}$ that is ‘simpler’ to implement than $f$ itself. Hence, $f^{\leftarrow }(\{s\})$ can be computed by attempting to match against each of the subsets $P^j$:

$$\begin{array}{lrlr}& f^{\leftarrow }(\{s\})& =\bigcup _{j=0}^{\pi -1}(f^{j.}{)}^{\leftarrow }(\{s\})& \end{array}$$

Alternatively, we can partition the set $C$ into sets $C^0,C^1,\dots C^{\gamma -1}$, with corresponding functions $f^{.k}:𝒦\times C^k\to L=f{|}_{𝒦\times C^k}$, such that

$$\begin{array}{lrlr}& f^{\leftarrow }(\{s\})& =\bigcup _{k=0}^{\gamma -1}(f^{.k}{)}^{\leftarrow }(\{s\})& \end{array}$$

Importantly, each of these decompositions produce a set of tuples $({𝒦}^{\prime },C^{\prime },L^{\prime },f^{\prime })$ which can be analyzed as a subproblem of the original problem and treated in the same way.

As an example, consider a language that has five classes for nominal inflections, which can be categorized into two broad groups, X and Y. This language also has cases in three groups:

• Group A cases are the most commonly used cases and have distinct declensions per class.
• Group B cases are less commonly used than group A cases and are declined differently between X classes and Y classes, but the declensions are the same within each group of classes.
• Group C cases are the least commonly used and are declined in the same way across all nouns. Additionally, while group A and B cases are coexponential with number, group C cases are monoexponential in that nouns in group C cases have a case ending followed by a number ending.

Then we could decompose the problem $(𝒦,C,L,f)$ first by partitioning $C$ into $C^A\cup C^B\cup C^C$. Subsequently, $(𝒦,C^A,L,f^{.A})$ is decomposed by partitioning $𝒦$ into $P^0\cup \dots \cup P^4$, while $(𝒦,C^B,L,f^{.B})$ is decomposed by partitioning the same set as $P^X\cup P^Y$.

In contrast, $(𝒦,C^C,L,f^{.C})$ is decomposed by composition into $(𝒦,C_0^C,L_1,f_0^{.C})$ (adding the case affix) and $(L_1,C_1^C,L,f_1^{.C})$ (adding the number affix). We now have the following simpler problems:

$$\begin{array}{lcr}& (P^0,C^A,L,f^{0.A})& \\ & (P^1,C^A,L,f^{1.A})& \\ & (P^2,C^A,L,f^{2.A})& \\ & (P^3,C^A,L,f^{3.A})& \\ & (P^4,C^A,L,f^{4.A})& \\ & (P^X,C^B,L,f^{X.B})& \\ & (P^Y,C^B,L,f^{Y.B})& \\ & (𝒦,C_0^C,L_1,f_0^{.C})& \\ & (L_1,C_1^C,L,f_1^{.C})& \end{array}$$

This compositionality was the reason that we did not choose to define the set of possible categories $C(k)$ as dependent on the lexical entry. If we did so, then we could partition $𝒦$ into equivalence classes on $C(k)$ to yield subproblems that have a fixed set of category labels.