Truncation

In many cases, inflection involves the addition of prefixes or suffixes to a stem. It follows that inverting this process would involve the removal of these affixes. However, concatenation often results in phonological changes to one or both of the stem and the affix. For example, I meet you in Ŋarâþ Crîþ would be derived as cenv-a-ve, but the co-occurrence of v in the resulting word is considered undesirable (oginiþe cfarðerþ) and is resolved by replacing the first v with an n. Thus, the resulting word is not **cenvave but rather cennave.

Let $\mathrm{\Sigma }$ be an alphabet and $f:{\mathrm{\Sigma }}^{*}\times {\mathrm{\Sigma }}^{*}\to {\mathrm{\Sigma }}^{*}\times {\mathrm{\Sigma }}^{*}$ be a function describing concatenation rules transforming pairs of strings $(a,b)$. Generally, $f$ can be seen as the composition of some number of individual ‘rules’ $f_0,f_1,\dots ,f_{n-1}:{\mathrm{\Sigma }}^{*}\times {\mathrm{\Sigma }}^{*}\to {\mathrm{\Sigma }}^{*}\times {\mathrm{\Sigma }}^{*}$.

Then let $a\stackrel{f}{\sim }b$ be the concatenation of $a$ and $b$ under $f$, or $f$-concatenation, defined as

$$\begin{array}{lrr}& a\stackrel{f}{\sim }b=a^{\prime }\cdot b^{\prime }\text{ where }(a^{\prime },b^{\prime })=f(a,b)& \end{array}$$

Given $b,w\in {\mathrm{\Sigma }}^{*}$, we wish to find all $a\in {\mathrm{\Sigma }}^{*}$ such that $a\stackrel{f}{\sim }b=w$. If we can compute the preimage of a set over $f$, then this is simply

$$\begin{array}{lrr}& A=\bigcup _{i=0}^{|w|}\{\alpha |({\alpha }^{\prime },{\beta }^{\prime })\in f^{\leftarrow }(\{(w[0..i],w[i..|w|])\})\wedge {\beta }^{\prime }=b\}& \end{array}$$

That is, we do the following:

• Split $w$ into $(\alpha ,\beta )$ in all possible ways.
• Find all $({\alpha }^{\prime },{\beta }^{\prime })$ such that $f({\alpha }^{\prime },{\beta }^{\prime })=(\alpha ,\beta )$.
• Collect all such ${\alpha }^{\prime }$ where ${\beta }^{\prime }=b$.

An analogous problem and its solution can be stated for removing prefixes.

This algorithm is quite general, and certain properties of $f$ admit simpler algorithms. (The solution is trivial if $f$ is the identity function.)

If for all $a,b$ and $(a^{\prime },b^{\prime })=f(a,b)$, the strings $b$ and $b^{\prime }$ have the same length, then $f$ is considered to be right-isometric. In this case, we do not have to try all combinations of $(\alpha ,\beta )$ but rather only the one in which $|\beta |=|b|$.

More generally, let

$$\begin{array}{lrr}& D_f(b)=\{|b^{\prime }||a\in {\mathrm{\Sigma }}^{*},(a^{\prime },b^{\prime })=f(a,b)\}& \end{array}$$

be the set of possible lengths that $f$ could transform $b$ to become. Then we only have to try combinations of $(\alpha ,\beta )$ where $|\beta |\in D_f(b)$.

A stronger property that right isometry is right invariance, which requires $b=b^{\prime }$; in other words, $f$ is not allowed to change the second string. If $f$ is right-invariant, then we can return an empty set if $b$ is not a suffix of $w$.

Additionally, concatenation rules in human languages rarely change segments far away from the junction. For $a,b\in {\mathrm{\Sigma }}^{*}$ and $(a^{\prime },b^{\prime })=f(a,b)$, let $s$ be the longest common suffix of $b$ and $b^{\prime }$, leaving $r$ and $r^{\prime }$ before it. Then the forward dextral radius of influence of $(a,b)$ with respect to $f$ is $R_d(f;a,b)=|r|$ and the backward dextral radius of influence is $R_d^{\prime }(f;a,b)=|r^{\prime }|$. We can also define these radii for the function itself:

$$\begin{array}{lrlr}& R_d(f)& =\underset{a,b\in {\mathrm{\Sigma }}^{*}}{\sup }{R}_d(f;a,b)& \\ & R_d^{\prime }(f)& =\underset{a,b\in {\mathrm{\Sigma }}^{*}}{\sup }{R}_d^{\prime }(f;a,b)& \end{array}$$

Note that for right-isometric $f$, $R_d(f)=R_d^{\prime }(f)$.

Given knowledge of these values, suppose that for a given $(\alpha ,\beta )$, we compare $b$ and $\beta$, aligning them at their ends. Then if $b$ and $\beta$ differ in the characters at indices $|b|-i$ and $|\beta |-i$, respectively, and if $|b|-i<R_d(f)$ or $|\beta |-i<R_d^{\prime }(f)$, then we can conclude that $f^{\leftarrow }(\alpha ,\beta )$ does not contain any pairs $({\alpha }^{\prime },{\beta }^{\prime })$ such that ${\beta }^{\prime }=b$ and can thus discard the pair $(\alpha ,\beta )$.

Unfortunately, Ŋarâþ Crîþ v9e’s concatenation rules have a dextral radius of influence of 5, while many of its affixes are shorter than 5 assemblage units long. For that reason, radius-of-influence simplifications are unlikely to be useful for Ŋarâþ Crîþ.

Examples of concatenation rules

The identity function is right-invariant and has a dextral radius of influence of 0.

Let $m$ and $n$ be nonnegative integers and $g\in {\mathrm{\Sigma }}^m\times {\mathrm{\Sigma }}^n\to {\mathrm{\Sigma }}^{*}\times {\mathrm{\Sigma }}^{*}$. Then denote by ${\text{peephole}}_{m,n}(g)$ the function $f$ such that

$$\begin{array}{lrlr}& f(a,b)& =\{\begin{array}{cc}(a[..|a|-m]\cdot a^{\prime },b^{\prime }\cdot b[n..])& \text{i}\text{f}|a|\ge m,|b|\ge n,(a^{\prime },b^{\prime })=g(a[|a|-m..],b[..n])\\ (a,b)& \text{i}\text{f}|a|<m\text{o}\text{r}|b|<n\end{array}& \end{array}$$

In effect, ${\text{peephole}}_{m,n}(g)$ is a function that affects only the $m+n$ characters around the juncture.

Then the following statements are true:

$$\begin{array}{lrlr}& D_f(b)& =\{l+(|b|-n)|l\in D_g(b[..n])\}\text{i}\text{f}|b|\ge n& \\ & R_d(f)& =n& \\ & R_d^{\prime }(f)& =\underset{a,b}{\max }|b^{\prime }|\text{w}\text{h}\text{e}\text{r}\text{e}(a^{\prime },b^{\prime })=g(a,b)& \end{array}$$

In particular, $f$ is right-isometric if $g$ is.

Often, we wish to replace one substring with another if a juncture occurs anywhere within the substring. For instance, the rule replacing ‘cat’ with ‘dog’ can be expressed as the composition of two functions ${\text{peephole}}_{\mathrm{2,1}}(g_2)\circ {\text{peephole}}_{\mathrm{1,2}}(g_1)$ where

$$\begin{array}{lrlr}& g_1(a,b)& =\{\begin{array}{cc}(\text{d},\text{og})& \text{i}\text{f}a=\text{c},b=\text{at}\\ (a,b)& \text{ otherwise}\end{array}& \\ & g_2(a,b)& =\{\begin{array}{cc}(\text{do},\text{g})& \text{i}\text{f}a=\text{ca},b=\text{t}\\ (a,b)& \text{ otherwise}\end{array}& \end{array}$$

Suppose that we have a function $h\in {\mathrm{\Sigma }}^k\to {\mathrm{\Sigma }}^k$. If $f={\text{subst}}_k(h)$ is such a substitution function, then it can be expressed as a composition of peephole functions $f_{n-1}\circ \cdots \circ f_1$ where

$$\begin{array}{lrlr}& f_i& ={\text{peephole}}_{i,k-i}(g_i)& \\ & g_i(a,b)& =(s^{\prime }[..i],s^{\prime }[i..])\text{w}\text{h}\text{e}\text{r}\text{e}{s}^{\prime }=h(a\cdot b)& \end{array}$$

${\text{subst}}_k(h)$ is right-isometric and has a dextral radius of influence of $k-1$.

We have assumed that the function $h$ preserves the length of the substring. We can generalize $\text{subst}$ to account for functions that change the length of the input, but we must be careful about where the new juncture is placed.

Generalizations

In practice, we often want to check a word $w$ against multiple suffixes from a fixed set $B\subseteq {\mathrm{\Sigma }}^{*}$. This problem can be solved similarly to the single-suffix case by matching any of $({\alpha }^{\prime },{\beta }^{\prime })\in f^{\leftarrow }(\dots )$ where $\beta \in B$. This problem might be simplifiable depending on the properties of $f$. If $f$ is right-invariant, for instance, then it is possible to use a trie containing the reversed elements of $B$.

Often, we do not want to find all elements of $A$ but rather its intersection with a ‘dictionary set’ $K_b$.

Concatenation on regular systems

The notion of truncation can be generalized to be over any pair of formal languages. In this case, the concatenation rules function may have a different codomain from its domain. Usually, we are interested in languages of a regular system $\mathrm{\Lambda }$ in which the end state of the first string is equal to the start state of the second string. We define an extended concatenative system $\mathrm{\Phi }$ over $\mathrm{\Lambda }$ as a pair of functions $(\kappa ,\varphi )$ where:

• $\kappa :Q\times Q\times Q\to Q$ is a function that takes in three states $(p,q,r)$ and outputs a new middle state $q^{\prime }$, and
• $\varphi :{\bigcup }_{p,q,r\in Q}[\{(p,q,r)\}\to \mathrm{\Lambda }(p,q)\times \mathrm{\Lambda }(q,r)\to \mathrm{\Lambda }(p,\kappa (p,q,r))\times \mathrm{\Lambda }(\kappa (p,q,r),r)]$ returns for every triple of states $(p,q,r)$ a concatenation rule function for two strings, possibly changing the middle state according to $\kappa$.

For $a\in \mathrm{\Lambda }(p,q)$ and $b\in \mathrm{\Lambda }(q,r)$, the extended concatenation $a\underset{p,q,r}{\stackrel{\mathrm{\Phi }}{\sim }}b=a\stackrel{\varphi (p,q,r)}{\sim }b$ is an element of $\mathrm{\Lambda }(p,r)$. If no ambiguity would arise, we omit the state names from the operator and simply write $a\stackrel{\mathrm{\Phi }}{\sim }b$.

$N$-ary concatenation

We have looked at binary concatenation; concatenation of more than two operands is often assumed to be left associative. In other words, concatenating $(a,b,c)$ concatenates $a$ and $b$ first, then the result of that to $c$.

Another possibility for concatenating multiple morphemes is to apply the juncture rules after all of the concatenations. This means that in this example, any juncture rules applied between $a$ and $b$ would have access to the contents of $c$. This is more complex than repeated binary concatenation but has the advantage of being able to use word-global information (such as stress or syllable position within a word).

The concept of $N$-ary concatenation itself does not specify the order in which juncture rules are applied to each juncture. For instance, if the juncture rules consist of three subprocesses A, B, and C, then given a word with three junctures labeled 1, 2, and 3 from start to end, then the rules could trigger in any of the following orders (among other possibilities):

• Apply the subprocesses in sequence to each juncture from start to end: A1, B1, C1, A2, B2, C2, A3, B3, C3
• Apply the subprocesses in sequence to each juncture from end to start: A3, B3, C3, A2, B2, C2, A1, B1, C1
• Apply each subprocess to all junctures from start to end: A1, A2, A3, B1, B2, B3, C1, C2, C3
• Apply subprocesses A and C from start to end but B from end to start: A1, A2, A3, B3, B2, B1, C1, C2, C3
• Apply subprocess A to all junctures, then B and C to each juncture in sequence: A1, A2, A3, B1, C1, B2, C2, B3, C3

In exchange for this flexibility, $N$-ary concatenation has the disadvantage that truncation requires searching a larger space for possible juncture placements.

Case study: Ŋarâþ Crîþ v9e

According to the Ŋarâþ Crîþ v9e grammar, concatenation consists of the following processes applied across the juncture:

1. Any new instances of ⟦j⟧ before ⟦i⟧, ⟦î⟧, or ⟦u⟧ are elided.
2. Deduplication rules are applied.
3. Newly formed bridges are canonicalized and repaired.

We assume that we are working with assemblages in a regular system. Therefore, while a substitution function can be regarded as a composition of multiple functions $f_{n-1}\circ \cdots \circ f_1$, most of these functions will have no effect on concatenation at a given juncture state.

The first process, glide elision, is a right-invariant substitution function based on

$$\begin{array}{lrlr}& h(((\mu ,g,o),(\nu ,o,n)))& =\{\begin{array}{cc}((\epsilon ,g,o),(\nu ,o,n))& \text{i}\text{f}\nu \in \{\text{i},\hat{\text{ı}},\text{u}\}\\ ((\mu ,g,o),(\nu ,o,n))& \text{ otherwise}\end{array}& \end{array}$$

whose preimage is straightforward to compute.

The deduplication rules, which resolve instances of oginiþe cfarðerþ, work as follows:

1. The onset ⟦f⟧ or ⟦tf⟧ followed by a non-hatted vowel then ⟦f⟧ or ⟦p·⟧ is replaced with ⟦t⟧.
2. The onset ⟦þ⟧ or ⟦cþ⟧ followed by a non-hatted vowel then ⟦þ⟧ or ⟦t·⟧ is replaced with ⟦t⟧. In addition, a preceding ⟦þ⟧ or ⟦cþ⟧ coda is replaced with ⟦s⟧, and a preceding ⟦rþ⟧ coda is replaced with ⟦r⟧.
3. ⟦h⟧ followed by a non-hatted vowel then ⟦h⟧ or ⟦c·⟧ is replaced with ⟦p⟧.
4. ⟦v⟧ followed by a non-hatted vowel then ⟦v⟧ or ⟦m·⟧ is replaced with ⟦n⟧.
5. ⟦ð⟧ followed by a non-hatted vowel then ⟦ð⟧ or ⟦d·⟧ is replaced with ⟦ŋ⟧.
6. ⟦ħ⟧ followed by a non-hatted vowel then ⟦ħ⟧ or ⟦g·⟧ is replaced with ⟦g⟧.

In f9i, these rules are implemented twice: once for the case when the vowel in question is followed by a nonterminal coda (thus capturing the following initial), and once for the case when it is followed by a terminal coda (in which case only rules #1 and #2 are applicable). In both cases, the preceding coda is captured if available.

This process is more involved than glide elision, but its preimage is not too difficult to compute, and the process is right-isometric.

The assemblage form makes these changes difficult: the first consonant following a vowel might belong to the coda of the same syllable or to the initial of the following syllable, and it may be part of a complex coda or initial. It also complicates situations in which changing a letter requires the word to be syllabified differently; for this problem, v9e simply chooses to apply bridge resolution after deduplication, although this has the disadvantage of failing to remove some cases of oginiþe cfarðerþ.

Ŋarâþ Crîþ v9e’s deduplication rules are quite crude, prompting ad-hoc workarounds to be made in specific instances of inflection. There are plans in Project Shiva to expand the range of oginiþe cfarðerþ and thus the scope of deduplication, as well as a desire to avoid changing the initial consonant of a word. An even more challenging problem is propagation: if deduplication changes a consonant such that a new instance of oginiþe cfarðerþ arises, then additional invocations of deduplication might be required to resolve it.

The final step of concatenation is bridge resolution, which modifies awkward coda–initial pairs to more convenient ones. This process is also used for canonicalizing these pairs according to the maximal onset principle.

Ŋarâþ Crîþ v9e’s version of this process is complicated by the fact that although v7 allowed ŋ as a coda, v9 does not. When ŋ appeared as a coda, it was changed into r, modifying the preceding vowel. -aŋ, -oŋ, and -uŋ were changed to -or, and -eŋ and -iŋ were changed to -jor. Reflecting this change, bridge resolution first outputs either a true coda or a pseudo-coda of ŋ, subsequently resolving the latter case by applying this change to the vowel. That is, a final of -or might have arisen from one of -or, -aŋ, -oŋ, or -uŋ. Likewise, a final of -jor might have arisen from one of -jor, -jaŋ, -jeŋ, -joŋ, -eŋ, or -iŋ.

Since the number of possible bridges is relatively small, tabulation can be used to implement the preimage of the first step.

Because bridge resolution is right-isometric, Ŋarâþ Crîþ v9e’s concatenation rules as a whole are as well.