# Minimalist Grammar: Construction without Overgeneration

Isidor Konrad Maier  Johannes Kuhn  Jesse Beisegel  Markus Huber-Liebl
Matthias Wolff

###### Abstract

In this paper we give instructions on how to write a minimalist grammar (MG).
In order to present the instructions as an algorithm, we use a variant of
context free grammars (CFG) as an input format. We can exclude overgeneration,
if the CFG has no recursion, i.e. no non-terminal can (indirectly) derive to a
right-hand side containing itself. The constructed MGs utilize licensors/-ees
as a special way of exception handling. A CFG format for a derivation
$A\\_eats\\_B\mapsto^{*}peter\\_eats\\_apples$, where $A$ and $B$ generate
noun phrases, normally leads to overgeneration, e. g., $i\\_eats\\_apples$. In
order to avoid overgeneration, a CFG would need many non-terminal symbols and
rules, that mainly produce the same word, just to handle exceptions. In our
MGs however, we can summarize CFG rules that produce the same word in one item
and handle exceptions by a proper distribution of licensees/-ors. The
difficulty with this technique is that in most generations the majority of
licensees/-ors is not needed, but still has to be triggered somehow. We solve
this problem with $\epsilon$-items called _adapters_.

###### keywords:

Minimalist Grammar , Language Generation , Overgeneration

###### PACS:

07.05.Bx

###### MSC:

68Q42

††journal: Theoretical Computer Science

[inst1]organization=BTU Cottbus-Senftenberg, Chair of Communication
Engineering,addressline=Siemens-Halske-Ring 14, city=Cottbus,
postcode=DE-03046,

[inst2]organization=BTU Cottbus-Senftenberg, Department of Engineering
Mathematics and Numerics of Optimization,addressline=Platz der Deutschen
Einheit 1, city=Cottbus, postcode=DE-03046,

An algorithm is presented to transform a context-free grammar into a
Minimalist Grammar.

Context-free grammars without recursion can be transformed into a Minimalist
Grammar without overgeneration

Minimalist Grammars can work with a smaller lexicon than CFGs as they can
unite several rules generating the same word to one item. The multiple
functionality of the word for several rules is reimplemented with "adapter
items".

The Python implemented algorithm can be found in Maier (2023)

##  1 State of the Art

Minimalist grammars (MG) were developed by Stabler (1997) to mathematically
codify Chomsky’s Minimalist Program (1995). Beim Graben et al. (2019) present
ideas for constructing small MGs of numeral words.

We have extended these ideas to handcraft larger grammars of numerals and
expressions for date and time of day in different languages, see Maier and
Kuhn (2022) and Maier et al. (2022). In the handcrafted grammars we evaded to
use several lexical items with the same non-empty exponents. Instead, each
non-empty morpheme should not have more than one lexical item. This way, we
kept the lexicon small and made lexical parsing easier. Based on the
experiences gained from handcrafting these handy grammars, we have developed a
general algorithm.

Lately, we got the idea of using a format similar to context-free grammars as
the input to transform into an MG.

In Maier and Wolff (2022), we have presented an algorithm to decompose numeral
words into context-free derivation trees. It can deliver us a lot of input
material to build MGs out of.

About the relation between CFGs and MGs it is well-known that MGs without
remnant move are context free, see Kobele (2010).

Amblard (2011) showed that constructions in MGs can be represented as trees
and gave further insights into the complexity of MGs.

Regarding general rules of MG modelling, in Graf (2017) there are ideas on how
constraints can be represented by features in minimalist syntax. In Kobele
(2021) decompositions are modelled with respect to a generalized version of
MGs. Some of the most significant present attempts for MG construction can be
found in Indurkhya (2019) and Ermolaeva (2020). While Indurkhya’s
implementation allows overgeneration, Ermolaeva’s ideas can overcome this
issue by using several lexical items for one word. In Englisch (2019) another
program is offered for computational implementation of Minimalist Syntax.

Stabler (2011a) showed how to turn an MG into a multiple context free grammar
based on theory of Mery et al. (2006), Michaelis (2001) and Harkema (2001).

We intend to avoid overgeneration without duplication of items. However, it is
argued that this task could be moved from the lexica over to the interfaces,
see Graf (2017, 2012); Kobele (2011, 2014).

For the development of minimalist grammars there is a software environment in
LKB-style (Linguistic Knowledge Builder), see Herring (2016). For further
information on LKB see Copestake (2002).

Regarding the question, how small one should sensibly deconstruct morphemes
for an MG model, the payoff is analyzed in Ermolaeva (2021).

##  2 Prerequisites

In this section we give a deeper introduction into the required terms by
providing definitions and some background.

###  2.1 Minimalist Grammars

Minimalist grammars (MGs) are especially well-suited for modelling natural
human language, see Torr (2019); Stabler (2013); Fowlie and Koller (2017);
Versley (2016); Stanojević and Stabler (2018). Within the Chomsky hierarchy
their languages are strictly located between the context-free and context-
sensitive languages (cf. Jäger and Rogers (2012), especially Figure 6).
Minimalist languages are equivalent to multiple context-free languages and
linear context-free rewriting languages (cf. Stabler (2011b)) as well as
mildly context-sensitive languages (cf. Jäger and Rogers (2012)). As those,
they establish an infinite hierarchy strictly between context-free and
context-sensitive languages (cf. Vijay-Shanker and Weir (1994))

A minimalist grammar consists of a lexicon of items, which store an exponent
and syntactic features, and the structure-building functions “merge” and
“move”. The structure-building rules are written in the format

$\displaystyle\text{Rule}\frac{Input1\ (Input2)}{Output}.$

We use a notation originating from Stabler and Keenan (2003) and write it like
in Section II.B of beim Graben et al. (2019). There, exponent and syntactic
part are given inside a bracket, separated by either ‘$::$’ or ‘$:$’.
$\langle\text{exponent}::\text{syntax}\rangle$ means that the item is an
original item from the lexicon and
$\langle\text{exponent}:\text{syntax}\rangle$ means that the item is a derived
item. The separator ‘$\cdot$’ is used as a variable placeholder for either
‘$::$’ or ‘$:$’. The structure-building functions can also be non-final,
meaning that they do not (finally) merge the input items but just connect them
to a chain.

In the following notation of the structure-building rules, the ${\bf q}$s
denote possible parts of a chain, that may be empty. The ${\bf t}$s denote
non-empty lists of features.

Selectors like ${=}f$ trigger a merge with an item of category $f$ and
licensors like $+f$ trigger a move with a non-finally merged item that holds a
licensee $-f$.

merge-1 $\displaystyle\dfrac{\langle e_{\\_}1::{=}f{\bf t}\rangle\quad\langle
e_{\\_}2\cdot\ f\rangle,{\bf q}}{\langle e_{\\_}1e_{\\_}2:{\bf t}\rangle,{\bf
q}}$ (final) merge-2 $\displaystyle\dfrac{\langle e_{\\_}1:{=}f{\bf
t}\rangle,{\bf q_{\\_}1}\quad\langle e_{\\_}2\cdot\ f\rangle,{\bf
q_{\\_}2}}{\langle e_{\\_}2e_{\\_}1:{\bf t}\rangle,{\bf q_{\\_}1,q_{\\_}2}}$
(final) merge-3 $\displaystyle\dfrac{\langle e_{\\_}1\cdot\ {=}f{\bf
t_{\\_}1}\rangle,{\bf q_{\\_}1}\quad\langle e_{\\_}2\cdot\ f{\bf
t_{\\_}2}\rangle,{\bf q_{\\_}2}}{\langle e_{\\_}1:t_{\\_}1\rangle,{\bf
q_{\\_}1},\langle e_{\\_}2:t_{\\_}2\rangle,{\bf q_{\\_}2}}$ (non-final) move-1
$\displaystyle\dfrac{\langle e_{\\_}1:+f{\bf t}\rangle,{\bf q_{\\_}1},\langle
e_{\\_}2:-f\rangle,{\bf q_{\\_}2}}{\langle e_{\\_}2e_{\\_}1:{\bf
t}\rangle,{\bf q_{\\_}1,q_{\\_}2}}$ (final) move-2
$\displaystyle\dfrac{\langle e_{\\_}1:+f{\bf t_{\\_}1}\rangle,{\bf
q_{\\_}1},\langle e_{\\_}2:-f{\bf t_{\\_}2}\rangle,{\bf q_{\\_}2}}{\langle
e_{\\_}1:{\bf t_{\\_}1}\rangle,{\bf q_{\\_}1},\langle e_{\\_}2:{\bf
t_{\\_}2}\rangle,{\bf q_{\\_}2}}$ (non-final)

The left items of the inputs are the active items that “trigger” the
operation, while the right items are the passive. We call them merger/mover
and mergee/movee respectively and we use wordings like:
“Merger $F$ merges (with) a mergee $X$” / “Mover $F$ moves a movee $X$”
“Mergee $X$ is/gets merged by a merger $F$” / “Movee $X$ is/gets moved by a
mover $F$”
At times we simply identify mergers/movers/movees with the symbols
selector/licensor/licensee.

The five operation rules themselves are no alternatives to each other, but it
is entirely determined by (the feature lists of) the input which operation is
triggered, see Amblard (2011). This makes it possible to simply present
structures as graphs.

We may refer to MG items simply by their exponent, if the exponent
unambiguously belongs to one specific item in a MG in context.

###  2.2 Define the input: Context-Free Grammars with Categories

As we intend to present an algorithm that produces MGs, we need to define an
input. We chose “CFGs with categories", as it is similar to a well-known
format that also matches our intuition of the needed input well.

Our definition is based on the underlying definition of CFGs in Hopcroft and
Ullman (1979). We suppose that CFGs with categories offer two advantages in
that

  * 1.

they can be generated well with the numeral decomposer presented in Maier and
Wolff (2022) and

  * 2.

we regard them as a rather intuitive structure of slot-filling.

We present the needed definitions and give some context to each.

######  Definition 1 (Context-Free Grammar with Categories).

A context-free grammar with categories is a context-free grammar in which each
derivation rule $A\mapsto\alpha$ holds a category $\mathcal{C}$ as another
parameter. We will write the rules in the shape

$\displaystyle A\mapsto\alpha\leavevmode\nobreak\ \\#\mathcal{C}$

$A$ is called the (producing) non-terminal (NT) or producer or input of the
rule, $\alpha$ the word or output of the rule and $\mathcal{C}$ the category
of the rule. $\alpha$ is a string out of terminals and non-terminals.
Sometimes we may omit the category, if it is needless to mention in the
present context.

When writing out the word of a rule, we consistently use lower-case letters
for terminals and upper-case for non-terminals. Lower-case Hellenic letters
are used for unspecified words consisting of terminals and non-terminals. We
may use lower-case Latin letters, if the word contains only terminals. The
empty string is denoted by $\epsilon$.

In the eventually produced MG, each rule will be represented by an item
storing

  * 1.

the rule’s word,

  * 2.

the rule’s category as the most important syntactic feature

  * 3.

and potentially some more syntactic features.

When intending to convert a CFG to a MG using our instructions, one will need
to assign the rules to categories, so the MG item of a CFG rule’s word gains
the category of the rule. In order to implement the top category
$\mathcal{C}Fin$, we need to apply our first instruction.

######  Instruction 1:

Add rule $S_{\\_}0\mapsto S\leavevmode\nobreak\ \\#\mathcal{C}Fin$ to the CFG
and reset the start symbol to $S_{\\_}0$

We recommend using categories that refer to the meaning or grammatical
property of the rule’s word. For example ($A\mapsto$ eat) may be category
$\mathcal{C}Action$ or $\mathcal{C}Verb$ and ($B\mapsto$ apples) may be
category $\mathcal{C}Noun$ or $\mathcal{C}NounPlural$ or $\mathcal{C}Food$.
Grammar-based distributions will facilitate making the MG’s language
grammatically correct, while meaning-based distribution will rather facilitate
excluding semantically undesired expressions like ’apples eat apples’.

A trivial way to add categories, would be to give each rule $A\mapsto\alpha$ a
category $\mathcal{C}A$ that simply repeats the rule’s NT. However, in this
case the MG format can rarely offer advantages over the CFG, especially it
cannot work on a smaller lexicon. A major advantage of the MG format is that
it can comprise rules $A\mapsto\alpha$ and $B\mapsto\alpha$ into one item for
$\alpha$ if they get the same category. Using NTs as categories would
eliminate this advantage.

######  Definition 2 (Free/Restricted Non-Terminals).

Given $A$ is a NT in a CFG with categories, $A$ is restricted if there are
rules $B\mapsto\beta\leavevmode\nobreak\ \\#\mathcal{C}$ and
$A\mapsto\alpha\leavevmode\nobreak\ \\#\mathcal{C}$ of one category with
$B\neq A$ but there is no $A\mapsto\beta\leavevmode\nobreak\ \\#\mathcal{C}$.
Otherwise, $A$ is a free NT.

In the MG format, NTs are represented by selectors that target a specific
category. If a NT $A$ is free, then each word of the targeted category can be
derived from $A$. So, the spot that $A$ holds as a placeholder has free access
for all words of the targeted category. Otherwise, if $A$ would be restricted,
then according to the definition there would be a rule $B\mapsto\beta$ that
produces a word in a target category that $A$ cannot produce. In this case,
the access to the spot that $A$ holds as a placeholder, would need to to be
restricted, so that $b$ cannot get there despite belonging to a target
category.

######  Definition 3 (Recursion Free and Category-Recursion Free).

A CFG with categories is recursion-free, if for any NT $A$ and any series of
at least one derivation
$A\mapsto\alpha_{\\_}1\mapsto\alpha_{\\_}2\mapsto\ldots\alpha_{\\_}n$, the NT
$A$ cannot appear in $\alpha_{\\_}n$. If additionally $\alpha_{\\_}n$ cannot
contain a NT symbol producing a rule of the same category as
$A\mapsto\alpha_{\\_}1$, then the CFG is category-recursion free.

The property category-recursion free is significant, because we can prove that
MGs built out of category-recursion free CFGs do not overgenerate, e.g. they
do not generate expressions apart from those that the input CFG does. Any
recursion-free CFG can be made category-recursion free by favorable
distribution of categories. All it needs is a sufficient separation of the
categories, where any pair of rules that violates the condition is separated.

######  Note.

The relation $\succ$ of categories defined as

$\displaystyle\mathcal{C}\ \succ\ \mathcal{C}^{\prime}:\Leftrightarrow$ (1)
$\displaystyle\exists\text{ rules }(A\mapsto\alpha\leavevmode\nobreak\
\\#\mathcal{C}),(A^{\prime}\mapsto\alpha^{\prime}\leavevmode\nobreak\
\\#\mathcal{C}^{\prime}):$ $\displaystyle\exists\text{ derivation
}A\mapsto\alpha\mapsto\ldots\mapsto\omega\text{ with }A^{\prime}\text{ in
}\omega$

is a strict partial order if the overlying CFG is category-recursion free.

##  3 Basic Models for Single CFG rules

In this section we show how a derivation of one CFG word can be transformed
into a derivation of MG items in a vacuum, i.e. we ignore for now that the
grammar may have more items that interfere with the construction. A word - or
output of a rule - can generally be represented as
$s_{\\_}0X_{\\_}1s_{\\_}1X_{\\_}2\ldots X_{\\_}ns_{\\_}n$, where the
$s_{\\_}i$ are strings of terminals and $X_{\\_}j$ are (free or restricted)
non-terminal symbols. We show how the rules $X_{\\_}j\mapsto x_{\\_}j$ with a
string $x_{\\_}j$ of terminals for $j=1,\ldots,n$ can be applied on the word.

We explain the modelling in three steps:

  1. 1.

The 3 basic shapes of a word, where the MG model is the simplest

  2. 2.

Resolve the issue of a NT producing words in several categories

  3. 3.

How to model a word of general shape as a combination of the basic shapes

General notes on the MGs:

  * 1.

Categories whose names end in an apostrophe, as well as categories with an
exponent are auxiliary categories. Auxiliary categories are singletons, i. e.,
they only contain one item.

  * 2.

Some of the (input) items in the grammars are written with a ‘$\cdot$’ instead
of a ‘::’. It means that they could already be derived items, since usually a
preceding adaption of the feature list is necessary before modelling the
derivation from a NT. The adaption procedure is described in Section 4.
As derived items cannot be listed in a lexicon, the following lists of items
should technically be seen as workspaces rather than as grammars.

  * 3.

The workspaces also do not contain any item of category $\mathcal{C}Fin$,
which implies that the given trees are not only incomplete at the bottom, but
also at the top. They are just coutouts of a derivation tree.

  * 4.

It follows from the structure rules that the given items of each workspace
cannot be composed differently than intended. Moreover, the distribution of
licensees/-ors makes sure that a word can be derived from a restricted NT if
and only if it holds the required licensee.

###  3.1 The word shapes easiest to model by MGs

In this subsection we present three different MG workspaces that can generate
the expression $peter\\_eats\\_apples$.

In the trivial case where the expression is a single word without composition,
the MG item would be $\langle
peter\\_eats\\_apples::\mathcal{C}Sentence\rangle$.
Next we present the easy to model words that actually contain NTs.

Case 1. Right-free: We can model the derivation

$\displaystyle peter\\_eats\\_F\mapsto^{*}peter\\_eats\\_apples$

by creating items $\langle
peter\\_eats\\_::{=}\mathcal{C}Food,\mathcal{C}Sentence\rangle$ and $\langle
apples::\mathcal{C}Food\rangle$. The selector ${=}\mathcal{C}Food$ can trigger
a merge1 with any item of the shape
$\langle\ldots\cdot\mathcal{C}Food\rangle$, which would merge the mergee to
the right-hand side:

merge-1 $\displaystyle\dfrac{\langle
peter\\_eats\\_::{=}\mathcal{C}Food,\mathcal{C}Sentence\rangle\quad\langle
apples::\mathcal{C}Food\rangle}{\langle
peter\\_eats\\_apples:\mathcal{C}Sentence\rangle}$ (2)

Merge-2 would only be triggered, if the merger already was a derived item.
Merge-3 would be triggered, if the mergee had licensors left in its feature
list.

Case 2. Two-handed free: We can model the derivation

$\displaystyle P\\_eats\\_F\mapsto^{*}peter\\_eats\\_apples$

by creating items
$\langle\\_eats\\_::{=}\mathcal{C}Food,{=}\mathcal{C}Person,\mathcal{C}Sentence\rangle$,
$\langle apples::\mathcal{C}Food\rangle$ and $\langle
peter::\mathcal{C}Person\rangle$. First, the selector ${=}\mathcal{C}Food$ can
trigger a merge1 with any item of the shape
$\langle\ldots\cdot\mathcal{C}Food\rangle$, which would merge the mergee to
the right-hand side:

merge-1
$\displaystyle\dfrac{\langle\\_eats\\_::{=}\mathcal{C}Food,{=}\mathcal{C}Person,\mathcal{C}Sentence\rangle\quad\langle
apples::\mathcal{C}Food\rangle}{\langle\\_eats\\_apples:{=}\mathcal{C}Person,\mathcal{C}Sentence\rangle}$
(3)

Then the selector $=\mathcal{C}Person$ can trigger another final merge with
any item of the shape $\langle\ldots\cdot\mathcal{C}Person\rangle$. As the
merger is a derived item then, a merge-2 is triggered, which merges the mergee
to the left-hand side:

merge-2
$\displaystyle\dfrac{\langle\\_eats\\_apples:{=}\mathcal{C}Person,\mathcal{C}Sentence\rangle\quad\langle
peter::\mathcal{C}Person\rangle}{\langle
peter\\_eats\\_apples:\mathcal{C}Sentence\rangle}$ (4)

Case 3. Left-restricted: We can model the derivation

$\displaystyle N\\_eats\\_apples\mapsto^{*}peter\\_eats\\_apples$

by creating items
$\langle\\_eats\\_apples::{=}\mathcal{C}Noun,+person,\mathcal{C}Sentence\rangle$
and $\langle peter::\mathcal{C}Noun,-person\rangle$.111The item for $peter$
has been intentionally modelled different here than in the two-handed free
case, since we want to model $N$ as a restricted NT. The selector
${=}\mathcal{C}Noun$ can trigger a merge with any item that has its category
$\mathcal{C}Noun$ as its foremost feature. However, if the mergee has no
licensor $-person$ that matches the mergers $+person$, then the construction
meets a dead end. This way the licensee $+person$ indirectly forbids the merge
with some items of category $\mathcal{C}Noun$, so unsensible expressions like
$stone\\_eats\\_apples$ can be avoided. If
$\langle\\_eats\\_apples::{=}\mathcal{C}Noun,+person,\mathcal{C}Sentence\rangle$
performs a merge with an item of the shape
$\langle\ldots\cdot\mathcal{C}Noun,-person\rangle$, it is a non-final merge-3,
as the mergee has licensors left in its feature list:

merge-3
$\displaystyle\dfrac{\langle\\_eats\\_apples::{=}\mathcal{C}Noun,+person,\mathcal{C}Sentence\rangle\quad\langle
peter::\mathcal{C}Noun,-person\rangle}{\langle\\_eats\\_apples:+person,\mathcal{C}Sentence\rangle,\langle
peter:-person\rangle}$ (5)

Then $+person$ triggers a final move-1, because $-person$ is the only licensor
left in the movees feature list. move1 moves the movee to the left-hand side:

move-1
$\displaystyle\dfrac{\langle\\_eats\\_apples:+person,\mathcal{C}Sentence\rangle,\langle
peter:-person\rangle}{\langle
peter\\_eats\\_apples:\mathcal{C}Sentence\rangle}$ (6)

###  3.2 Non-Terminals with Several Target Categories

In the previous subsection we presented the most basic MG models of CFG words.
However, in each case an NT could only be derived into words of one specific
target category.

But what if we have rules $A\mapsto\alpha\leavevmode\nobreak\ \\#\mathcal{C}$
and $A\mapsto\beta\leavevmode\nobreak\ \\#\mathcal{C}^{\prime}$? Or generally,
if $\mathcal{C}_{\\_}1,\ldots,\mathcal{C}_{\\_}n$ is the set of categories,
for which a rule $A\mapsto\alpha_{\\_}i\leavevmode\nobreak\
\\#\mathcal{C}_{\\_}i$ of the NT $A$ exists?

We resolve the issue, by choosing a main target category $\mathcal{C}_{\\_}m$.
Then, for $i\in\\{1,\ldots,n\\}\setminus\\{m\\}$, introduce $A_{\\_}i$ as a
new auxiliary NT and replace each rule
$A\mapsto\alpha_{\\_}i\leavevmode\nobreak\ \\#\mathcal{C}_{\\_}i$ by two rules
$A\mapsto A_{\\_}i\leavevmode\nobreak\ \\#\mathcal{C}_{\\_}m$ and
$A_{\\_}i\mapsto\alpha_{\\_}i\leavevmode\nobreak\ \\#\mathcal{C}_{\\_}i$. This
way, $A$ has one unique target category $\mathcal{C}_{\\_}m$ and the new
auxiliary NTs $A_{\\_}i$ also have only one unique target category
$\mathcal{C}_{\\_}i$.

As an example, consider the following snippet of a CFG for numerals:

$\displaystyle\ldots$ $\displaystyle\mapsto hundredandA$
$\displaystyle\leavevmode\nobreak\ \\#\mathcal{C}3$ $\displaystyle A$
$\displaystyle\mapsto thirty-B$ $\displaystyle\leavevmode\nobreak\
\\#\mathcal{C}2$ $\displaystyle A$ $\displaystyle\mapsto two$
$\displaystyle\leavevmode\nobreak\ \\#\mathcal{C}1$

Here, the numerals are categorized after their number of digits. Since
$hundredA$ allows 1-digit numerals as well as 2-digit numerals as a suffix,
the NT $A$ targets both category $\mathcal{C}2$ and $\mathcal{C}1$. In order
to resolve this issue, $\mathcal{C}2$ can be chosen as the the main target
category of $A$. Then the rule $A\mapsto two\leavevmode\nobreak\
\\#\mathcal{C}1$ would have to be replaced by two rules $A\mapsto
A_{\\_}1\leavevmode\nobreak\ \\#\mathcal{C}2$ and $A_{\\_}1\mapsto
two\leavevmode\nobreak\ \\#\mathcal{C}1$.

Note that such newly added rules $A\mapsto A_{\\_}i\leavevmode\nobreak\
\\#\mathcal{C}_{\\_}m$ generally have an impact on the relation $\prec$
defined in Equation 1. $\mathcal{C}_{\\_}m$ should be chosen "maximal" with
respect to $\prec$, i.e. so that $\mathcal{C}_{\\_}m\nprec\mathcal{C}_{\\_}i$
for $i=1,\ldots,n$. Then $\prec$ keeps being a strict partial order, if it was
before.

In the present example, if we consider that there is another rule
$B\mapsto\leavevmode\nobreak\ two\leavevmode\nobreak\ \\#\mathcal{C}1$, then
$\mathcal{C}1$ should not be chosen as the main target category of $A$. In
this case, $A\mapsto A_{\\_}1\leavevmode\nobreak\ \\#\mathcal{C}1$,
$A_{\\_}1\mapsto thirty-B\leavevmode\nobreak\ \\#\mathcal{C}2$ and $B\mapsto
two\leavevmode\nobreak\ \\#\mathcal{C}1$ would form a category recursion and
$\prec$ would no longer be a strict order.

In contrast, $\mathcal{C}2$ would be proper choice for the main target
category, since the rule $B\mapsto two\leavevmode\nobreak\ \\#\mathcal{C}1$
with $B$ originating from the word $thirty-B$ of category $\mathcal{C}2$ means
that $\mathcal{C}1\prec\mathcal{C}2$.

Is such proper choice always possible? Yes, unless $\prec$ was not strict
before anyway. Each strict partial order $\prec$ is a subset of a total order
$\prec^{\prime}$, so the "maximum" can be chosen with respect to some fixed
total order $\prec^{\prime}$. Here we can continue our instructions:

######  Instruction 2:

Normalize each NT’s target category:

  * For each NT $A$:

    * If $A$ has rules of more than one category:

      * Choose main category $\mathcal{C}_{\\_}m$ so that neither of the other categories have a word containing a NT that has a rule of $\mathcal{C}_{\\_}m$.

      * For all other categories $\mathcal{C}_{\\_}i$ of $A$:

        * introduce a new auxiliary NT $A_{\\_}i$ and add a rule $A\mapsto A_{\\_}i\leavevmode\nobreak\ \\#\mathcal{C}_{\\_}m$

        * replace all rules $A\mapsto\ldots\leavevmode\nobreak\ \\#\mathcal{C}_{\\_}i$ by $A_{\\_}i\mapsto\ldots\\#\mathcal{C}_{\\_}i$

When the target category of each NT is normalized, one can assess which NT is
free and which is restricted.

######  Instruction 3:

Classify all NTs as free or restricted with respect to Definition 2.

###  3.3 MG model of general word shape

Before the complicated general case we explain two tricks separately in edge
cases.

  1. 1.

Right restricted: We have seen in section 3.1 that that the MG items

$\displaystyle\langle
peter\\_eats\\_::{=}\mathcal{C}Noun,+food,\mathcal{C}Sentence\rangle$
$\displaystyle\text{ and }\langle apples::\mathcal{C}Noun,-food\rangle$

would produce $applespeter\\_eats\\_$, rather than $peter\\_eats\\_apples$.
So, there is no straight way to model the CFG word $peter\\_eats\\_N$ with a
restricted $N$. Instead, the rule $A\mapsto
peter\\_eats\\_N\leavevmode\nobreak\ \\#\mathcal{C}Noun$ can be decomposed
into $A\mapsto peter\\_eats\\_N^{\prime}\leavevmode\nobreak\
\\#\mathcal{C}Noun^{\prime}$ and $N^{\prime}\mapsto N\leavevmode\nobreak\
\\#\mathcal{C}N$. Then the word $N$ can be interpreted as left restricted (as
$N\epsilon$), and $peter\\_eats\\_N^{\prime}$ is right free, as the auxiliary
category $\mathcal{C}N^{\prime}$ is new and unique to $N^{\prime}$. In MG
format the construction is then:

[.merge-1: $\langle peter\\_eats\\_apples:\mathcal{C}Sentence\rangle$
[.$\langle
peter\\_eats\\_::{=}\mathcal{C}Noun^{\prime},\mathcal{C}Sentence\rangle$
][.move-1: $\langle apples:\mathcal{C}Noun\rangle$ [.merge-3:
$\langle\epsilon+food,\mathcal{C}Noun^{\prime}\rangle,\langle
apples:-food\rangle$
[.$\langle\epsilon:{=}\mathcal{C}Noun,+food,\mathcal{C}Noun^{\prime}\rangle$
][.$\langle apples::\mathcal{C}Noun-food\rangle$ ] ] ] ]

Figure 1: Derivation model for a right restricted NT

  2. 2.

Left free: We have seen in Section 3.1 that the MG items

$\displaystyle\langle\\_eats\\_apples::{=}\mathcal{C}Person\rangle$
$\displaystyle\text{ and }\langle peter::\mathcal{C}Person\rangle$

would produce $\\_eats\\_applesPeter$, rather than $Peter\\_eats\\_apples$. As
$\langle\\_eats\\_apples::{=}\mathcal{C}Person\rangle$ is an original lexical
item, ${=}\mathcal{C}Person$ triggers a merge1 that merges $peter$ to the
right-hand side. However, we can remodel the CFG word $P\\_eats\\_apples$ to a
two-handed free $P\\_eats\\_applesO$, where $O$ can perform a neutral
derivation with the rule $O\mapsto\epsilon\leavevmode\nobreak\
\\#\mathcal{C}nix$.222’nix’ means ’nothing’ in a variant of Deutsch (German)
Then the MG construction would work:

[.merge-2 : $\langle peter\\_eats\\_apples:\mathcal{C}Sentence\rangle$
[.merge1 :
$\langle\\_eats\\_apples::{=}\mathcal{C}Person,\mathcal{C}Sentence\rangle$
[.$\langle\\_eats\\_apples::{=}\mathcal{C}nix,{=}\mathcal{C}Person,\mathcal{C}Sentence\rangle$
][.$\langle\epsilon::\mathcal{C}nix\rangle$ ] ][.$\langle
peter::\mathcal{C}Person\rangle$ ] ]

Figure 2: Derivation model for a left free NT

As seen in the edge cases, the way is to introduce auxiliary rules with
auxiliary NTs. The auxiliary NTs are always free as they target their own
unique auxiliary category. By using these auxiliary rules, a word can be
decomposed into several words, so that each of them is either right free or
left restricted or 2-handed free.

Now we consider a general rule $A\mapsto
s_{\\_}0X_{\\_}1s_{\\_}1X_{\\_}2\ldots X_{\\_}ns_{\\_}n\leavevmode\nobreak\
\\#\mathcal{C}$, where the $s_{\\_}i$ are strings of terminals and the
$X_{\\_}j$ are (free or restricted) NTs that target the category
$\mathcal{C}_{\\_}j$.

######  Instruction 4:

Decompose each rule

$\displaystyle A\mapsto s_{\\_}0X_{\\_}1s_{\\_}1X_{\\_}2\ldots
X_{\\_}ns_{\\_}n\leavevmode\nobreak\ \\#\mathcal{C}$

into several rules

$\displaystyle A$ $\displaystyle\mapsto s_{\\_}0$ $\displaystyle A^{\prime}:$
$\displaystyle\mathcal{C}$ $\displaystyle A^{\prime}$ $\displaystyle\mapsto
X_{\\_}1s_{\\_}1$ $\displaystyle A^{\prime\prime}:$
$\displaystyle\mathcal{C}^{\prime}$ $\displaystyle\vdots$ $\displaystyle
A^{(i)}$ $\displaystyle\mapsto X_{\\_}is_{\\_}i$ $\displaystyle A^{(i+1)}:$
$\displaystyle\mathcal{C}^{(i)}$ $\displaystyle\vdots$ $\displaystyle A^{(n)}$
$\displaystyle\mapsto X_{\\_}ns_{\\_}n:$ $\displaystyle\mathcal{C}^{(n)},$

under usage of the following exceptions:

  * 1.

If $s_{\\_}0$ is $\epsilon$, summarize the first two rules to $A\mapsto
X_{\\_}1s_{\\_}1A^{\prime\prime}$.

  * 2.

If $s_{\\_}n$ is $\epsilon$ and $X_{\\_}n$ is free, summarize the last two
rules to $A^{(n-1)}\mapsto
X_{\\_}{n-1}s_{\\_}{n-1}X_{\\_}n:\mathcal{C}^{(n-1)}$.

  * 3.

For $i=1,\ldots,n-1$, if $X_{\\_}i$ is restricted, replace the rule
$A^{(i)}\mapsto X_{\\_}is_{\\_}iA^{(i+1)}:\mathcal{C}^{(i+1)}$ by two rules
$A^{(i)}\mapsto X^{\prime}_{\\_}is_{\\_}iA^{(i+1)}:\mathcal{C}^{(i+1)}$ and
$X^{\prime}_{\\_}i\mapsto X_{\\_}i:\mathcal{C}^{\prime}_{\\_}i$.

  * 4.

If $X_{\\_}n$ is free and $s_{\\_}n$ is not $\epsilon$, then replace
$A^{(n)}\mapsto X_{\\_}ns_{\\_}n$ by two rules $A^{(n)}\mapsto
X_{\\_}ns_{\\_}nO:\mathcal{C}^{(n)}$ and $O\mapsto\epsilon:\mathcal{C}nix$.

The last two exceptions utilize the right restricted and left free edge cases
respectively. Funnily enough, these "edge cases" only appear at the edges of
word in general, so the wording makes sense in several ways.

After following this instruction, all rules of the CFG are either right free
or left restricted or 2-handed free or entirely terminal.

######  Instruction 5:

For each right free word $wordX$ of category $\mathcal{C}$ create a MG item

$\displaystyle\langle word::{=}\mathcal{C}(X),\mathcal{C}\rangle.$

For each 2-handed free word $YwordX$ of category $\mathcal{C}$ create a MG
item

$\displaystyle\langle
word::{=}\mathcal{C}(X),{=}\mathcal{C}(Y),\mathcal{C}\rangle.$

For each left restricted word $Yword$ of category $\mathcal{C}$ create a MG
item

$\displaystyle\langle word::{=}\mathcal{C}(Y),+a_{\\_}Y,\mathcal{C}\rangle.$

For each terminal word $word$ of category $\mathcal{C}$ create a MG item

$\displaystyle\langle word::\mathcal{C}\rangle.$

######  Definition 4 (Word Item).

All MG items introduced in Instruction 5 are called word items, as they
represent a (part of a) CFG word.

######  Instruction 6:

Give to each MG item $\langle word::\ldots\mathcal{C}\rangle$ \- which
represents the CFG word $wordX$, $YwordX$, $Yword$ or $word$ in category
$\mathcal{C}$ \- one licensee $-a_{\\_}R$ for each restricted NT $R$ that
generates its CFG word.

##  4 From Basic Models to Complete MGs

In Section 3, we have shown how to MG model a direct derivation of one CFG
word. In the presented minimal examples, many obstacles do not appear yet.
In a real application however, there are several words and many NTs and each
word may be derivable from several NTs. Possibly also from several restricted
NTs, in which case by Instruction 6 it would hold several licensees that could
interfere with each other.

The problem and the evolution of the solution is explained in the following
example:
The Deutsch333Endonym for German numeral ‘vier’ can be extended to larger
numerals like ‘vierzehn’, ‘vierzig’ or ‘vierundzwanzig’. We start modelling
this with the following items:

$\displaystyle\langle\text{zig}::{=}\mathcal{C}1,+zi,\mathcal{C}2\rangle$
$\displaystyle\langle\text{zehn}::{=}\mathcal{C}1,+zeh,\mathcal{C}2\rangle$
$\displaystyle\langle\text{undzwanzig}::{=}\mathcal{C}1,+un,\mathcal{C}2\rangle$
$\displaystyle\langle\text{vier}::\mathcal{C}1,-zi,-zeh,-un\rangle$

This way ‘vier’ has a proper licensee for either extension.
However, the present items are not sufficient for proper constructions, which
we demonstrate in the following elucidating cases:

  * 1.

In order to construct ‘vierzehn’ we would merge ‘zehn’ and ‘vier’. As ‘vier’
has features left in its feature list apart from its category, a non-final
merge-3 is triggered:

$\displaystyle\text{merge-3:}\
\dfrac{\langle\text{zehn}::{=}\mathcal{C}1,+zeh,\mathcal{C}2\rangle\quad\langle\text{vier}::\mathcal{C}1,-zi,-zeh,-un\rangle}{\langle\text{zehn}:+zeh,\mathcal{C}2\rangle,\langle\text{vier}:-zi,-zeh,-un\rangle}$

Then we would meet a dead end, where the merged items cannot perform a
$zeh$-triggered move before at least the unneeded licensee $-zi$ is removed.
When and how to remove $-zi$? The next case demonstrates, whether such
unneeded licensees should be removed before or after the merge.

  * 2.

For constructing ‘vierzig’ we would merge ‘zig’ and ‘vier’ - again non-
finally:

$\displaystyle\text{merge-3:}\
\dfrac{\langle\text{zig}::{=}\mathcal{C}1,+zi,\mathcal{C}2\rangle\quad\langle\text{vier}::\mathcal{C}1,-zi,-zeh,-un\rangle}{\langle\text{zig}:+zi,\mathcal{C}2\rangle,\langle\text{vier}:-zi,-zeh,-un\rangle}$

Now a move would be triggered as intended, but since ‘vier’ has further
licensees left in its feature list it would lead to a non-final move:

$\displaystyle\text{move-2:}\
\dfrac{\langle\text{zig}:+zi,\mathcal{C}2\rangle,\langle\text{vier}:-zi,-zeh,-un\rangle}{\langle\text{zig}:\mathcal{C}2\rangle,\langle\text{vier}:-zeh,-un\rangle}$

As already seen in the first example, there are licensees left to be
triggered. Another problem is that ‘zig’ and ‘vier’ are still not merged
finally. Since all the features - that are responsible for the correct final
merge - are triggered already, a correct construction can no longer be
guaranteed.
Regarding the question, whether the leftover licensee should be triggered
before or after the merge: If we added items that allow to remove $-zeh$ and
$-un$ after the merge, we could still not guarantee that they are removed
before the $zi$-triggered move. Then we still could not exclude wrong
constructions. So, we rather remove unneeded features before the merge.

Conclusion: Before a word item is merged by another, all its unneeded features
have to be removed.

In the next subsection, we explain how to remove unneeded features.

###  4.1 Adapters

We call the removal of features ’adapting’. Adapting is done with adapter
items. An adapter item holds a selector ${=}\mathcal{C}$ of its own category
$\mathcal{C}$ and one or more licensors. This way it can merge with another
item of its category $\mathcal{C}$ and trigger some of its licensees, while
the category of the construction remains unchanged. Since adapter items can
only adapt the items of their own category specifically, we are able to
influence that items of CFG words have to be adapted before they get merged by
another word’s item.

The most basic way of adapting is to remove the foremost licensee $-a$ of an
item of category $\mathcal{C}$ by merging with
$\langle\epsilon::{=}\mathcal{C},+a,\mathcal{C}\rangle$ and then moving
$a$-triggered. These items are called remove adapters.

######  Instruction 7:

For each licensee $-a$ that appears in some item of category $\mathcal{C}$ in
your lexicon, add a remove adapter
$\langle\epsilon::{=}\mathcal{C},+a,\mathcal{C}\rangle$.

The required remove adapters for the present example are:

$\displaystyle\langle\epsilon 1::{=}\mathcal{C}1,+zi,\mathcal{C}1\rangle$
$\displaystyle\langle\epsilon 2::{=}\mathcal{C}1,+zeh,\mathcal{C}1\rangle$
$\displaystyle\langle\epsilon 3::{=}\mathcal{C}1,+un,\mathcal{C}1\rangle$

With these remove adapters we can generate ‘vierundzwanzig’ in the present
grammar, see Figure 3.

[.move-1 [.merge-1
[.$\langle$undzwanzig$::{=}\mathcal{C}1,+un,\mathcal{C}2\rangle$
][.move-2:$\langle\epsilon:\mathcal{C}1\rangle,\langle$vier$:-un\rangle$
[.merge-1 [.$\epsilon 2$ ][.move-2 [.merge-3 [.$\epsilon 1$ ][.vier ] ] ] ] ]
] ]

Figure 3: Derivation tree of ‘vierundzwanzig’. Since the needed licensee is
the last in the feature list, ‘vier’ can be adapted just with remove adapters.
This special case causes that ‘vier’ is merged-1 by ‘undzwanzig’, instead of a
merge-3 as in the examples in Section 3. The outcome is the same, though.

If we instead wanted to generate ‘vierzig’ or ‘vierzehn’, then we would need
to keep a licensee - $-zi$ or $-zeh$ respectively - while removing other
licensees further back - $-zeh$ and $-un$ or only $-un$ respectively. We use
items called select adapters for that, which remove all licensees except for
the foremost.
For the present example we need the following select adapters:444A select
adapter $\langle\epsilon::{=}\mathcal{C}1,+un,c1,-un\rangle$ for $-un$ is not
needed, as can be seen in Figure 3. However, it can be helpful to introduce
one to make the constructions more uniform and thus easier adaptable for e. g.
the addition of semantics.

$\displaystyle\langle\epsilon::{=}\mathcal{C}1,+zi,+zeh,+un,\mathcal{C}1,-zi\rangle$
$\displaystyle\langle\epsilon::{=}\mathcal{C}1,+zeh,+un,\mathcal{C}1,-zeh\rangle$

With the select adapters added we can bring ‘vier’ into any shape in which it
keeps none or one arbitrary of its licensees—except for the last, whose case
is covered in Figure 3—by following this procedure:

  1. 1.

As long as the foremost licensee of the word item is unneeded:
Remove it by merging and moving with the related remove adapter.

  2. 2.

Then: If there are still unneeded licensees in the feature list: Merge with
the related select adapter and perform moves until all its licensors are
triggered.

An example for a typical adapting procedure is given in Figure 4.

[.move-1:$\langle$vier$:\mathcal{C}1,-zeh\rangle$ [.move-2 [.merge-1
[.$\langle\epsilon::{=}\mathcal{C}1,+zeh,+un,\mathcal{C}1,-zeh\rangle$
][.move-2:$\langle\epsilon:\mathcal{C}1\rangle,\langle$vier$:-zeh,-un\rangle$
[.merge-3 [.$\langle\epsilon::{=}\mathcal{C}1,+zi,\mathcal{C}1\rangle$
][.$\langle$vier$::\mathcal{C}1,-zi,-zeh,-un\rangle$ ] ] ] ] ] ]

Figure 4: ‘vier’ gets adapted in such a way that all licensees except $-zeh$
are removed, so it can construct ‘vierzehn’. First, $-zi$ is removed with a
remove adapter. Then the select adapter for $-zeh$ removes $-un$ while keeping
$-zeh$.

Thus, ‘vier’ can flexibly turn into any shape where it holds one or none of
its original licensees.
Any adapting procedure that is finished by a final move-1 - such as in Figure
4 \- gives the word item the adapted shape that is called for in the
workspaces presented in Section 3. A final move occurs, when the backmost
licensee of the word item is triggered. This happens in every adapting
procedure, unless it is the backmost licensee that is needed to model the
derivation from a restricted NT. This is showcased in Figure 3. There, ‘vier’
turns into the adapted shape
$\langle\epsilon:\mathcal{C}1\rangle,\langle$vier$:-un\rangle$. Then the first
item of the chain has no more features apart from its category, so it is
merged-1 finally instead of a non-final merge-3. After that however,
constructions are the same as those showcased in Section 3.

######  Instruction 8:

For each licensee $-x$ and each non-empty sequence $-t$ of licensees that
appears behind $-x$ in the feature list of some item of some category
$\mathcal{C}$, add a select adapter
$\langle\epsilon::{=}\mathcal{C},+x,+t,\mathcal{C},-x\rangle$, where $+t$
denotes the sequence of the licensors corresponding to the licensees in $-t$.

Once select adapters are added, we have a grammar that allows each word item
to use any single of its licensees or none of them during its derivation.

So the desired MG would be finished.

However, there is an efficiency problem evolving from Instruction 8 which we
discuss in the next subsection.

###  4.2 A Sorting Problem for Efficiency

In this subsection, we discuss a complexity issue that occurs during
Instruction 8. The issue is not an essential part of this paper, but rather an
outlook on how the algorithm could be optimized towards building smaller MG
lexica.

Instruction 8 can blow up the lexicon with select adapters for different
orders of licensees, since the number of combinations tends to grow quickly.
Also, many of these select adapters would be restricted to a single use case,
since a select adapter
$\langle\epsilon::{=}\mathcal{C},+x,+y,+z,\mathcal{C},-x\rangle$ only works
for items whose feature list end in $\dots,-x,-y,-z\rangle$. Thus, we might
need many select adapters just for $-x$, especially if the licensees are
sorted in an unfavorable way.
Therefore, it is desirable to sort the licensees in such a way that the
feature lists of as many word items as possible match as long as possible when
read from the back.
For a demonstration we present the following lexicon:

$\displaystyle\langle\text{zehn}::{=}\mathcal{C}1,+zeh,\mathcal{C}2\rangle$
$\displaystyle\langle\text{undzwanzig}::{=}\mathcal{C}1,+un,\mathcal{C}2\rangle$
$\displaystyle\langle\text{zig}::{=}\mathcal{C}1,+zi,\mathcal{C}2\rangle$
$\displaystyle\langle\text{eins}::\mathcal{C}1\rangle$
$\displaystyle\langle\text{zwei}::\mathcal{C}1,-un\rangle$
$\displaystyle\langle\text{drei}::\mathcal{C}1,-zeh,-un\rangle$
$\displaystyle\langle\text{vier}::\mathcal{C}1,-zi,-zeh,-un\rangle$
$\displaystyle\langle\text{fünf}::\mathcal{C}1,-zi,-zeh,-un\rangle$
$\displaystyle\langle\text{sechs}::\mathcal{C}1,-un\rangle$
$\displaystyle\langle\text{sieben}::\mathcal{C}1,-un\rangle$
$\displaystyle\langle\text{acht}::\mathcal{C}1,-un\rangle$
$\displaystyle\langle\text{neun}::\mathcal{C}1,-zi,-zeh,-un\rangle$

In the given lexicon, the licensees in the feature lists of the word items
(category $\mathcal{C}1$) are always sorted in such a way that the more
frequent licensees are further back. This allows us to adapt all word items
arbitrarily (so that exactly one arbitrary licensee or no licensee remains)
with the following adapter items alone:

Remove adapters:
$\displaystyle\langle\epsilon::{=}\mathcal{C}1,+zi,\mathcal{C}1\rangle$
$\displaystyle\langle\epsilon::{=}\mathcal{C}1,+zeh,\mathcal{C}1\rangle$
$\displaystyle\langle\epsilon::{=}\mathcal{C}1,+un,\mathcal{C}1\rangle$ Select
adapters:
$\displaystyle\langle\epsilon::{=}\mathcal{C}1,+zi,+zeh,+un,\mathcal{C}1,-zi\rangle$
$\displaystyle\langle\epsilon::{=}\mathcal{C}1,+zeh,+un,\mathcal{C}1,-zeh\rangle$

In the present example, the sorting is simple because the item sets of the
three licensees form a series of inclusions, i. e., $I(un)\supset
I(zeh)\supset I(zi)$, given $I(a)$ denotes the set of items that hold $-a$.
In general, however, the item sets of the licensees can be disjoint or
partially overlapping. An especially unfortunate distribution has already been
found in the ‘Sorbian Clock’ grammar in Maier and Kuhn (2022). In this case,
smart sorting becomes complicated and requires advanced mathematical methods.

##  5 How Overgeneration is avoided

In this section we give insights into why MGs constructed out of category-
recursion free CFGs do not overgenerate.

The insights are no proof by any means, as leaving out many minor and
technical aspects leads to logical flaws. The full proof can be found in A.

First we explain, how category-recursion can cause overgeneration.

Consider a derivation $wordX\mapsto word\alpha$ caused by the rule
$X\mapsto\alpha\leavevmode\nobreak\ \\#\mathcal{C}$. If there is a category-
recursion in the grammar, $\alpha$ could (indirectly) derive another rule of
category $\mathcal{C}$. In MG format this would mean that there is an MG
construction on top of
$\langle\underline{\alpha}::\ldots\mathcal{C},\ldots\rangle$555Here,
$\underline{\alpha}$ denotes the word $\alpha$ under omission of NTs that
again has category $\mathcal{C}$. Then
$\langle\underline{\alpha}::\ldots\mathcal{C},\ldots\rangle$ is not
necessarily forced to trigger all its unneeded licensees before being merged
by another word’s item. Instead, it could potentially trigger some of its
licensee later, if the construction gets back to category $\mathcal{C}$. In
the mean time, operations would not go according to plan.

An example: Consider the lexicon

$\displaystyle\langle apple::\mathcal{C}NP,-t\rangle$
$\displaystyle\langle\epsilon::{=}\mathcal{C}NP,+t,\mathcal{C}NP\rangle$
$\displaystyle\langle sour\\_::{=}\mathcal{C}NP,\mathcal{C}NP\rangle$

Here, ’apple’ is a noun phrase that for whatever purpose holds a licensee
$-t$, which a remove adapter exists for, and ’sour’ is an adjective that is
modelled as a noun phrase requiring another noun phrase with a free NT.
The remove adapter can be used to remove the $-t$ from ’apple’, so ’sour’ can
perform a merge-1 on ’apple’ to form the grammatical noun phrase ’sour_apple’.
However, since the category is again $\mathcal{C}NP$ after the merge, as it
was before, the remove shaper can also be applied afterwards, which causes the
misconstruction ’applesour_’:

[.move-1: $\langle apple\epsilon sour\\_:\mathcal{C}NP\rangle$ [.merge-1:
$\langle\epsilon sour\\_:+t,\mathcal{C}NP\rangle,\langle apple:-t\rangle$
[.$\langle\epsilon::{=}\mathcal{C}NP,+t,\mathcal{C}NP\rangle$ ][.merge-3:
$\langle sour\\_:\mathcal{C}NP\rangle,\langle apple:-t\rangle$ [.$\langle
sour\\_::{=}\mathcal{C}NP,\mathcal{C}NP\rangle$ ][.$\langle
apple::\mathcal{C}NP,-t\rangle$ ] ] ] ]

Figure 5: Category recursion allows ungrammatical arrangement of exponents

’applesour_’ is ungrammatical, since it cannot be generated by the underlying
CFG.666Even if probably there is a cocktail called like that

We can avoid misconstruction, if word items trigger all licensees of the
mergees directly after the merge.

The present discussion contains the most important argument for the following
auxiliary result:

######  Theorem.

Let $G$ be a MG that is constructed out of a category-recursion free CFG
following the instructions in this paper. Let $l$ be a legal expression of
$G$. Let $f,x$ be lexical or derived item of $G$, so that a merge of $f$ with
$x$ is part of the construction of $l$. Then $f$ and $x$ have the shapes

$\displaystyle
x=\langle\ldots\cdot\mathcal{C},-t_{\\_}1,\ldots,t_{\\_}m\rangle$
$\displaystyle
f=\langle\ldots\cdot{=}\mathcal{C},+t_{\\_}1,\ldots,+t_{\\_}m,a,\ldots\rangle,$

where $a$

  * 1.

is either a category, selector or licensor, but it

  * 2.

is not a licensor, if $\mathcal{C}(f)\neq\mathcal{C}(x)$.

The theorem mirrors the results of Theorem 3 and it is proven in A. It
requires many auxiliary results beforehand to prove that each licensee has to
be triggered after a word item gets merged. The graph in Figure 6 shows
headlines of all used auxiliary results, arranged in a graph of dependencies:

Figure 6: Graph of auxiliary results (represented by headlines) used to prove
Theorem 3.3. The arrows indicate that each result used all parent results in
order to be proven.

Next, we describe, how it follows from the auxiliary result that a MG
constructed out of a category-recursion free CFG does not overgenerate.

We call the feature sequence ${=}\mathcal{C},+t_{\\_}1,\ldots,+t_{\\_}m$ the
foremost selector-licensor block of $f$, The theorem can be interpreted so
that

  * 1.

a merger $f$’s foremost selector-licensor block needs to correspond to the
start of its mergee $x$’s feature list and

  * 2.

when a mergee $x$ gets merged by a merger with
$\mathcal{C}(f)\neq\mathcal{C}(x)$, $f$’s foremost selector-licensor block has
to match $x$’s entire feature list exactly.

Note that $\mathcal{C}(f)\neq\mathcal{C}(x)$ whenever $f$ represents a CFG
word, otherwise there would be a category-recursion in the CFG. Considering
the equivalence

$\displaystyle f\text{ is not an adapter}\Leftrightarrow f\text{ is a word
item }\Leftrightarrow\mathcal{C}(f)\neq\mathcal{C}(x),$

we may rephrase the meaning of Theorem Theorem to: An item $x$ can be merged
by

  * 1.

a shaper item, if the shapers foremost selector-licensor block corresponds to
$x$’s foremost features

  * 2.

a word item, if the word item’s foremost selector-licensor block corresponds
to $x$’s entire feature list.

Based on these interpretations, we can fully describe, by what kind of merger
items a mergee item of $x$’s shape can be merged until it is merged by a word
item (see Figure7).

Figure 7: All possible legal paths of derivation from an item of shape
$\langle E\cdot\mathcal{C},-t_{\\_}1,\dots,-t_{\\_}n\rangle$ or
$\langle\epsilon:\mathcal{C}\rangle,\langle
E:-t_{\\_}1,\dots,-t_{\\_}n\rangle$. Each arrow represents a merge- and
potential consecutive move-operation(s) performed on the item that the arrow
goes out of. The markers remove/select indicate that the arrow’s merge- and
move-operation(s) are triggered by a remove/select adapter.

It can be seen that merges by word’s items only happen in such ways as they
are described in Subsection 3.1. This way, we can show that misconstructions
such as ’applesour_’ do not appear.

##  6 Summary and Results

We have presented the following algorithm to turn a CFG with categories into a
MG:

  1. 1.

Add rule $S_{\\_}0\mapsto S\leavevmode\nobreak\ \\#\mathcal{C}Fin$ to the CFG
and reset the start symbol to $S_{\\_}0$

  2. 2.

Normalize each NT’s target category:

     * For each NT $A$:

       * If $A$ has rules of more than one category:

         * Choose main category $\mathcal{C}_{\\_}m$ so that neither of the other categories have a word containing a NT that has a rule of $\mathcal{C}_{\\_}m$.

         * For all other categories $\mathcal{C}_{\\_}i$ of $A$:

           * introduce a new auxiliary NT $A_{\\_}i$ and add a rule $A\mapsto A_{\\_}i\leavevmode\nobreak\ \\#\mathcal{C}_{\\_}m$

           * replace all rules $A\mapsto\ldots\leavevmode\nobreak\ \\#\mathcal{C}_{\\_}i$ by $A_{\\_}i\mapsto\ldots:\mathcal{C}_{\\_}i$

  3. 3.

Classify all NTs as free or restricted with respect to Definition 2

  4. 4.

Decompose each rule

$\displaystyle A\mapsto s_{\\_}0X_{\\_}1s_{\\_}1X_{\\_}2\ldots
X_{\\_}ns_{\\_}n\leavevmode\nobreak\ \\#\mathcal{C}$

into several rules

$\displaystyle A$ $\displaystyle\mapsto s_{\\_}0$ $\displaystyle A^{\prime}:$
$\displaystyle\mathcal{C}$ $\displaystyle A^{\prime}$ $\displaystyle\mapsto
X_{\\_}1s_{\\_}1$ $\displaystyle A^{\prime\prime}:$
$\displaystyle\mathcal{C}^{\prime}$ $\displaystyle\vdots$ $\displaystyle
A^{(i)}$ $\displaystyle\mapsto X_{\\_}is_{\\_}i$ $\displaystyle A^{(i+1)}:$
$\displaystyle\mathcal{C}^{(i)}$ $\displaystyle\vdots$ $\displaystyle A^{(n)}$
$\displaystyle\mapsto X_{\\_}ns_{\\_}n:$ $\displaystyle\mathcal{C}^{(n)},$

under usage of the following exceptions:

     * (a)

If $s_{\\_}0$ is $\epsilon$, summarize the first two rules to $A\mapsto
X_{\\_}1s_{\\_}1A^{\prime\prime}$.

     * (b)

If $s_{\\_}n$ is $\epsilon$ and $X_{\\_}n$ is free, summarize the last two
rules to $A^{(n-1)}\mapsto
X_{\\_}{n-1}s_{\\_}{n-1}X_{\\_}n:\mathcal{C}^{(n-1)}$.

     * (c)

For $i=1,\ldots,n-1$, if $X_{\\_}i$ is restricted, replace the rule
$A^{(i)}\mapsto X_{\\_}is_{\\_}iA^{(i+1)}:\mathcal{C}^{(i+1)}$ by two rules
$A^{(i)}\mapsto X^{\prime}_{\\_}is_{\\_}iA^{(i+1)}:\mathcal{C}^{(i+1)}$ and
$X^{\prime}_{\\_}i\mapsto X_{\\_}i:\mathcal{C}^{\prime}_{\\_}i$.

     * (d)

If $X_{\\_}n$ is free and $s_{\\_}n$ is not $\epsilon$, then replace
$A^{(n)}\mapsto X_{\\_}ns_{\\_}n$ by two rules $A^{(n)}\mapsto
X_{\\_}ns_{\\_}nO:\mathcal{C}^{(n)}$ and $O\mapsto\epsilon:\mathcal{C}nix$.

  5. 5.

For each right free word $wordX$ of category $\mathcal{C}$ create a MG item

$\displaystyle\langle word::{=}\mathcal{C}(X),\mathcal{C}\rangle.$

For each 2-handed free word $YwordX$ of category $\mathcal{C}$ create a MG
item

$\displaystyle\langle
word::{=}\mathcal{C}(X),{=}\mathcal{C}(Y),\mathcal{C}\rangle.$

For each left restricted word $Yword$ of category $\mathcal{C}$ create a MG
item

$\displaystyle\langle word::{=}\mathcal{C}(Y),+a_{\\_}Y,\mathcal{C}\rangle.$

For each terminal word $word$ of category $\mathcal{C}$ create a MG item

$\displaystyle\langle word::\mathcal{C}\rangle.$

  6. 6.

Give to each MG item $\langle word::\ldots\mathcal{C}\rangle$ \- which
represents the CFG word $wordX$, $YwordX$, $Yword$ or $word$ in category
$\mathcal{C}$ \- one licensee $-a_{\\_}R$ for each restricted NT $R$ that
generates its CFG word.

  7. 7.

For each licensee $-a$ that appears in some item of category $\mathcal{C}$ in
your lexicon, add a remove adapter
$\langle\epsilon::{=}\mathcal{C},+a,\mathcal{C}\rangle$

  8. 8.

For each licensee $-x$ and each non-empty sequence $-t$ of licensees that
appears behind $-x$ in the feature list of some item of some category $C$, add
a select adapter
$\langle\epsilon::{=}\mathcal{C},+x,+t,\mathcal{C},-x\rangle$, where $+t$
denotes the sequence of the licensors corresponding to the licensees in $-t$.

The implementation can be found in Maier (2023).
In Maier and Kuhn (2022) we uploaded MG lexica that are designed based on the
ideas of the presented algorithm. They generate numerals words in Deutsch,
English, French, Mandarin and Upper Sorbian, as well as date and time of day
expressions in Upper Sorbian. For the Upper Sorbian language sets (word
classes), we also created FST lexica and discussed the pros and cons of FSTs
and MGs in Sections 2.1. and 2.2. of Maier et al. (2022). We concluded that
MGs can work with significantly smaller lexica than FSTs do, especially if the
grammar becomes more complicated. In particular, MGs can deal more efficiently
with iteration and with dependency between non-adjacent morphemes. Table 1
shows sizes of MG lexica and some FST and CFG lexica and underlines our
conclusions on a small sample size.

Language | MG | FST | CFG
---|---|---|---
English Numerals $<10^{6}$ | 40 | - | 39
Deutsch Numerals $<10^{6}$ | 56 | - | 75
French Numerals $<10^{6}$ | 66 | - | 81
Mandarin Numerals $<10^{8}$ | 63 | - | 53
Upper Sorbian Numerals $<10^{15}$ | 131 | 356 | 188
Upper Sorbian Times of Day | 133 | 1479 | 75
Upper Sorbian Dates | 133 | 118 | 210
YYYY-MM-DD | 56 | - | 82
Table 1: Lexicon sizes for different languages in MG, FST and CFG format

For the MG lexica the sorting problem of licensees has been dealt with
manually. As can be seen, MGs can often operate on similar or smaller sized
lexicon than CFGs, with 2 exceptions:

  * 1.

For the Mandarin numerals many words with inner inputs were used, e.g. for
$E,\textit{qi\={a}n},O,P,D\mapsto^{*}\textit{èr qi\={a}n líng y\={\i} shí
y\={\i}}$ (by word: two-thousand-zero-one-eleven). For MG format the rule
would have to be decomposed in many rules in Instruction 4, which causes the
MG lexicon to be bigger than the CFG lexicon. However, many CFG applications -
e.g. the Cocke-Younger-Kasami algorithm - ask for a CFG normal form anyway
that would not allow inner NTs either.

  * 2.

The Sorbian Clock is an unfortunate case where the licensees have an
especially high degree of mutual overlap. This is because the licensees
control the agreement between number words for time and daytime words, e.g.
’at nine in the morning’ is desired, while ’at nine in the afternoon’ is not.
This agreement naturally has much overlap, since the boundaries between e.g.
morning and noon are blurred

##  7 Outlook

We presented an algorithm on how to transform a CFG into a MG that generates a
desired language without overgeneration. In Graben et al. (2019) semantic
terms were introduced into MGs. So, their inclusion into the algorithm is
naturally desired.

Apart from Stabler’s original MG style, there are also further implementations
of the Minimalist Program which the presented algorithm could be adapted to,
see Graf (2012) and Stabler (2011c). We assume that this can work again by
determining the word shapes that are easiest to MG model and then use a
decomposition into those shapes, similar as in Instruction 4.

Since MGs have been compared with multiple context-free grammars in the past,
see Mery et al. (2006), a similar MCFG-to-MG algorithm may be concievable.

In Subsection 4.2, we presented a basic idea how to ideally sort the licensees
in the feature lists, such that less select adapters are required in the
lexicon. More detailed ideas have yet been applied in the construction of the
‘Sorbian Clock’ grammar in Maier and Kuhn (2022). The ideas can be extended to
a general sorting algorithm. The goal of the sorting algorithm would be to
sort the licensees in such a way that as many given feature lists as possible
match as long as possible when read from the back.

The usual questions about runtime and effect of such an algorithm can then be
included in the evaluation of the utility: How much more useful is a lexicon
with a few powerful (select adapter) items compared to a lexicon with a mass
of single-use (select adapter) items? How do the resulting MGs compare to
other grammar formats like, e. g., Finite State Transducers?

As the proposed instructions are ideal for grammars without recursions, a good
field of application is numeral grammars, as they have a clear hierarchy. In
Maier and Wolff (2022) we have proposed an algorithm to decompose numerals.
Based on the determined compositions, numeral systems of over 250 natural
languages can be presented as a CFG and then transformed into a MG. The
producable grammars can also be automatically equipped with number semantics.
This way, valuable resources can be produced for speech technology of peculiar
languages.

The algorithm facilitates the production of a bigger database of minimalist
grammars, which may even evade overgeneration. MGs constructed with the
present algorithm offer an explanation for each feature. Since MGs naturally
also have a strong distinction between code and lexicon, they are especially
well-suited for explainable AI methods, such as language learning algorithms,
potentially even for spontaneous speech.

## References

  * Amblard (2011) Amblard, M., 2011.  Minimalist grammars and minimalist categorial grammars, definitions toward inclusion of generated languages.  arXiv:1108.5096.
  * Chomsky (1995) Chomsky, N., 1995.  The Minimalist Program.  MIT Press.  doi:10.7551/mitpress/9780262527347.001.0001.
  * Copestake (2002) Copestake, A., 2002.  Implementing typed feature structure grammars. volume 110.  CSLI publications Stanford.
  * Englisch (2019) Englisch, J., 2019.  Implementing minimalist syntax and remove.  Structure Removal .
  * Ermolaeva (2020) Ermolaeva, M., 2020.  Induction of minimalist grammars over morphemes.  Proceedings of the Society for Computation in Linguistics 3, 484–487.  doi:10.7275/jed1-5j57.
  * Ermolaeva (2021) Ermolaeva, M., 2021.  Deconstructing syntactic generalizations with minimalist grammars, in: Proceedings of the 25th Conference on Computational Natural Language Learning, Association for Computational Linguistics, Online. pp. 435–444.  URL: https://aclanthology.org/2021.conll-1.34, doi:10.18653/v1/2021.conll-1.34.
  * Fowlie and Koller (2017) Fowlie, M., Koller, A., 2017\.  Parsing minimalist languages with interpreted regular tree grammars, in: Proceedings of the 13th International Workshop on Tree Adjoining Grammars and Related Formalisms, pp. 11–20.
  * Graben et al. (2019) Graben, P.b., Römer, R., Meyer, W., Huber, M., Wolff, M., 2019.  Reinforcement learning of minimalist numeral grammars, in: 2019 10th IEEE International Conference on Cognitive Infocommunications (CogInfoCom), pp. 67–72.  doi:10.1109/CogInfoCom47531.2019.9089924.
  * Graf (2012) Graf, T., 2012.  Movement-generalized minimalist grammars, in: International Conference on Logical Aspects of Computational Linguistics, Springer. pp. 58–73.  doi:10.1007/978-3-642-31262-5_4.
  * Graf (2017) Graf, T., 2017.  A computational guide to the dichotomy of features and constraints.  Glossa: a journal of general linguistics 2, 18.  doi:10.5334/gjgl.212.
  * Harkema (2001) Harkema, H., 2001.  A characterization of minimalist languages, in: de Groote, P., Morrill, G., Retoré, C. (Eds.), Logical Aspects of Computational Linguistics, Springer, Berlin, Heidelberg. pp. 193–211.  doi:10.1007/3-540-48199-0_12.
  * Herring (2016) Herring, J., 2016.  Grammar construction in the Minimalist Program.  Ph.D. thesis. Indiana University.
  * Hopcroft and Ullman (1979) Hopcroft, J.E., Ullman, J.D., 1979\.  Introduction to Automata Theory, Languages and Computation.  Addison-Wesley.
  * Indurkhya (2019) Indurkhya, S., 2019.  Automatic inference of minimalist grammars using an smt-solver.  CoRR abs/1905.02869.  URL: http://arxiv.org/abs/1905.02869, doi:10.48550, arXiv:1905.02869.
  * Jäger and Rogers (2012) Jäger, G., Rogers, J., 2012\.  Formal language theory: refining the chomsky hierarchy.  Philosophical Transactions of the Royal Society B: Biological Sciences 367, 1956–1970.  URL: http://dx.doi.org/10.1098/rstb.2012.0077, doi:10.1098/rstb.2012.0077.
  * Kobele (2010) Kobele, G.M., 2010.  Without remnant movement, mgs are context-free, in: Ebert, C., Jäger, G., Michaelis, J. (Eds.), The Mathematics of Language, Springer Berlin Heidelberg, Berlin, Heidelberg. pp. 160–173.
  * Kobele (2011) Kobele, G.M., 2011.  Minimalist tree languages are closed under intersection with recognizable tree languages, in: International Conference on Logical Aspects of Computational Linguistics, Springer. pp. 129–144.  doi:10.1007/978-3-642-22221-4_9.
  * Kobele (2014) Kobele, G.M., 2014.  Meeting the boojum.  Theoretical Linguistics 40, 165–173.  doi:10.1515/tl-2014-0007.
  * Kobele (2021) Kobele, G.M., 2021.  Minimalist grammars and decomposition.  Submitted.
  * Maier (2023) Maier, I., 2023.  CFG-to-MG-algorithm.  URL: https://github.com/ikmMaierBTUCS/CFG-to-MG-algorithm.
  * Maier and Kuhn (2022) Maier, I., Kuhn, J., 2022.  Minimalist Grammars - Numerals and expressions for date and time of day.  URL: https://github.com/ikmMaierBTUCS/Minimalist-Grammars/.
  * Maier et al. (2022) Maier, I., Kuhn, J., Duckhorn, F., Kraljevski, I., Sobe, D., Wolff, M., Tschöpe, C., 2022.  Word class based language modeling: A case of upper sorbian, in: Proceedings of The Workshop on Resources and Technologies for Indigenous, Endangered and Lesser-resourced Languages in Eurasia within the 13th Language Resources and Evaluation Conference, European Language Resources Association, Marseille, France. pp. 28–35.  URL: https://aclanthology.org/2022.eurali-1.5.
  * Maier and Wolff (2022) Maier, I., Wolff, M., 2022.  Poster: Decomposing numerals, in: EUNICE Science Dissemination: Poster Competition.  URL: https://www.b-tu.de/en/communications-engineering/publications/papers#c314785, doi:10.5281/zenodo.7501698.
  * Mery et al. (2006) Mery, B., Amblard, M., Durand, I., Retoré, C., 2006\.  A Case Study of the Convergence of Mildly Context-Sensitive Formalisms for Natural Language Syntax: from Minimalist Grammars to Multiple Context-Free Grammars.  Technical Report. INRIA.
  * Michaelis (2001) Michaelis, J., 2001.  On Formal Properties of Minimalist Grammars. volume 13 of Linguistics in Potsdam.  Universitätsbibliothek, Publikationsstelle, Potsdam.
  * Stabler (1997) Stabler, E., 1997.  Derivational minimalism, in: Retoré, C. (Ed.), Logical Aspects of Computational Linguistics, Springer Berlin Heidelberg, Berlin, Heidelberg. pp. 68–95.  doi:10.1007/BFb0052152.
  * Stabler (2011a) Stabler, E., 2011a.  Top-down recognizers for MCFGs and MGs, in: Proceedings of the 2nd Workshop on Cognitive Modeling and Computational Linguistics, Association for Computational Linguistics, Portland, Oregon, USA. pp. 39–48.  URL: https://aclanthology.org/W11-0605.
  * Stabler (2013) Stabler, E., 2013.  Two models of minimalist, incremental syntactic analysis.  Topics in cognitive science 5.  doi:10.1111/tops.12031.
  * Stabler (2011b) Stabler, E.P., 2011b.  After government and binding theory, in: van Benthem, J.F.A.K., ter Meulen, A. (Eds.), Handbook of Logic and Language. 2nd ed.. Elsevier, p. 395–414.  URL: http://dx.doi.org/10.1016/B978-0-444-53726-3.00007-4, doi:10.1016/b978-0-444-53726-3.00007-4.
  * Stabler (2011c) Stabler, E.P., 2011c.  Computational perspectives on minimalism.  Oxford handbook of linguistic minimalism , 617–643doi:10.1093/oxfordhb/9780199549368.013.0027.
  * Stabler and Keenan (2003) Stabler, E.P., Keenan, E.L., 2003\.  Structural similarity within and among languages.  Theoretical Computer Science 293, 345–363.  URL: https://www.sciencedirect.com/science/article/pii/S0304397501003516, doi:https://doi.org/10.1016/S0304-3975(01)00351-6. algebraic Methods in Language Processing.
  * Stanojević and Stabler (2018) Stanojević, M., Stabler, E., 2018\.  A sound and complete left-corner parsing for minimalist grammars, in: Proceedings of the Eight Workshop on Cognitive Aspects of Computational Language Learning and Processing, pp. 65–74.  doi:10.18653/v1/W18-2809.
  * Torr (2019) Torr, P., 2019.  Wide-coverage statistical parsing with minimalist grammars.  Ph.D. thesis. University of Edinburgh.
  * Versley (2016) Versley, Y., 2016.  Discontinuity (re) 2-visited: A minimalist approach to pseudoprojective constituent parsing, in: Proceedings of the Workshop on Discontinuous Structures in Natural Language Processing, pp. 58–69.  doi:10.18653/v1/W16-0907.
  * Vijay-Shanker and Weir (1994) Vijay-Shanker, K., Weir, D.J., 1994\.  The equivalence of four extensions of context-free grammars.  Mathematical Systems Theory 27, 511–546.  URL: http://dx.doi.org/10.1007/BF01191624, doi:10.1007/bf01191624.

##  Appendix A Proof of Functionality and Exactness

In this section,

  * 1.

$J$ is an arbitrary CFG with categories,

  * 2.

$I$ is the CFG with categories constructed out of $J$ by Instructions 1-4 in
Section 6 and

  * 3.

$G$ is an MG constructed out of $I$ by the remaining instructions.

Remember that the terms ’word’ and ’rule’ always refer to CFGs and ’item’ and
’operation’ always refer to MGs.

We show that every expression generatable by $J$ is generatable by $G$ and
that - if $J$ is category-recursion free - the reverse is also true.

First, we show that $I$ and $J$ have the same language.

######  Theorem 1.

$I$ and $J$ have the same language.

###### Proof.

By Instruction 4, $I$ is made out of $J$ by seperating rules of the shape
$A\mapsto s_{\\_}0X_{\\_}1s_{\\_}1\ldots X_{\\_}ns_{\\_}n$ into many rules.
(Also, some rules are united to one in the instruction, but this only affects
rules that have been united in $J$ but intermediately separated in the
process)

It is obvious that the separated rules in $I$ combined can generate anything
that the united rule in $J$ can. So, $L(J)\subseteq L(I)$. We need to show the
reverse.

Consider a legal derivation in $I$ that uses a rule that does not exist in
$J$. Then this rule has been created in Instruction 4 in order to represent
the $i$th terminal string of a word $\alpha$ from a rule $A\mapsto\alpha$ that
exists in $J$.777It could also be $S_{\\_}0\mapsto S$, but this rule has no
impact on the language. We call the rule $A_{\\_}i\mapsto\alpha_{\\_}i$. We
show that it is inevitable then that all separated parts of $A\mapsto\alpha$
are used, so $A\mapsto\alpha$ gets reconstructed in any case.

Note that $A_{\\_}i\mapsto\alpha_{\\_}i$ contains at least one auxiliary NT,
i.e. either $\alpha_{\\_}i$ contains one or $A$ is one (or both). Auxiliary
NTs are unique, i.e. they have only one occurrence in words and only one rule.
So,

  * 1.

if $A_{\\_}i$ is auxiliary then there is one rule
$A_{\\_}{i-1}\mapsto\alpha_{\\_}{i-1}$ where $\alpha_{\\_}{i-1}$ contains
$A_{\\_}i$ and

  * 2.

if $\alpha_{\\_}i$ contains the auxiliary NT $A_{\\_}{i+1}$ there is one rule
$A_{\\_}{i+1}\mapsto\alpha_{\\_}{i+1}$.

By studying Instruction 4, one can notice that the rule(s)
$A_{\\_}{i-1}\mapsto\alpha_{\\_}{i-1}$ and/or
$A_{\\_}{i+1}\mapsto\alpha_{\\_}{i+1}$ are also separated parts of
$\overline{A}\mapsto\overline{\alpha}$. So, by induction the abovementioned
properties of $A_{\\_}i\mapsto\alpha_{\\_}i$ can also be applied on
$A_{\\_}j\mapsto\alpha_{\\_}j$ for any $j$th component rule of
$A\mapsto\alpha$. Thus, the derivation can only be continued with a unique
combinable rule that also evolved from the separation of $A\mapsto\alpha$. The
derivation path of the generation and derivation of auxiliary NTs around
$A_{\\_}i\mapsto\alpha_{\\_}i$ cannot use other rules than those constructed
in Instruction 4 until $A^{0}=A$ is not auxiliary at the upper end and until
$\alpha_{\\_}n=\alpha$ contains no auxiliary NTs at the lower end. Then the
derivation around $A_{\\_}i\mapsto\alpha_{\\_}i$ comprises all rules of the
separation of $A\mapsto\alpha$ and combined they reproduce $A\mapsto\alpha$.
Thus, any rule $A_{\\_}i\mapsto\alpha_{\\_}i$ in $I$, separated from a united
rule $A\mapsto\alpha$ in $J$ cannot generate anything beyond what
$A\mapsto\alpha$ can. Hence, $L(I)\subseteq L(J)$ and $L(J)=L(I)$.

∎

From now it suffices to show the equivalence of $I$ and $G$.

######  Theorem 2.

Each legal expression of $I$ is a legal expression of $G$.

###### Proof.

A construction in $I$ can be presented as a tree (see Figure 8).

Figure 8: Here, each edge represents a derivation rule
$N_{\\_}w\mapsto[N_{\\_}{wl}]s_{\\_}w[N_{\\_}{wr}]$, with a series
$w\in\\{r,l\\}^{*}$ of indexes, $s_{\\_}w$ a string of terminals and
$N_{\\_}{wl}$ and $N_{\\_}{wr}$ the potential left and right NTs.
Consequently, each edge represents a CFG word and has one outgoing edge for
each of the word’s NTs. This way the graph reflects the hierarchy of the
resulting MG items

The leaves of the tree have no NTs. So, following Instruction 5, they are
initially created as simple MG items $\langle X::\mathcal{C}_{\\_}X\rangle$
with their word/exponent $X$ and category $\mathcal{C}_{\\_}X$. By Instruction
6 they may gain a list of licensees, so they finally have the shape $\langle
X::\mathcal{C}_{\\_}X,-a_{\\_}1,\ldots,-a_{\\_}n\rangle$ in the MG lexicon.
All words in the tree’s lowest tier are of this shape. In the second lowest
tier, there is at least one word $[N_{\\_}{wl}]s_{\\_}w[N_{\\_}{wr}]$
containing at least one NT, otherwise there would not be a tier below.

Let $F$ be such a word of 2nd lowest tier and let $X$ be the leaf word that is
derived from $F$’s NT. In case $F$ is a two-handed free word, let $X$
represent the two leaf words $(X_{\\_}1,X_{\\_}2)$ that are derived from $F$’s
NTs. The shape of $F$ is $\langle
F::{=}\mathcal{C}_{\\_}X,\mathcal{C}_{\\_}F\rangle$ or $\langle
F::{=}\mathcal{C}_{\\_}{X1},{=}\mathcal{C}_{\\_}{X2},\mathcal{C}_{\\_}F\rangle$
or $\langle F::{=}\mathcal{C}_{\\_}X,+a_{\\_}X,\mathcal{C}_{\\_}F\rangle$, if
$F$ is right-free or 2-handed-free or left-restricted respectively.

The MG items of $F$ and $X$ have the same shape as the respective items in
Section 3.1 \- $F$ being the merger and $X$ the mergee(s) respectively -
except that each of them may hold more licensees in their feature list than
required.

If $F$ has such a list of licensees, it would not impact the construction. In
the structure-building rules shown in Subsection 2.1 one can see that the
merger or mover may have a chain ($t$ or $t_{\\_}1$) that would persist any
merge- or move-operation.

If (one of the components of) $X$ with the shape $\langle
X::\mathcal{C}_{\\_}X,-a_{\\_}1,\ldots,-a_{\\_}n\rangle$ has an overshoot of
licensees, it can be adapted as described in Section 4. This way it can get an
adapted shape $\langle X::\mathcal{C}_{\\_}X\rangle$ or $\langle
X::\mathcal{C}_{\\_}X,-a_{\\_}i\rangle$ for $i\lneq n$, so the construction
would work as intended.

In order to use the licensee $-a_{\\_}n$ one can use $n-1$ remove adapters to
produce the shape $\langle\epsilon:\mathcal{C}_{\\_}X\rangle,\langle
X:-a_{\\_}n\rangle$. Then the construction can be continued as in Figure 3 and
again produce the intended output. In its way, it deviates slightly from the
cases in Section 3.1, as a final merge1 on
$\langle\epsilon:\mathcal{C}_{\\_}X\rangle,\langle X:-a_{\\_}n\rangle$
replaces a non-final merge3 on $\langle
X:\mathcal{C}_{\\_}X,-a_{\\_}n\rangle$. However, both operations lead to the
same outcome.

In order to use another licensee $-a_{\\_}i$, one can use $i-1$ remove shapers
and one select shaper to produce the shape
$\langle\epsilon:\mathcal{C}_{\\_}X\rangle,\langle X:-a_{\\_}i\rangle$.

In order to use no licensee, one can use $n$ remove shapers to produce the
shape $\langle\epsilon:\mathcal{C}_{\\_}X\rangle,\langle X:-a_{\\_}i\rangle$.

In either case, a shape could be produced that can undergo the same operations
as in Section 3.1. Thus, the derivation of leaf words from the NT(s) of an
item of 2nd lowest tier can be performed as a construction in MG format.

Once the derivation is performed a derived MG item $\langle
F(X):\mathcal{C}_{\\_}F,a_{\\_}1,\ldots,a_{\\_}n\rangle$ is obtained with the
exponent $F(X)\in\\{FX,XF,X_{\\_}2FX_{\\_}1\\}$.The derived item $F(X)$ has
the same shape as a leaf item, except that it is derived. This difference
cannot matter anymore, as it would only split the difference between
triggering a merge1 or a merge2. But $F(X)$ does not have any selectors to
trigger a merge, so it behaves just like a leaf item in advance. By recursion,
we can conclude that derivations of 3rd lowest tier words’ NTs to 2nd lowest
tier words - and generally $n$th tier words’ NTs to $(n+1)$th tier words - can
also be performed as intended.

Hence each arbitrary construction in $I$ \- as presented in the tree - is also
constructable in $G$. ∎

Before we can state and prove the reverse of this theorem, we need many
auxiliary results.

###  A.1 Auxiliary Results

####  A.1.1 Classification of Lexical Items in $G$ and Merge Criteria

In order to delimit what $G$ could potentially generate, we aim to classify
what merges can happen in the construction of a legal expression in $G$.
Merges are the operations that make the difference, while Moves are just
automatic consequences of Merges.

First, we profile the lexical items of $G$ based on the instructions:

######  Observation 1.

Each lexical item in $G$ has the shape profile:

$\displaystyle\langle
E::A_{\\_}1,\ldots,A_{\\_}n,\mathcal{C},-t_{\\_}1,\ldots,-t_{\\_}m\rangle,$

where

  * 1.

$m,n\in\mathbb{N}_{\\_}0$, $n\leq 2$

  * 2.

$E$ is the exponent

  * 3.

for $i=1,\dotsc,n$: $A_{\\_}i$ is a selector-licensor-block
${=}\mathcal{C}_{\\_}i,+a_{\\_}{i,1},\dotsc,+a_{\\_}{i,l(i)}$, where

    * (a)

$l(i)\in\mathbb{N}_{\\_}0$

    * (b)

${=}\mathcal{C}_{\\_}i$ is the selector of some category $\mathcal{C}_{\\_}i$

    * (c)

$+a_{\\_}{i,1},\dotsc,+a_{\\_}{i,l(i)}$ are licensors

  * 4.

$\mathcal{C}$ is the category

  * 5.

$-t_{\\_}1,\dotsc,-t_{\\_}m$ are licensees

More specifically, we can differentiate:

######  Observation 2 (Classification of lexical items).

Each lexical item in $G$ belongs to one of the types listed in the following
table:

Type | Shape |  Notable properties
---|---|---
Word items | $\langle E::[A_{\\_}1],[A_{\\_}2],\mathcal{C},-t_{\\_}1,\dotsc,-t_{\\_}m\rangle$ |  $n\leq 2$ $n=1\Rightarrow l(1)\leq 1$ $n=2\Rightarrow l(1)=l(2)=0$ Represents a word in $I$
Remove adapters | $\langle\epsilon::{=}\mathcal{C},+a,\mathcal{C}\rangle$ |  $E=\epsilon$, $n=1$, $\mathcal{C}_{\\_}1=\mathcal{C}$, $l(1)=1$ and $m=0$
Select adapters | $\langle\epsilon::{=}\mathcal{C},+a_{\\_}1,\dotsc,+a_{\\_}l,\mathcal{C},-a_{\\_}1\rangle$ |  $E=\epsilon$, $n=1$, $\mathcal{C}_{\\_}1=\mathcal{C}$, $l(1)\geq 2$, $m=1$ and $-t_{\\_}1$ corresponds to $+a_{\\_}{1,1}$.
Table 3: Classification of lexical items

The variables $m,n\ldots$ in Table 2 refer to the notation in Observation 1.

######  Note.

The item $\langle\epsilon::\mathcal{C}nix\rangle$ is also profiled as a word
item in Observation 2, as it represents the word $\epsilon$ of the rule
$O\mapsto\epsilon\leavevmode\nobreak\ \\#\mathcal{C}nix$.

Next, we analyse under which conditions two items can merge.

######  Theorem 3.

Let $f,x$ be lexical or derived888We used notation $\cdot$ for either ’$::$’
(lexical) or ’$:$’ (derived), see Sect. 2.1 items of $G$ with the shape

$\displaystyle f=\langle E\cdot
A_{\\_}1,\ldots,A_{\\_}n,\mathcal{C}_{\\_}f,-t_{\\_}1,\ldots,-t_{\\_}m\rangle$
$\displaystyle x=\langle E^{\prime}\cdot
A^{\prime}_{\\_}1,\ldots,A^{\prime}_{\\_}{n^{\prime}},\mathcal{C}_{\\_}x,-t^{\prime}_{\\_}1,\ldots,-t^{\prime}_{\\_}{m^{\prime}}\rangle$

with

$\displaystyle
A_{\\_}j={=}\mathcal{C}_{\\_}j,+a_{\\_}{j,1},\ldots,+a_{\\_}{j,l(j)}\text{ for
}j=1,\ldots,n$ $\displaystyle
A^{\prime}_{\\_}j={=}\mathcal{C}^{\prime}_{\\_}j,+a^{\prime}_{\\_}{j,1},\ldots,+a^{\prime}_{\\_}{j,l^{\prime}(j)}\text{
for }j=1,\ldots,n^{\prime}.$

If $f$ and $x$ merge - as merger and mergee respectively - at any point of the
construction of a legal derivation tree in $I$, then

  1. 1.

$n^{\prime}=0$ and $\mathcal{C}_{\\_}1=\mathcal{C}_{\\_}x$.

  2. 2.

$m^{\prime}\geq l(1)$ and $a_{\\_}{1,i}=t^{\prime}_{\\_}i\ \forall i\leq
l(1)$.

  3. 3.

if $I$ is category-recursion free and
$\mathcal{C}_{\\_}f\neq\mathcal{C}_{\\_}x$, then $m^{\prime}=l(1)$

###### Proof.

  1. 1.

If $n^{\prime}\neq 0$, then there is a selector in front of the category,
which would have to be triggered before the merge. If
$\mathcal{C}_{\\_}1\neq\mathcal{C}_{\\_}x$, then the merger’s selector and the
mergee’s category do not correspond, so a merge would be illegal.

  2. 2.

A merge of $f$ with $x$ produces

$\displaystyle\langle
E:+a_{\\_}{1,1},\ldots,+a_{\\_}{1,l(1)},A_{\\_}2,\ldots,A_{\\_}n,\mathcal{C}_{\\_}f,-t_{\\_}1,\ldots,-t_{\\_}m\rangle,\langle
E^{\prime}:-t^{\prime}_{\\_}1,\ldots,-t^{\prime}_{\\_}{m^{\prime}}\rangle.$

Then $+a_{\\_}{1,1}$ would trigger a move with a corresponding
$-a_{\\_}{1,1}$. If $-t^{\prime}_{\\_}1\neq-a_{\\_}{1,1}$, the move could not
be performed, so the construction would meet a dead end and no legal
derivation tree could be formed. Thus $-t^{\prime}_{\\_}1=-a_{\\_}{1,1}$ and a
move would be performed. After that, a corresponding licensee for
$+a_{\\_}{1,2}$ would be needed, which must be $-t^{\prime}_{\\_}2$. By
induction, $-t^{\prime}_{\\_}i$ has to correspond to $a_{\\_}{1,i}$ for
$i=1,\ldots,l(1)$, so $l(1)\leq m^{\prime}$.

  3. 3.

Proven later at the end of A.1.3.

∎

We will prove Statement 3 of Theorem 3 at the end of A.1.3. First, we need
more definitions and auxiliary results. All auxiliary results used to prove it
are also arranged in the dependency graph in Figure 6.

####  A.1.2 Classification of Derived Items in $G$

Recently, we have classified lexical items in $G$. Next, we go ahead and
classify derived items. We only consider derived items upon which a legal
expression is derivable, while we might not always mention this restriction.

######  Definition 5 (Self-Triggered and (Purely) Externally Triggered
Derivation).

Let $x$ be a (lexical or derived) item in $G$ and let $y$ be an item derived
from $x$, including the possibility $y=x$.

  * 1.

$y$ is a _self-triggered_ derivation of $x$, if all merges involved in the
derivation are triggered by $x$’s selectors. If $p_{\\_}1,\ldots,p_{\\_}n$
with $n\leq 2$ are the mergees of the self-triggered derivation
chronologically, we write

$\displaystyle y=x(p_{\\_}1,\ldots,p_{\\_}n).$

  * 2.

$y$ is a _purely externally triggered_ derivation of $x$, if no merges
involved in the derivation are triggered by $x$’s selectors. Let
$m_{\\_}1,\ldots,m_{\\_}n$ be the - lexical or derived - mergers of the purely
externally triggered derivation chronologically. If all $m_{\\_}i$ have only
one selector, then we can write

$\displaystyle y=m_{\\_}n\bigr{(}\ldots
m_{\\_}2\bigr{(}m_{\\_}1(x)\bigl{)}\bigl{)}.$

However, if some $m_{\\_}i$ has 2 selectors, then $m_{\\_}{i+1}$ cannot merge
it, until $m_{\\_}i$ has triggered its 2nd selector to merge with some co-
mergee $q_{\\_}i$. So, generally we need to write

$\displaystyle
y=m_{\\_}n\bigl{(}\ldots\bigl{(}m_{\\_}2\bigl{(}m_{\\_}1(x,[q_{\\_}1]),[q_{\\_}2]\bigr{)},[q_{\\_}3]\bigr{)}\ldots\bigr{)}.$
(7)

By defining

$\displaystyle m^{q}(x):=m(x,q),$

we can shorten Equation 7 to

$\displaystyle
y=m_{\\_}n^{[q_{\\_}n]}\bigl{(}...m_{\\_}1^{[q_{\\_}1]}(x)\bigr{)}\text{ or}$
$\displaystyle y=m_{\\_}n^{[q_{\\_}n]}\circ...\circ m_{\\_}1^{[q_{\\_}1]}(x),$

where $m^{[q]}(x)$ implies that $q$ may not necessarily exist.

  * 3.

$y$ is an _externally triggered_ derivation of $x$, if not all merges involved
in the derivation are triggered by $x$’s selectors. If chronologically
$m_{\\_}1,\ldots,m_{\\_}n$ are the mergers, $q_{\\_}i$ is the potential co-
mergee of $m_{\\_}i$ and $p_{\\_}1,\ldots,p_{\\_}k$ are the mergees merged by
$x$, we write

$\displaystyle y=m_{\\_}n^{[q_{\\_}n]}\circ...\circ
m_{\\_}1^{[q_{\\_}1]}\bigl{(}x(p_{\\_}1,...,p_{\\_}k)\bigr{)}$ (8)

Generally, from now we will often often write $\overline{y}$ to name an item
that $y$ is derived from and $\hat{x}$ for an item derived from $x$.

######  Note.

For a - lexical or derived - item $x$ in $G$

  * 1.

any derivation $y$ can be presented as in Equation 8 with
$n,k\in\mathbb{N}_{\\_}0$. It follows that any derived item $y$ is a self-
triggered derivation of some item $\overline{y}$. In the equation,
$\overline{y}$ is $m_{\\_}n$, if $n>0$, and $\overline{y}=x$ otherwise.

  * 2.

a self-triggered derivation of $x$ has the same category and licensees as $x$.

######  Definition 6 (Adapted derivation).

An adapted derivation is an externally triggered derivation, where all mergers
are adapter items.

######  Lemma 1 (Adapted derivations retain category and licensees).

Let $x$ be an item and $y$ an adapted derivation of $x$ that is part of a
legal derivation tree. Then, item $x$ has the same category as $y$ and $y$’s
set of licensees is a subset of the licensees of $x$.

###### Proof.

An adapted derivation can involve self-triggered operations and operations
triggered by adapters. Self-triggered operations have no impact on category or
licensees.

Now it suffices to prove the theorem for $y$ being a purely externally
triggered adapted derivation of $x$. Since all mergers are adapters, none of
them has 2 selectors, so none of them merges a co-mergee. Thus
$y=m_{\\_}n\circ\ldots\circ m_{\\_}1(x)$ with adapter items
$m_{\\_}1,...,m_{\\_}n$.

It suffices to prove the statement for just $n=1$ adapter item, so
$y=m_{\\_}1(x)$, then it follows by induction that any number $n\in\mathbb{N}$
of adapter items will never change the category or add new licensees.

$m_{\\_}1(x)$ has the same category as $x$, as adapters can only merge items
of the category they hold, so they cannot change the category.

Can $m_{\\_}1$ bring additional licensees to $x$?

Remove adapters have no licensees so they cannot enrich $x$’s list of
licensees.

Select adapters have one licensee $-a$, but they also hold the corresponding
$+a$ as their foremost licensor in their only selector-licensor block. By
Statement 2 of Theorem 3 the select adapter can only merge $x$, if $x$ also
has $-a$ as its foremost licensee. Then $x$’s $-a$ would be triggered by the
adapters $+a$ in the consecutive move. So, select adapters do not enrich the
list of licensees either. ∎

######  Lemma 2 (Classification of merger items in $G$).

When an item $x$ in $G$ triggers a merge during the construction of a legal
derivation tree, then $x$ is either an adapter item or a word item or a self-
triggered derivation of a word item.

###### Proof.

Let $x$ be an item in $G$. $x$ needs a selector to trigger its merge. If $x$
is lexical, then by Observation 2 it can only be an adapter item or a word
item.

If $x$ is derived, then it is a self-derivation of some lexical
$\overline{x}$. The lexical item $\overline{x}$ has at least two selectors,
one for the merge to become $x$ and one for the merge that $x$ triggers. So,
since only word items can have more than one selector, $x$ can only be a self-
derivation of a word item $\overline{x}$, if it is derived. ∎

######  Lemma 3 (Classification of derived items in $G$).

Each derived item $x$ in $G$ \- that is not lexical - is an adapted derivation
of a lexical word item.

###### Proof.

Let $x$ be a non-lexical item. First, note that $x$ is derived from some word
item. As $x$ is lexical, its construction involves an initial merge with a
lexical mergee, which by Statement 1 of Theorem 3 cannot have any selector. By
Observation 2, the initial mergee can only be a word, which $x$ is eventually
derived from.

Let $w$ be a lexical word item, which $x$ is derived from. Then $w$ has a
self-triggered derivation $\hat{w}=w(\ldots)$ so that

$\displaystyle x=m_{\\_}n^{[q_{\\_}n]}\circ\ldots\circ
m_{\\_}1^{[q_{\\_}1]}(\hat{w})$

with mergers $m_{\\_}1,\ldots,m_{\\_}n$ and co-mergees $q_{\\_}i$ for all
$m_{\\_}i$ with 2 selectors.

Each $m_{\\_}i$ (first) merges $m_{\\_}{i-1}^{[q_{\\_}{i-1}]}\circ\ldots\circ
m_{\\_}1^{[q_{\\_}1]}(x)$, regardless whether or not it has a co-mergee
$q_{\\_}i$. So by Lemma 2, each $m_{\\_}i$ is either an adapter or (a self-
triggered derivation of) a word $\overline{m_{\\_}i}$. If all $m_{\\_}i$ are
adapters, then $x=m_{\\_}n\circ\ldots\circ m_{\\_}1(\hat{w})$ is an adapted
derivation of the lexical word $w$. Otherwise, let $z$ be the largest index
such that $\overline{m_{\\_}{z}}$ is a word item. Then
$m_{\\_}{z+1},...,m_{\\_}{n}$ are adapter items and $m_{\\_}{z}$ is a self-
triggered derivation of $\overline{m_{\\_}{z}}$, so

$\displaystyle x=m_{\\_}n\circ\ldots\circ
m_{\\_}{z+1}\bigl{(}\underbrace{m_{\\_}{z}\bigl{(}m_{\\_}{z-1}(\ldots),[q_{\\_}z]\bigr{)}}_{\\_}{=\overline{m_{\\_}z}(\ldots)}\bigr{)}$

is an adapted derivation of the lexical word $\overline{m_{\\_}{z}}$.∎

######  Definition 7 (Head Word).

The head word of a derived item in $G$ is the lexical word item of which it is
an adapted derivation. The definition may also be used for a lexical word
item, which is the head word of itself.

####  A.1.3 Impact of Category-Recursion in $I$ on $G$

In this section we show that, if $I$ is category-recursion free, $G$ has a
similar property.

######  Lemma 4 (Detection of CFG rules).

Let $\phi$ and $\chi$ be words (right-hand sides) of CFG rules in $I$ and let
$\mathcal{C}_{\\_}{\phi}$ and $\mathcal{C}_{\\_}{\chi}$ be their categories.
Let

$\displaystyle F=\langle
f::A_{\\_}{1},...,A_{\\_}{n},\mathcal{C}_{\\_}{\phi},\ldots\rangle$
$\displaystyle\text{and }X=\langle
x::\ldots\mathcal{C}_{\\_}\chi,-t_{\\_}1,\ldots,-t_{\\_}m\rangle$

with $n\leq 2$ be the MG items created with Instruction 5 representing the CFG
words $\phi$ and $\chi$. Their exponents $f$ and $x$ equal $\phi$ and $\chi$
under omission of NTs respectively.

If one of the $A_{\\_}{i}$ equals either ${=}\mathcal{C}_{\\_}{\chi}$ or
${=}\mathcal{C}_{\\_}{\chi},+t_{\\_}j$ for some $j\leq m$, then there is a
non-terminal $N$ that generates $\chi$ and is contained in the word $\phi$.

###### Proof.

Assume that some $A_{\\_}i$ in $F$ is ${=}\mathcal{C}_{\\_}{\chi}$ without a
licensor. Then reviewing Instruction 5, $F$ has gotten
${=}\mathcal{C}_{\\_}{\chi}$ due to $\phi$ being right free or 2-handed free,
so $\phi$ holds a free NT $N$ with target category $\mathcal{C}_{\\_}{\chi}$.
As $N$ is free, it generates any CFG word of category
$\mathcal{C}_{\\_}{\chi}$, so there is a rule
$N\mapsto\chi\leavevmode\nobreak\ \\#\mathcal{C}_{\\_}{\chi}$.

Assume that some $A_{\\_}i$ in $F$ is ${=}\mathcal{C}_{\\_}{\chi},+t_{\\_}j$.
Then reviewing Instruction 5, $F$ has gotten ${=}\mathcal{C}_{\\_}{\chi}$ due
to $\phi$ being left restricted, so $\phi$ holds a NT $N$ with target category
$\mathcal{C}_{\\_}{\chi}$ that is restricted with the licensor $+t_{\\_}j$.
Since $N$ is restricted it can only generate some of the CFG words of category
$\mathcal{C}_{\\_}{\chi}$. In the MG the word items of those CFG words are
given a licensee $-t_{\\_}j$ in Instruction 6. $\chi$’s MG item $X$ has
category $\mathcal{C}_{\\_}{\chi}$ and a licensor $+t_{\\_}j$, so it is one of
those that can be generated by $N$, so there is a rule
$N\mapsto\chi\leavevmode\nobreak\ \\#\mathcal{C}_{\\_}{\chi}$. ∎

Now we can interpret the impact of category-recursions in $I$ on $G$.

######  Lemma 5 (Category-Recursions in MGs).

Let $I$ be category-recursion free and let $a$ be an item in $G$ (derived or
lexical) and $b$ an item derived from $a$, such that
$\mathcal{C}(a)=\mathcal{C}(b)$ and $b$ is part of a legal derivation tree.
Then $b$ is an adapted derivation of $a$.

######  Note.

The consequence in Lemma 5 can be interpretted as:

  * 1.

Item $a$ has a self-triggered derivation $\hat{a}$, so that $\hat{a}$ and $b$
have the same exponent. Or

  * 2.

During the derivation from $a$ to $b$, the category has remained the same all
the time.

###### Proof.

Each self-triggered derivation of $a$ is an adapted derivation of $a$.
Therefore let $b$ be an externally triggered derivation of $a$.

Let $\hat{a}$ be the self-triggered derivation of $a$ without selectors or
licensors, so that $b$ is a derivation of $\hat{a}$.

Let $\overline{a}$ be the head word of $\hat{a}$. Then $\overline{a}$ is also
the head word of $a$. Note that $\hat{a}$, $a$ and $\overline{a}$ have the
same category.

We have

$\displaystyle b=m_{\\_}n^{[q_{\\_}n]}\circ\ldots\circ
m_{\\_}1^{[q_{\\_}1]}(\hat{a})$

with merger items $m_{\\_}1,\ldots,m_{\\_}n$ and co-mergees $q_{\\_}i$. We
need to show that all $m_{\\_}i$ are adapter items.

By Lemma 2, each $m_{\\_}i$ is either an adapter or (a self-triggered
derivation of) a lexical word item.

Rename the $m_{\\_}1,\ldots,m_{\\_}n$ and the $q_{\\_}i$ so that

$\displaystyle b=d_{\\_}{p,k(p)}\circ\ldots\circ d_{\\_}{p,1}\circ$
$\displaystyle w_{\\_}p^{[q_{\\_}p]}\circ d_{\\_}{p-1,k(p-1)}\circ\ldots$
$\displaystyle\ldots$ $\displaystyle\ldots\circ d_{\\_}{2,1}\circ$
$\displaystyle w_{\\_}2^{[q_{\\_}2]}\circ d_{\\_}{1,k(1)}\circ\ldots$
$\displaystyle\ldots\circ d_{\\_}{1,1}\circ$ $\displaystyle
w_{\\_}1^{[q_{\\_}1]}\circ d_{\\_}{0,k(0)}\circ\ldots\circ
d_{\\_}{0,1}(\hat{a})$

where for each $i$ the $w_{\\_}i$ is a self-triggered derivations of a word
item $\overline{w_{\\_}i}$, $q_{\\_}i$ is $w_{\\_}i$’s potential co-mergee and
the $d_{\\_}{i,j}$ are the $k(i)$ adapter items used between
$w_{\\_}i^{[q_{\\_}i]}$ and $w_{\\_}{i+1}^{[q_{\\_}{i+1}]}$.

Set $w_{\\_}0=\hat{a}$ and $\overline{w_{\\_}0}=\overline{a}$ and

$\displaystyle r_{\\_}i=d_{\\_}{i,k(i)}\circ\ldots\circ
w_{\\_}i^{[r_{\\_}i]}\circ\ldots\circ d_{\\_}{0,1}(\hat{a})$

for $i=0,\ldots,p$. Then $b=r_{\\_}p$ and for $i=0,...,p-1$: $r_{\\_}i$ is a
mergee that the merger $w_{\\_}{i+1}$ merges with in the construction of $b$.

Note that for $i=1,\ldots,p$,

  * 1.

$w_{\\_}i$ is a self-triggered derivation of $\overline{w_{\\_}i}$, so
$\overline{w_{\\_}i}$ has all selector-licensor-blocks that $w_{\\_}i$ has,

  * 2.

since $r_{\\_}{i-1}$ is merged by $w_{\\_}i$, by Statement 2 of Theorem 3 the
foremost selector-licensor block of $w_{\\_}i$ corresponds to the category
(and foremost licensee) of $r_{\\_}{i-1}$ and

  * 3.

$r_{\\_}{i-1}$ is an adapted derivation of $\overline{w_{\\_}{i-1}}$, so by
Lemma 1 $\overline{w_{\\_}{i-1}}$ has the category and all the licensees that
$r_{\\_}{i-1}$ has.

Hence, one selector-licensor-block of $\overline{w_{\\_}i}$ corresponds to the
category (and a licensee) of $\overline{w_{\\_}{i-1}}$, so by Lemma 4, the CFG
word of $\overline{w_{\\_}i}$ contains a NT that generates the CFG word of
$\overline{w_{\\_}{i-1}}$ for $i=1,\ldots,p$.

Now remember that

  * 1.

$b$ is $r_{\\_}p$, which is an adapted derivation of $\overline{w_{\\_}p}$, so
$\mathcal{C}(b)=\mathcal{C}(\overline{w_{\\_}p})$,

  * 2.

$a$ has the same category as $\overline{a}$, and since
$\overline{a}=\overline{w_{\\_}0}$, we have
$\mathcal{C}(a)=\mathcal{C}(\overline{w_{\\_}0})$ and

  * 3.

$\mathcal{C}(a)=\mathcal{C}(b)$, so we see that
$\mathcal{C}(\overline{w_{\\_}0})=\mathcal{C}(a)=\mathcal{C}(b)=\mathcal{C}(\overline{w_{\\_}p})$,
and the CFG items of $\overline{w_{\\_}0},\ldots,\overline{w_{\\_}p}$ would
form a category-recursion in $I$, if $p>0$.

Since by assumption $I$ has no category-recursions, we know that $p=0$, so all
mergers $m_{\\_}1,\ldots,m_{\\_}n$ are adapter items. ∎

Now we have all tools to prove Statement 3 of Theorem 3.

###### Proof.

We showed that Statement 2 is true because every licensor needs a
corresponding licensee to merge with. Now we show that - if $I$ is category-
recursion free and $\mathcal{C}\neq\mathcal{C}^{\prime}$ \- there cannot be
more licensees than licensors.

If $m^{\prime}>l(1)$, then after the merge and the moves triggered by the
$+a_{\\_}{1,1},\ldots,+a_{\\_}{1,l(1)}$, we would have an item $g=f(x)$ of
category $\mathcal{C}_{\\_}f$ with at least one licensee
$-t^{\prime}_{\\_}{m^{\prime}}$, which from now we call $-t$. In order for
this item to become a legal expression, $-t$ eventually needs to be triggered
by some $+t$.

We show that this is no longer possible.

First we ask, in which case $x$ holds $-t$. If $x$ is lexical, it has to be a
word item. Otherwise, as an adapter $x$ would hold a selector, so by Statement
1 of Theorem 3 item $x$ could not be merged by $f$. If $x$ is derived, then by
Lemma 3 it is an adapted derivation of a word item $\overline{x}$. By Lemma 1,
$\overline{x}$ then also holds $-t$. Summarized, $x$ is an adapted derivation
of some word $\overline{x}$ of category $\mathcal{C}_{\\_}x$ that holds $-t$.
The items $x$ and $\overline{x}$ may be equal.

Following Instruction 6, the purpose of giving $\overline{x}$ a licensee $-t$
is to allow $\overline{x}$ to be merged by some word item, that represents a
CFG word containing a restricted NT for the (main) target category
$\mathcal{C}_{\\_}x$. Only items of the main target category
$\mathcal{C}_{\\_}x$ can hold $-t$.

Following Instructions 5-6, a corresponding $+t$ for $-t$ can then only be
found behind a selector ${=}\mathcal{C}_{\\_}x$, let it be in a word or an
adapter.

Recall that $g=f(x)$ and
$\mathcal{C}(g)=\mathcal{C}_{\\_}f\neq\mathcal{C}_{\\_}x$ and $f$ holds $-t$.
In order for $g$ to get its $-t$ triggered, it needs a derivation $h$ of
category $\mathcal{C}_{\\_}x$ that could then be merged by a word or adapter
with a selector-licensor block ${=}\mathcal{C}_{\\_}x,+t$. Then $h$ is a
derivation of $\overline{x}$ with $\mathcal{C}(h)=\mathcal{C}(\overline{x})$,
so by Lemma 5, it is an adapted derivation. This means that the category
cannot have deviated from $\mathcal{C}(\overline{x})$ at any point in the
derivation between $\overline{x}$ and $h$. However, $f$ is an intermediate
derivation of category
$\mathcal{C}_{\\_}f\neq\mathcal{C}_{\\_}x=\mathcal{C}(\overline{x})$.

Hence, such a derivation $h$ cannot exist and $-t^{\prime}_{\\_}{m^{\prime}}$
can no longer be removed after $x$ is merged by $f$, so a legal expression can
no longer be formed. ∎

###  A.2 Exactness

We have shown that $G$ generates everything that $I$ does.

Now we use the auxiliary results - mainly Theorem 3 \- to show that $G$
generates nothing beyond what $I$ does, if $I$ has no category-recursions.

######  Theorem 4.

If $I$ is category-hierarchical, then each legal expression of $G$ is a legal
expression of $I$.

###### Proof.

Consider a legal derivation tree in $G$. We show that in any path from a leaf
to the root, any operation that affects the exponent is analogous to one the
operations described in Subsection 3.1 or Figure 3.

Any path of legal derivation tree in $G$ includes at the bottom an initial
merge of a lexical mergee item, i.e. a lexical item without selectors and
licensors. Let $x$ be such an item. Then each (legal) derivation of $x$ can be
written

$\displaystyle m_{\\_}s^{[q_{\\_}s]}\circ\ldots\circ m_{\\_}1^{[q_{\\_}1]}(x)$
(9)

where the $m_{\\_}i$ are the - lexical or derived - mergers in chronological
order and the $q_{\\_}i$ are the co-mergees for those $m_{\\_}i$ that have 2
selectors.

We show that whenever an intermediate operation from
$m_{\\_}i^{[q_{\\_}i]}\circ\ldots\circ m_{\\_}1^{[q_{\\_}1]}(x)$ to
$m_{\\_}{i+1}^{[q_{\\_}{i+1}]}\circ\ldots\circ m_{\\_}1^{[q_{\\_}1]}(x)$
affects the exponent, it behaves like in Section 3.1 or Figure 3.

Since the mergee $x$ has no selectors, it has the shape $\langle
E::\mathcal{C},-t_{\\_}1,\ldots,-t_{\\_}l\rangle$, so by Observation 2, it has
to be a word.

  * For the sake of generalization, we already note that it would not make a difference if it had either of the shapes

$\displaystyle\langle E::\mathcal{C},-t_{\\_}1,\ldots,-t_{\\_}l\rangle$ (10)
$\displaystyle\langle E:\mathcal{C},-t_{\\_}1,\ldots,-t_{\\_}l\rangle$
$\displaystyle\langle\epsilon:\mathcal{C}\rangle,\langle
E:-t_{\\_}1,\ldots,-t_{\\_}l\rangle$

They produce the exact same derivations once they get merged by some $\langle
E^{\prime}\cdot{=}\mathcal{C},\ldots\rangle$. In the latter case, the merge
would be final merge-1 instead of a non-final merge-3, but in either case the
merge would produce $\langle E^{\prime}:\ldots\rangle,\langle
E:-t_{\\_}1,\ldots,-t_{\\_}l\rangle$.

The merger, by Lemma 3, can be an adapter or a (self-triggered derivation of
a) word item.
If the merger is an adapter:

  * By Theorem 3.2 it is the remove adapter or the select adapter of the first licensee $-t_{\\_}1$. If it is

    * the999There is a highly unlikely possibility that a select adapter with $n^{\prime}<n$ fitting licensors exists and could be applied. This situation would imply a very bad sorting of licensees, albeit possibly unavoidable. In this case, a merge-3 and $m$ move-2s would produce $\langle\epsilon:\mathcal{C},-t_{\\_}1\rangle,\langle E:-t_{\\_}{n^{\prime}+1},\ldots,-t_{\\_}n\rangle$. This item would also behave like the items in Equation 10 select adapter, one merge-3, $n-1$ times move-2 and a move-1 produce the shape $\langle E:\mathcal{C},-t_{\\_}1\rangle$. As this is a special case of one of the mergee shapes in Equation 10, the consecutive derivations can be described the same again.

    * the remove adapter and

      * $l=1$, then a merge-3 and a move-1 produce $\langle E:\mathcal{C}\rangle$

      * $l>1$, then a merge-3 and a move-2 produce $\langle\epsilon:\mathcal{C}\rangle,\langle E:-t_{\\_}2,\ldots,-t_{\\_}l\rangle$.

In either case the product would be a special case of one of the mergee shapes
in Equation 10, so the consecutive derivations can be described the same
again.

If the merger is (a self-derivation of) a word item, then the merger has a
different category as the mergee, otherwise there would be a category
recursion in the CFG. So, by Theorem 3.3, we have:

The merger can only be (a self-derivation of) a word if the first selector-
licensor block in its feature list exactly matches the mergee’s feature list.
More precisely, then the number $l$ of the merger’s licensors is always $0$ or
$1$, depending on whether the word’s NT is free or restricted. So, the mergee
can only be merged by a (a self-derivation of) a word if it is $\langle
E\cdot\mathcal{C}\rangle$ or $\langle E\cdot\mathcal{C},-t\rangle$ or
$\langle\epsilon:\mathcal{C}\rangle,\langle E:-t\rangle$.
With the present results we can completely describe101010Application of a
select shaper with less than $n$ licensors not included in the graph. Then
$\langle\epsilon:\mathcal{C},-t_{\\_}1\rangle,\langle
E:-t_{\\_}{n^{\prime}+1},\ldots,-t_{\\_}n\rangle$ would be produced, a
construction that would re-enter the graph latest when it has only one
licensor left. in Figure 9 what a lexical item - or more generally: an item
without selectors and licensors - could derive until it gets merged by another
(self-derivation of a) word item.

Figure 9: The possible legal paths of derivation from an item of shape
$\langle E\cdot\mathcal{C},-t_{\\_}1,\dots,-t_{\\_}n\rangle$ or
$\langle\epsilon:\mathcal{C}\rangle,\langle
E:-t_{\\_}1,\dots,-t_{\\_}n\rangle$. Each arrow represents a merge- and
potential consecutive move-operation(s) performed on the item that the arrow
goes out of. The markers remove/select indicate that the arrow’s merge- and
move-operation(s) are triggered by a remove/select adapter.

Next, we take a deeper look into the possible shapes of word mergers, i.e.
what does a $m_{\\_}i^{[q_{\\_}i]}$ do in the derivation path of Equation 9,
if $m_{\\_}i$ is (a self-derivation of) a word item. We show that

  * 1.

the operations triggered by $m_{\\_}i$ always run analogously as in the
scenarios described in Subsection 3.1 or Figure 3.

  * 2.

the resulting product $m_{\\_}i^{[q_{\\_}i]}\circ\ldots\circ
m_{\\_}1^{[q_{\\_}1]}(x)$ always has the shape
$\langle\ldots\cdot\mathcal{C}_{\\_}m,\ldots\rangle$.

Recall that (self-triggered derivations of) word items can only merge mergees
of the shapes $\langle E\cdot\mathcal{C}\rangle$ or $\langle
E\cdot\mathcal{C},-t\rangle$ or $\langle\epsilon:\mathcal{C}\rangle,\langle
E:-t\rangle$. Consider a merger $m$ of category $\mathcal{C}_{\\_}m$. It must
hold ${=}\mathcal{C}$ or ${=}\mathcal{C},+t$ as its foremost selector-licensor
block. $m$’s lexical head word $\overline{m}$ must also hold this block.

If the selector ${=}\mathcal{C}$ that triggers the merge with $x$ is
$\overline{m}$’s foremost feature, then - assuming $m$ would be a non-trivial
derivation of $\overline{m}$ \- $m$ would not hold ${=}\mathcal{C}$, because
this selector would have been triggered before. Then $m=\overline{m}$, so $m$
is a lexical word item. By Instruction 5 (or Observation 2) it is either
right-free, 2-handed-free or left-restricted, so $m$ has the shape $\langle
M::{=}\mathcal{C},\mathcal{C}_{\\_}m,\ldots\rangle$ or $\langle
M::{=}\mathcal{C},{=}\mathcal{C}_{\\_}2,\mathcal{C}_{\\_}m,\ldots\rangle$ or
$\langle M::{=}\mathcal{C},+t,\mathcal{C}_{\\_}m,\ldots\rangle$ respectively.

If ${=}\mathcal{C}$ is not $\overline{m}$’s foremost feature, then by
Observation 2 $\overline{m}$ must have 2 selector-licensor blocks and
${=}\mathcal{C}$ must be the second. Then
$\overline{m}=\langle\overline{M}::{=}\mathcal{C}_{\\_}1,{=}\mathcal{C},\mathcal{C}_{\\_}m,\ldots\rangle$
and $m=\langle M:{=}\mathcal{C},\mathcal{C}_{\\_}m,\ldots\rangle$.

The remaining possibilities of (merger,mergee)-pairs - when the merger is a
(self-triggered derivation of a) word item - is listed in Table 4 and each of
the pairs lead to one the scenarios described in either Subsection 3.1 or
Figure 3.

Merger | Mergee |  Operation(s) | Resulting item
---|---|---|---
$\langle M::{=}\mathcal{C},\mathcal{C}_{\\_}m,\ldots\rangle$ | $\langle E\cdot\mathcal{C}\rangle$ |  merge-1, see Eq. 2 | $\langle ME:\mathcal{C}_{\\_}m,\ldots\rangle$
$\langle M::{=}\mathcal{C},{=}\mathcal{C}_{\\_}2,\mathcal{C}_{\\_}m,\ldots\rangle$ | $\langle E\cdot\mathcal{C}\rangle$ |  merge-1, see Eq. 3 | $\langle ME:{=}\mathcal{C}_{\\_}2,\mathcal{C}_{\\_}m,\ldots\rangle$
$\langle M:{=}\mathcal{C},\mathcal{C}_{\\_}m,\ldots\rangle$ | $\langle E\cdot\mathcal{C}\rangle$ |  merge-2, see Eq. 4 | $\langle EM:\mathcal{C}_{\\_}m,\ldots\rangle$
$\langle M::{=}\mathcal{C},+t,\mathcal{C}_{\\_}m,\ldots\rangle$ | $\langle E\cdot\mathcal{C},-t\rangle$ |  merge-3 +move-1, see Eq. 5 \+ 6 | $\langle EM:\mathcal{C}_{\\_}m,\ldots\rangle$
$\langle M::{=}\mathcal{C},+t,\mathcal{C}_{\\_}m,\ldots\rangle$ |  $\langle\epsilon:\mathcal{C}\rangle,\langle E:-t\rangle$) |  merge-1 +move-1, see Figure 3 | $\langle EM:\mathcal{C}_{\\_}m,\ldots\rangle$
Table 4: All possible scenarios, how (a self-triggered derivation of) a word
can merge in $G$. As can be seen, each scenario equals one of the scenarios
described in Subsection 3.1 or Figure 3

Unless the merger $m_{\\_}i$ is $\langle
M::{=}\mathcal{C},{=}\mathcal{C}_{\\_}2,\mathcal{C}_{\\_}m,\ldots\rangle$, it
only has 1 selector and the outcome of merging a mergee $\hat{x}$ is always

$\displaystyle
m_{\\_}i^{[q_{\\_}i]}(\hat{x})=m_{\\_}i(\hat{x})=\langle\ldots:\mathcal{C}_{\\_}m,\ldots\rangle.$

If the merger $m_{\\_}i$ is $\langle
M::{=}\mathcal{C},{=}\mathcal{C}_{\\_}2,\mathcal{C}_{\\_}m,\ldots\rangle$, it
is the only case where it has 2 selectors and thus has a co-mergee $q_{\\_}i$.
The co-mergee $q_{\\_}i$ must be merged by $m_{\\_}i(\hat{x})=\langle
ME:{=}\mathcal{C}_{\\_}2,\mathcal{C}_{\\_}m,\ldots\rangle$. So by Theorem 3
$q_{\\_}i$ must have the shape $\langle Q\cdot\mathcal{C}_{\\_}2\rangle$. A
merge-2 would be triggered, which would produce

$\displaystyle
m_{\\_}i^{[q_{\\_}i]}(\hat{x})=m_{\\_}i(\hat{x})(q_{\\_}i)=\langle
QME:\mathcal{C}_{\\_}m,\ldots\rangle.$

In either case $m_{\\_}i^{[q_{\\_}i]}(\hat{x})$ has the shape
$\langle\ldots:\mathcal{C}_{\\_}m,\ldots\rangle$. Hence, all further
derivations can again be fully described by the graph in Figure 9, until a
derivation has reached one of the mergee shapes of Table 4. Then the
derivation can again be merged by (a self-derivation of) a word item, but
again the following derivation would not deviate from the scenarios described
in Subsection 3.1 or Figure 3.

Hence, there is no way for a derivation in a legal tree to escape the graph in
Figure 9 and Table 4, so all merges and moves triggered by word items happen
just as described in Subsection 3.1. So, in any leaf-to-root path of any
derivation tree in $G$, each operation that affects the exponent is analogous
to some derivation in $I$, where some NT is replaced by some word. No
arrangement errors can occur, so the expression of the legal derivation tree
in $G$ is also generatable by the CFG $I$.

∎