text:
\documentclass[output=paper]{langsci/langscibook}
\ChapterDOI{10.5281/zenodo.3598560}

\usepackage{csquotes}

\title{What can we learn from novel compounds?}

\author{Gary Libben\affiliation{Brock University}}

\abstract{This chapter focuses on the question of how novel compounds are processed. To address this question, morphologically unambiguous compounds such as \textit{shotden} are contrasted with morphologically ambiguous compounds such as \textit{clampeel} (which can have the constituent structure \textit{clam-peel} or \textit{clamp-eel}). I discuss how these strings can be seen as \textit{lexical superstates} and present a proposal for how they are parsed. An experiment using progressive demasking and typing is reported. Typing results show evidence of activation of both versions of ambiguous compounds,  supporting the view that all lexical substrings in a multiword expression that can be activated, will be activated.  I claim that this type of activation is fundamental to the understanding of morphological effects in both the visual recognition and production of English words. Specifically, it enables the creation of \textit{morphological superstates}, the flexible morphological structures that \citet{Libben2017} claims characterize cognitive processing in lexical comprehension and production.}

\begin{document}

\maketitle

\section{Background}\label{sec:libben:1}\largerpage
\subsection{An illustrative example}\label{sec:libben:1.1}
It might be worthwhile to begin with a non-laboratory example of the type of lexical processing that needs to be accounted for.   The example begins with a furniture store in Vienna, named \textit{FantasTeak}.  To be sure, the highlighting of \textit{Teak} in the name \textit{FantasTeak} is extremely important, considering that it is a furniture store. But does the medial \textit{T} in \textit{FantasTeak} need to be capitalized?  Removing it reveals that indeed it does!  Without the medial capitalized \textit{T}, \textit{Fantasteak} seems to generate the activation of the subword \textit{steak}. Indeed, \textit{Fantasteak} is the name of a steak restaurant that opened in Campbelltown, Australia on Mother’s Day 2019.

\textit{Fantasteak} is a highly complex and ambiguous multiword expression. It has multiple interpretations that trade on the activation of subwords such as \textit{steak}, \textit{teak} and the drink \textit{Fanta}, as well as orthographic and phonological similarity to the whole word \textit{fantastic}.  This suggests great voracity in the activation of subwords. Yet, not all subwords of the string appear to be activated. The string \textit{Fantasteak} also contains the substrings \textit{fan,} \textit{ant}, \textit{taste}, and \textit{tea}.  Although these are, on average, higher in frequency than either \textit{steak} or \textit{teak}, they seem to be relatively inaccessible within the string. The goal of this chapter is to explain why.  Why is it that some substrings of ambiguous and unambiguous compounds are activated, why other substrings are not activated, and what can this tell us about the fundamental nature of cognitive operations involved in lexical processing?

Understanding how novel morphologically complex words are parsed is key to understanding how people expand their vocabularies and indeed how morphological productivity enables new words to enter the language.  There seems to be good reason to believe that this morphological parsing and the activation of lexical substrings that it entails is not as simple and rigid as was previously thought.  As \citet{Libben2015} notes, this progression can be seen by tracing developments in the field starting with \citet{TaftForster1975}. They contrasted stimulus pairs such as \textit{replicate} and \textit{repertoire}, arguing that a word such as \textit{replicate} is perceived by native speakers of English as prefixed, whereas a word such as \textit{repertoire} is not prefixed. They predicted that, as a result, the novel prefixed form \textit{deplicat}e (containing the prefix \textit{de}{}- and an existing morphological substring \textit{-plicate}) will appear to be more word-like than the novel prefixed form \textit{depertoire} (which does not contain an existing morphological substring). Indeed, \citet{TaftForster1975} reported elevated rejection latencies for strings such as \textit{deplicate} in a lexical decision task.

The \citet{TaftForster1975} contribution was truly seminal. It was the first to invoke a process of lexical parsing and the activation of substrings to predict patterns of lexical processing across word types.  Even more importantly, from my perspective, it linked the morphological structure of a word to the manner in which it is processed by native speakers. This implies that a word such as \textit{replicate} has a prefix-stem structure because (and, perhaps, only because) people ``strip off'' the prefix during visual word processing.\largerpage

In my view, considering the morphological structure of a word in terms of what people do when they recognize or produce it, has very substantial advantages. It enables us to link the processing of novel words with the processing of existing words and it requires that we be explicit about the parsing processes that could enable the interpretation of prefixed, suffixed and compound words. Perhaps most importantly, it leads us to the view that words are actions, not things, and that morphology is what people do, not what people have.

\subsection{Questions of lexical constituent structure}\label{sec:libben:1.2}

This leads us directly to the question: So, what is the actual morphological structure of \textit{Fantasteak}? Is it \textit{Fanta-steak}, or \textit{Fantas-steak}, or \textit{Fantas-teak}?  My answer to this question would be that the actual structure of \textit{Fantasteak} is any one of those that a language user happens to need.  Because \textit{Fantasteak} is a novel creation, it does not ``have'' any morphological structure when people first see it. Rather, it is their actions that give the word morphological structure. And, as we can see, more than one set of actions are possible. Thus, I suggest that a word such as \textit{Fantasteak} does not have a single fixed morphological structure. Rather, the characteristics of morphological processing in English create a situation in which there is both \textit{steak} and \textit{teak} in \textit{Fantasteak}.

The formation of questions like ``Is there \textit{teak} in \textit{Fantasteak}?'' above has been at the heart of a line of psycholinguistic inquiry that has sought to isolate the conditions under which lexical substrings are and are not activated during processing. These include the \textit{hat} in \textit{that} \citep{BowersHanley2005},  the \textit{broth} in \textit{brothel} \citep{RastleNew2004}, and the \textit{corn} in \textit{corner} \citep{LongtinHalle2003,MorrisGrainger2008,LehtonenMPoeppel2011,LavricRastle2012}. For the most part, this literature has focused more on the drivers of morphological decomposition and less on the details of morphological parsing.  A key question, for example, has been whether morphological decomposition of existing words can be driven by form-based factors \citep{BeyersmannGrainger2016} or whether true morphological decomposition depends on semantic features of the word and of processing \citep{JärvikiviPyykkönen2011,RuecklAicher2008,MorrisHolcomb2007}.

To be sure, understanding how morphological processing is influenced by formal factors and how it is influenced by the lexical semantic characteristics (e.g., the semantic transparency of the whole word) is extremely important in the development of our understanding of online lexical processing.  In this context, novel forms such as \textit{Fantasteak} may have a special role to play. The alternate morphological parses that are available for this novel string may shed light on how putative constituents are identified and the conditions under which substrings such as \textit{fantas-} can be treated by users of the language as word substrings (supported, presumably by the semantic similarity among words such as \textit{fantasia}, \textit{fantastic}, and \textit{fantasy}).

\subsection{Ambiguous novel compounds and lexical superstates}\label{sec:libben:1.3}\largerpage

\citet{LibbenDerwingdeAlmeida1999} employed a type of novel morphological construction that they claimed is particularly revealing of the dynamics of morphological processing in general and morphological parsing in particular.  They focused on ambiguous novel compounds. These are novel compounds such as \textit{clampeel}, which can be parsed as either \textit{clam-peel} or \textit{clamp-eel}.  They found that there was no general tendency for native speakers of English to adopt either a first parse (e.g., \textit{clam-peel}) or last parse (e.g., \textit{clamp-eel}) approach. Moreover, they found that ambiguous novel compounds such as \textit{clampeel} show activation of all their potential constituents (e.g., \textit{clam}, \textit{clamp}, \textit{peel}, and \textit{eel}). In other words the answer to the question “Is there a (\textit{clam}, or \textit{clamp} or \textit{peel} or \textit{eel}) in \textit{clampeel}?” would simply be “Yes”.

Findings such as these call into question the assumption that a given word will have a univocal morphological structure.  \citet{Libbeninpress} argues that this indeterminacy applies to the morphology of lexical structures in general.  Under this view, a string such as \textit{clampeel} can be described as being in a lexical superstate – a cognitive state that is best described by the opportunities for interpretation that it enables.  \citet{Libbeninpress} claims that this applies to morphological structures in general. Thus, an existing compound such as \textit{keyboard} has, as a superstate, the whole word representation \textit{keyboard} as well as the decomposed representation \textit{key-board}. Analogously, an existing suffixed word such as \textit{formality} can be best described as having the lexical superstate representation shown in \figref{fig:libben:1}. In this figure, the string has a whole word representation as well as multiple decomposition possibilities. Which one of these is actually implemented in an act of lexical processing will depend on the specifics of the processing task, the individual language user, and the situation in which they are found.

\begin{figure}
    \begin{tikzpicture}[rotate=45,transform shape]
    \draw [draw,fill=lsLightGray,even odd rule,name=nucleus]  (0,0) circle (3mm)  (0,0) circle (.5mm);
    \coordinate (nucleus) at (0,0);
    \node [right=3mm of nucleus.east] {[formal][ity]};
    \node [left=3mm of nucleus.west,anchor=east] {[form][al][ity]};
    \node [below=3mm of nucleus.south,rotate=-90,anchor=west] {[formality]};
    \node [above=3mm of nucleus.north,rotate=-90,anchor=east] {[form][ality]};
    \end{tikzpicture}
\caption{\label{fig:libben:1}An example lexical superstate representation. The word \textit{formality} can be undecomposed, fully decomposed, have a suffix string (\textit{-ality}) or a complex stem (\textit{formal}).}
\end{figure}

Lexical superstate representations can also be effective in capturing the structural ambiguity of a word such as \textit{unlockable} in \figref{fig:libben:2}, which can be interpreted as `not lockable' (\textit{un-lockable}) or `able to be unlocked' (\textit{unlock-able}). Lexical superstate representation can also be applied to novel ambiguous strings such as \textit{Fantasteak} and \textit{clampeel}. These are shown in \figref{fig:libben:3}. As can be seen in this figure, in many ways, the novel string \textit{Fantasteak} is the more complex of the two. In order to capture the key features of \textit{Fantasteak}, it is necessary to indicate that it is linked in an unspecified manner (represented by a dotted line) to the existing word \textit{fantastic} (and \textit{fantasy}, etc.). This acknowledges the likely source of both novel interpretations. It also leads to the requirement to accept a fuzzy parse such as \textit{Fantas-steak}, in which the medial \textit{s} is repeated.

\begin{figure}
    \begin{tikzpicture}[rotate=45,transform shape]
    \draw [draw,fill=lsLightGray,even odd rule,name=nucleus]  (0,0) circle (3mm)  (0,0) circle (.5mm);
    \coordinate (nucleus) at (0,0);
    \node [right=3mm of nucleus.east] {[unlock][able]};
    \node [left=3mm of nucleus.west,anchor=east] {[un][lock][able]};
    \node [below=3mm of nucleus.south,rotate=-90,anchor=west] {[unlockable]};
    \node [above=3mm of nucleus.north,rotate=-90,anchor=east] {[un][lockable]};
    \end{tikzpicture}
\caption{\label{fig:libben:2}Superstate representations for the structurally ambiguous word \textit{unlockable}.}
\end{figure}

\begin{figure}
    \begin{minipage}{.5\linewidth}\centering%
    \begin{tikzpicture}
    \draw [draw,fill=lsLightGray,even odd rule,name=nucleus]  (0,0) circle (3mm)  (0,0) circle (.5mm);
    \coordinate (nucleus) at (0,0);
    \node [above right= .5\baselineskip and 3mm of nucleus.north east,anchor=west,rotate=45] {[Fanta][steak]};
    \node [above left= .5\baselineskip and 3mm of nucleus.north west,anchor=east,rotate=-45] {[Fantas][teak]};
    \node [below=3mm of nucleus.south,rotate=-90,anchor=west] {[Fantas][steak]};
    \node (fantastic) [above=3\baselineskip of nucleus.north] {\itshape fantastic};
    \draw[dotted,thick] (fantastic) -- (nucleus.north) +(0,-3mm);
    \end{tikzpicture}\end{minipage}\begin{minipage}{.5\linewidth}\centering%
    \begin{tikzpicture}
    \draw [draw,fill=lsLightGray,even odd rule,name=nucleus]  (0,0) circle (3mm)  (0,0) circle (.5mm);
    \coordinate (nucleus) at (0,0);
    \node [above right= .5\baselineskip and 3mm of nucleus.north east,anchor=west,rotate=45] {[clamp][eel]};
    \node [above left= .5\baselineskip and 3mm of nucleus.north west,anchor=east,rotate=-45] {[clam][peel]};
    \node [below=3mm of nucleus.south,rotate=-90,anchor=west] {[clamp][peel]};
    \end{tikzpicture}\end{minipage}
\caption{\label{fig:libben:3}Superstate representations for novel compounds. \textit{Fantasteak} is shown on the left.  The dotted line indicates an association to the existing word \textit{fantastic}.  \textit{Clampeel} is shown on the right.}
\end{figure}

The representation\largerpage[-1] of \textit{clampeel} in \figref{fig:libben:3} has a structure that has features in common with that of \textit{Fantasteak}.  It shows the possibility of a fuzzy parse in which the medial letter is repeated (in this case the medial \textit{p} to enable the interpretation \textit{clamp-peel}).  Overall, however, \textit{clampeel} is quite a bit more controlled and straightforward than \textit{Fantasteak}. First, we can be relatively confident that \textit{clam} and \textit{clamp} are existing lexical strings of English. This is not necessarily the case for \textit{Fanta} (the name of a drink produced by Coca Cola) or \textit{fantas} (which may or may not be a unit of recognition for speakers of English). Second, the interpretation cannot draw on the interpretation of a set of existing words (as is the case for Fantasteak).  Ambiguous novel compounds such as \textit{clampeel}, therefore, may constitute the stimulus type that would enable us to investigate the \textit{Fantasteak} phenomenon under relatively controlled conditions. In addition, ambiguous novel compounds provide a testing ground for the investigation of how readers of English are able to make use of the advantages enabled by compound word productivity in the context of a writing system in which compound words are often written as single unspaced strings.

\subsection{Fuzzy Forward Lexical Activation generates lexical superstate representations}\label{sec:libben:1.4}

Why are English language users likely to find \textit{clam} and \textit{clamp} in \textit{clampeel}? And why are they less likely to find the substrings \textit{lamp}, \textit{am}, and \textit{amp}? \citet{TaftForster1976} claimed that, fundamentally, morphological processing was a left-to-right process in the reading of English.

There is a good deal of evidence that supports the assumption that morphological activation is achieved through beginning-to-end processing. However, it is less clear that morphemes themselves have discreet representations in the mental lexicon (e.g., \citealt{BaayenSmolka2019,RamscarEtAl2018}).  In addition, phenomena such as the shared \textit{s} in \textit{Fantas-steak} suggest that an approach to parsing that requires that reference be made to fixed individual morphemes and individual letters in a word is likely to be problematic.  A more useful approach to capturing how individuals identify constituent substrings of English words can be to simply posit a heuristic of Fuzzy Forward Lexical Activation. In this approach, processing always takes place from beginning to end. Initial letters of a word are scanned until a familiar initial lexical substring is encountered. If it is, a final substring is computed from that position onward. If that final substring is also familiar, it is interpreted and the process continues.  Thus, the strings \textit{formality}, \textit{clampeel}, \textit{Fantasteak}, and \textit{unlockable} would be processed in the manner shown in \tabref{tab:libben:1}.

\begin{table}
\caption{\label{tab:libben:1}Fuzzy Forward Lexical Activation for stimuli such as \textit{formality,} \textit{clampeel,} \textit{Fantsteak}, and \textit{unlockable}.}
\begin{tabular}{c*{4}{>{\itshape}l}}
\lsptoprule

{Parse}  & \multicolumn{4}{c}{{Stimuli}}\\\cmidrule(lr){2-5}
& \textit{formality} & \textit{clampeel} & \textit{Fantastic} & \textit{unlockable}\\\midrule
 1. & form-ality & clam-peel & Fanta-steak & un-lockable\\
 2. & formal-ity & clamp-eel & Fantas-teak & unlock-able\\
 3. & formality & (+clamp-peel) & (+Fantas-steak) & unlockable\\
\lspbottomrule
\end{tabular}
\end{table}

This parsing heuristic makes the claim that processing activity will generate patterns that correspond to both readings of a novel ambiguous word such as \textit{clampeel}, as well as an existing structurally ambiguous word such as \textit{unlockable}, simply by parsing them.

In addition, the parsing heuristic will generate both stem-suffix representations for the word \textit{formality}, as well as an affix string representation. It will, however, neither generate the fully decomposed representation \textit{form-al-ity} nor the fully decomposed representation \textit{un-lock-able.} The heuristic therefore makes the empirical claim that English language users do not create such fully decomposed representations either.  They are thus claimed to be potential lexical superstate representations that are not realized because of the dynamics of visual lexical processing in English.

Fuzzy Forward Lexical Activation is likely the simplest possible approach to English visual morphological parsing. Like the signs that one sees on London crosswalks to aid tourists, it says: “Look right →”.  By beginning at the beginning and looking right it ensures that the key initializing activity in morphological processing is the activation of the initial substring of the word. Thus, although this approach to morphological processing differs from the prefix-stripping approach of \citet{TaftForster1975}, it has much the same effect.  The processing of a word such as \textit{unlockable} begins with the recognition of the prefix \textit{un-}.
From there, the parses \textit{un-lockable}, \textit{unlock-able} are created (under the assumption that the substrings \textit{lockable}, \textit{unlock} and \textit{-able} are known to the language user). This feature of checking that substring to the right is known to the language user ensures that the parse \textit{form-ality} is possible under the assumption that a language user maintains a trace of suffix strings such as \textit{-ality} \citep{Derwing2014,LibbenJaremaEtAl2016}.  However, the potential parse \textit{for-mality} would fail at the “look right” stage because the string \textit{-mality} is unlikely to be known to the language user as a representation of English.

Fuzzy Forward Lexical Activation constituted an extremely simple approach to morphological parsing that, I claim, is linked directly to the lexical superstate representations shown in Figures~\ref{fig:libben:1}, \ref{fig:libben:2} and~\ref{fig:libben:3}. Indeed, it creates them.  Its functioning results in morphological processing that is primarily binary. The reason for this is that it must begin at the beginning and it must look toward the end of the word. The functioning of Fuzzy Forward Lexical Activation also results in what might be termed hierarchical morphological structure, so that a word such as \textit{undrinkable} would be parsed as the right-branching structure \textit{un-drinkable,} whereas a word such as \textit{unlockable} will be parsed as both the right-branching structure \textit{un-lockable} and the left-branching structure \textit{unlock-able}.

\subsection{Typing as a window to morphological processing}\label{sec:libben:1.5}

This brings us to the question how the predictions of the lexical superstate hypothesis and the proposed mechanisms of Fuzzy Forward Lexical Activation can be evaluated.  A potentially revealing task is one that specifically targets lexical activation in left-to-right processing.  I suggest that the online typing of words is exactly such a task.  In online typing, a participant is presented with a lexical string and is asked to type it as quickly and as accurately as possible.  For each word typed, it is possible to calculate overall per letter typing times as well as per letter typing times at specific locations in the word \citep{FeldmanEtAl2019,LibbenJaremaEtAl2016,SahelWeingarten2008,WillWeingarten2006}.

If indeed, morphological structure for novel compounds is evident in online typing, we should see elevated response times at the morpheme boundary for unambiguous strings such as \textit{anklecob.} This would correspond to the location at which participants recognize an initial string \textit{ankle} and then would look right to the end of the string, recognizing \textit{cob}. For ambiguous novel compounds such as \textit{clampeel}, however, the location of the putative morpheme boundary should be blurred and both potential parses should become part of the lexical superstate.  We would expect elevated letter typing times at both the locations between \textit{clam} and \textit{peel}, as well as between \textit{clamp} and \textit{eel}.
Our previous research has shown that the typing of morphologically complex words is characterized by elevated typing times at the constituent boundary \citep{LibbenWeber2014,LibbenJaremaEtAl2016}. This difference in typing time may reflect morphological chunking in letter typing, so that a two constituent compound word is typed as a sequence of two motor plans. Each motor plan would correspond to a compound constituent. The prediction regarding typing times for ambiguous novel compounds follows from this observation: If the production of ambiguous novel compounds involves the activation of all potential constituents, then we should expect that four motor plans are in play.  This would result in ``blurring'', i.e., longer and lower latency spikes. Latency increases would be longer because they would be spread over two letter boundaries rather than one and they would be lower because each of those letter boundaries is at once a ``between constituent'' location and a ``within-constituent'' location.

Thinking about constituent boundary effects in terms of motor plans suggests that a number of control variables also need to be tracked.  The reason for this is that one would expect that the speed with which word typing motor plans are created and executed can be influenced by position in the word and by the frequency of particular letter combinations in the language. Moreover, particular attention would need to be paid to letter co-occurrence frequencies at the constituent boundary itself.  These predictions and analytic considerations were tested in the experiment described below.

\section{Method}\label{sec:libben:2}

\subsection{Participants}\label{sec:libben:2.1}

Twenty-four native English speakers between the age of 17 and 26 years participated in the study.  All reported English to be their mother tongue and none had learned a second language before age ten.  All participants had normal or corrected-to-normal vision. They were all university students from a variety of departments of Brock University who received either course credit or \$15 for their participation.

\subsection{Stimuli}\label{sec:libben:2.2}
In total, participants viewed and produced 45 stimuli, all of which were novel  noun-noun English compounds. Fifteen of these were unambiguous novel compounds, thirty were ambiguous novel compounds. The ambiguous novel compound stimuli were created by extracting all nouns from the CELEX database \citep{BaayenGulikers1995} and then identifying which of those also created nouns when their last letter was removed. This created a candidate first constituent pair (e.g. \textit{clam}, \textit{clamp}). Each such pair was then linked to a noun in the CELEX database that began with the last letter of the longer member of the pair (in this case, \textit{p}) and which also created a noun when its first letter is removed (e.g., \textit{peel}, \textit{eel}). This process of selection creates the set of English novel noun-noun compound stimuli such as \textit{clampeel}.  The resulting set of 45 stimuli are shown in \tabref{tab:libben:2}.  These were created so that constituents were comparable in frequency and length. The set of ambiguous novel compounds was subdivided into those in which the grapheme-to-phoneme relations were different in each of the two parses and those for which the grapheme-to-phoneme relations were essentially the same. The difference between these two subgroups can be easily appreciated by reading aloud the stimuli in the middle column of \tabref{tab:libben:2} and reading aloud those in the final column of the table. The ambiguous stimuli with sound change shown in the middle column are those such as \textit{babelarch}. As \textit{babe-larch}, the first constituent is one syllable in length and has the initial vowel /ej/. As \textit{babel-arch}, the first constituent is two syllables in length and has the initial vowel /æ/.  In contrast, \textit{clampeel}, as the first stimulus in the third column of \tabref{tab:libben:2}, has essentially the same phonological realization as \textit{clam-peel} and \textit{clamp-eel} (assuming co-articulation and other effects associated with the morpheme boundary).

\begin{table}
\caption{\label{tab:libben:2}The novel compound stimuli in the progressive demasking and typing tasks.  Unambiguous stimuli (e.g., \textit{anklecob}) have a single morphological parse (e.g., \textit{ankle}\,+\,\textit{cob}). Ambiguous stimuli (e.g., \textit{clampeel,} \textit{babelarch)} have two possible morphological parses. For the ones with sound change, the pronunciation of graphemes depends on the parse (e.g., \textit{babe}\,+\,\textit{larch}, \textit{babel}\,+\,\textit{arch}).  For ambiguous stimuli without sound change, it does not (e.g., \textit{clam}\,+\,\textit{peel}, \textit{clamp}\,+\,\textit{eel}).}
\begin{tabular}{*{3}{>{\itshape}l}}
\lsptoprule
{\normalfont Unambiguous} & \multicolumn{2}{c}{{\normalfont Ambiguous}}\\\cmidrule(lr){2-3}
& {\normalfont with sound change} & {\normalfont without sound change}\\\midrule
anklecob & babelarch & clampeel\\
clubswim & bandanger & crampinch\\
deckswerve & bowlease & damplane\\
fakebread & cardevil & fangape\\
floataxe & cellorange & feedraft\\
friendbotany & dudemission & firmaid\\
kelpfibre & fatemotion & fundrain\\
lyricalp & findrag & rumplight\\
plazafocus & grindream & rungear\\
shotden & gripequality & scarfright\\
spillcarriage & kindrift & sealedge\\
squeakpub & modelore & songlass\\
supplychase & realmink & spamoral\\
watchpanic & sodacorn & teamother\\
whiffpalace & winglint & wardrug\\
\lspbottomrule
\end{tabular}
\end{table}

\section{Apparatus and procedure}\label{sec:libben:2.3}
The procedure employed in the present study was implemented in Psyscope X, running on a MacBook Pro, using an IO Labs button box Voice Key.

We used a combined progressive demasking and typing paradigm as developed by \citet{LibbenEtAl2012} and \citet{LibbenWeber2014}. In this paradigm, participants first see a word being progressively demasked in the center of a computer screen. and must identify it as quickly as possible. After the word is identified (either by saying it aloud or by pressing the return key), the stimulus disappears. The participant is then asked to type it as quickly and as accurately as possible.

All 24 participants identified and typed all 45 stimulus words. Stimuli were presented in a different random order for each participant.  Testing was conducted in a single block of trial and the main experiment was preceded by a practice session of six trails.

Each trial consisted of two components:  a progressive demasking component and a typing component, with an inter-trial interval of two seconds.  Thus, in the first trial of the experiment, a participant would see word being progressively demasked and would identify it. This progressive demasking component would be immediately followed by the typing component. The screen would go blank and the participant would type the word using the keyboard of the MacBook Pro. Participants pressed the return key after they had typed the last letter of the stimulus word. That action initiated the appearance of the target stimulus in the center of the string. Participants were asked to verify that this was in fact the stimulus that they saw by pressing a key marked “yes” or “no” on the keyboard (all participants responded “yes” to all words).  Their pressing of the “yes” key ended the trial. The screen then went blank for 2 seconds, after with the progressive demasking component of the next trial began.  The details of each of two the trial components are presented below.

\subsection{The progressive demasking component}\label{sec:libben:2.3.1}
The key feature of the progressive demasking is that words appear very slowly as though they were emerging from a fog. This effect was created in this experiment by alternating the presentation of a stimulus word and a pattern mask of cross hatches (\#\#\#\#\#\#\#\#\#\#) over 18 cycles. Each cycle was 300\,ms in length. In the first cycle, the target word is presented for only 16\,ms and the mask is presented for 284\,ms. In the next cycle, the target is presented for 16\,ms longer than in the previous cycle and the mask is presented for 16\,ms less (i.e., 32\,ms and 268\,ms respectively), Thus, in each successive cycle, the target word becomes more visible. Typically, for real and novel compound words, the stimulus word is identified in under 10 cycles (3,000\,ms). In the present study, participants were randomly assigned to one of two progressive demasking procedures. The difference between the groups was that Group 1 participants were asked to press the keyboard return key as soon as they could identify the word. Group 2 participants were asked to say the word aloud as soon as they could identify it. These two groups were created in order to test whether saying the stimuli aloud in the progressive demasking task would have the effect of disambiguating the ambiguous stimuli in the subsequent typing task.

\subsection{The typing component}\label{sec:libben:2.3.2}
For each stimulus, the typing component of the task began immediately following the participant’s identification of the progressively demasked stimulus. Typing was done on a standard laptop keyboard, and the letters that the participant typed were visible on the screen (as is the case in normal typing). Participants were able to self-correct during word typing by pressing the backspace key. As soon as they finished typing the word, they pressed the return key. This ended the typing component of the trial.

\section{Results}\label{sec:libben:3}

Our analysis focused on trials in which stimuli were typed without error (i.e., the word produced was that which was presented and was typed without the backspace key having been pressed).  The overall accuracy rate, defined in this way, was 79\%. The progressive demasking response latencies and letter typing times for correctly typed stimuli were analyzed using linear mixed effects models in R.

\subsection{Progressive demasking}\label{sec:libben:3.1}

The analysis of progressive demasking latencies in a generalized linear mixed effects model did not yield significant effects of recognition latency differences related to whether the stimulus was ambiguous, whether the ambiguity resulted in a pronunciation change, or whether participants responded by saying the word aloud or by pressing the return key. There was, however, a facilitating effect of the frequency of the initial substring of the stimulus ($p<0.001$). This is consistent with the expectation that Fuzzy Forward Lexical Activation is driven by the familiarity of an initial lexical substring. No other significant lexical frequency effects were observed in the progressive demasking task or in the typing task (e.g., for a stimulus such as \textit{clampeel}, the frequency of \textit{clam} had an effect, but the frequencies of \textit{clamp}, \textit{peel}, or \textit{eel} did not). Lexical frequency values were obtained from the CELEX English lemma databases \citep{BaayenGulikers1995}.

\subsection{Typing}\label{sec:libben:3.2}
In the analysis of typing times, the random effects included participant, stimulus and letter typed. This last random effect was included to capture the influences of factors that could be associated with the typing of a particular letter on a keyboard. These may include whether it is a consonant or a vowel, whether it is typed with the right hand or left hand, the index finger or some other finger, etc.

The two key fixed effects in the model were the position of the letter with respect to the constituent boundary and stimulus ambiguity (ambiguous vs.\ nonambiguous). For the variable ``letter location around boundary'', four locations were targeted:

\begin{enumerate}
\item the letter before the first constituent boundary (e.g., \textit{m} in \textit{clampeel}). This is on the intercept;
\item the letter at the first constituent boundary (e.g., \textit{p} in \textit{clampeel});
\item the letter at the second constituent boundary (e.g., the first \textit{e} in \textit{clampeel});
\item the letter after the second constituent boundary (e.g., the second \textit{e} in \textit{clampeel});
\end{enumerate}

This factor was investigated as a fixed effect and in terms of its interaction with stimulus ambiguity.

There was no effect or interaction associated with whether the participant responded in the progressive demasking task by pressing the return key or by saying the stimulus aloud ($p>0.1$). This variable was removed from the model and the participants were treated as a single group.

The analysis began with the two key factors above. To this, a number of control factors were added. These included trial ($p=0.003$), which indicated that participants' typing got faster as they progressed through the experiment. The variable ``position within the word'' was also added. This variable, which was marginally significant ($p=0.049$), showed a tendency for participants to be somewhat slower at later points in the word. The inclusion of this factor improved the model and acted as a control for the fact that the first constituent boundary for some stimuli (e.g., \textit{clampeel}) was at letter 5 of the stimulus, whereas, for others, (e.g., \textit{damplane}) it was at letter 4. Stimuli with constituent boundaries later in the string were associated with slower typing times.

The four additional control variables that were added to the model all concern the frequency of letter sequences. All improved model performance. The first was the overall bigram frequency of the stimulus string, obtained from the English Lexicon Project \citep{BalotaEtAl2007}. The second was the frequency of the letter being typed in combination with its preceding letter. The third was the frequency of the letter being typed in combination with its following letter. Finally, the fourth variable was the frequency of the two-letter sequence at the first constituent boundary. Whereas, in the first three bigram frequency measures, higher frequency was associated with faster typing times, the opposite was the case for bigram frequency at the constituent boundary. Here, higher bigram frequency slowed typing times. This observation is consistent with the view that typing involves chunking by constituent and therefore, high frequency bigram transitions that could potentially disrupt the segmentation of the novel compound into constituents are disruptive.

The results of typing times showed effects of bigram frequency, location with respect to constituent boundaries, and ambiguity.  The analysis of these data patterns is presented in \tabref{tab:libben:5} and \figref{fig:libben:4}.\largerpage

As can be seen in \figref{fig:libben:4}, the non-ambiguous stimuli (e.g., \textit{anklecob}) show a clear typing pause at the constituent boundary. That is, at the point at which they type the first letter of the second constituent (e.g., the \textit{c} in \textit{anklecob}). Letter typing times for the following letter drop considerably to below 200 milliseconds immediately following that letter. In contrast, that same position shows typing times in the 250 millisecond range for ambiguous stimuli. The key difference is that, for ambiguous stimuli, that position (e.g., the \textit{e} in \textit{clampeel}), is at once a constituent boundary in the reading \textit{clamp-eel} and the second letter in the reading \textit{clam-peel}. This dual status seems to be reflected in the per letter typing times shown in \figref{fig:libben:4}.

\begin{sidewaystable}
\caption{Fixed effects of the predictors in the linear mixed effects model for letter typing times. (Note: \text{*} = $p < 0.05$; \text{**} = $p < 0.01$; $\text{***} = p < 0.001$)\label{tab:libben:5}}
\begin{tabular}{clSSSSS[table-format=<1.3]l}
\lsptoprule
 ID & Factor and level names &  {Estimate} &  {Std. Error} &  {df} &  {\textit{t}-value} &  {$p$} & \\\midrule
 1 & (Intercept) &  618.8 &  131.3 &  61.5 &  4.7 &  >.001 & ***\\
 2 & Bigram Freq. &  -27.6 &  15.0 &  40.0 &  -1.8 &  .073 & \\
 3 & Trial &  -0.5 &  0.2 &  3246.6 &  -3.0 &  .003 & **\\
 4 & Position in word &  17.8 &  8.7 &  39.4 &  2.0 &  .049 & *\\
 5 & Freq. of letter and its predecessor &  -22.8 &  3.5 &  1083.6 &  -6.5 &  .000 & ***\\
 6 & Freq. of letter and its successor &  -8.4 &  3.1 &  1474.2 &  -2.7 &  .008 & **\\
 7 & Freq. of bigram at boundary 1 &  16.3 &  4.9 &  40.9 &  3.3 &  .002 & **\\
 8 & Letter is 2nd constituent onset (v.1) &  30.9 &  13.1 &  189.3 &  2.4 &  .019 & *\\
 9 & Letter is 2nd constituent onset (v.2) &  43.1 &  19.8 &  64.8 &  2.2 &  .033 & *\\
 10 & Letter is 2nd constituent letter 3 (v.1) &  -31.8 &  27.6 &  48.7 &  -1.2 &  .255 & \\
 11 & Nonambiguous stimulus &  5.3 &  20.9 &  69.1 &  0.3 &  .801 & \\
 12 & Interaction of 8 X 11 &  59.2 &  17.2 &  2288.3 &  3.4 &  .001 & ***\\
 13 & Interaction of 9 X  11 &  -80.3 &  17.1 &  1937.3 &  -4.7 &  .000 & ***\\
 14 & Interaction of 10 X  11 &  -17.5 &  18.2 &  2599.8 &  -1.0 &  .338 & \\
\lspbottomrule
\end{tabular}
\end{sidewaystable}

\begin{figure}
\includegraphics[width=.8\textwidth]{figures/Libbenfigure4.png}
\caption{\label{fig:libben:4}Per letter typing times for ambiguous novel compounds (e.g., \textit{clampeel}) and non-ambiguous novel compounds (e.g., \textit{anklecob}).}
\end{figure}

The notion of dual status accords with the view that lexical superstates characterize ambiguous strings such as \textit{clampeel}.  The data obtained through this experiment also seem to suggest that lexical superstates remain intact even when they could have been disambiguated as a result of reading aloud.  The data showed no interaction of response type (return key vs. reading aloud) with stimulus type (unambiguous vs. ambiguous with sound change vs. ambiguous without sound change).

\section{General discussion}\label{sec:libben:4}

This chapter has focused on English novel compounds as words that are themselves multiword expressions. I have claimed that the investigation of these structures can advance our understanding of morphological processing in general and the parsing of multiword lexical strings, in particular.  In that context, ambiguous novel compounds such as \textit{clampeel} may have a special role to play. Because they are ambiguous (e.g., can be parsed into \textit{clam-peel} or \textit{clamp-eel}) they enable us to investigate whether lexical processing results in the activation of one structure or all possible structures.  The prediction for these stimuli, in accordance with previous research by \citet{LibbenDerwingdeAlmeida1999}, was that we should see evidence of the activation of all potential constituents of ambiguous novel compounds in a word typing task.  This prediction is based on the claim that a core property of lexical representations is that they are shaped by patterns of lexical activity and they are commonly in a lexical superstate, rather than in any particular morphological configuration \citep{Libbeninpress}.

An experiment was reported in which 24 participants each saw 45 novel compounds as progressively demasked stimuli and were required to type each of these as quickly and as accurately as possible. Typing times for each letter were recorded.

\subsection{Lexical superstates}\label{sec:libben:4.1}

The typing data are consistent with the lexical superstate hypothesis.  Whereas the non-ambiguous novel compounds such as \textit{anklecob} showed a sharp spike in letter typing times at the location between the two compound constituents, the ambiguous ones (e.g., \textit{clampeel}) showed more moderately elevated letter typing times at both putative inter-constituent locations (e.g., between \textit{clam} and \textit{peel} and between \textit{clamp} and \textit{eel}). This pattern of results is consistent with the view that such ambiguous words are in a lexical superstate so that the language user can employ the most appropriate interpretation of the string, depending on the situation.  I would argue that this phenomenon of lexical superstates is particularly easily seen in the case of ambiguous novel compounds but, in fact, is present in all putatively multimorphemic words. All such existing words are, by definition, structurally ambiguous. The simple reason for this is that they can at once have decomposed and undecomposed interpretations.  Again, lexical superstates allow the language user to employ whichever of these is most appropriate or most needed under particular circumstances.

An additional reason why the investigation of ambiguous novel compounds can be revealing of the underlying principles of lexical processing is that they constitute, by their nature, a controlled experiment.  They do not have existing whole word memory traces. So, when a participant encounters a novel compound, they must create an interpretation in real time. This interpretation can only be created with reference to possible internal constituents. Thus, these compounds provide us the controlled conditions under which we can investigate how lexical substrings are identified and how putative constituents are created.

\subsection{Action-based sublexical structure}\label{sec:libben:4.2}

If indeed, as I propose, morphological structure arises from lexical activity and words are more properly considered to be actions rather than things, an action-based account of how morphology comes about is required. I propose Fuzzy Forward Lexical Activation as such an account. Fuzzy Forward Lexical Activation has a maximally simple functional architecture. It claims that visual lexical processing in English proceeds from beginning to end and that, as soon as an initial lexical substring is identified, the system ``looks right'' to the end of the string for a possible concluding lexical substring.  It then continues in a left-to-right manner so that any possible initial substrings will be longer and any possible final substrings will be shorter. In this way, the heuristic only creates initial and final substrings (i.e., those that start at the beginning of the string and those that end at the end of the string, respectively).  All internal structures, therefore, will be binary.  Importantly, however, these binary structures will be overlapping for all multi-constituent strings.  These overlaps, created through lexical activity, constitute the structural lexical superstates for the words that are shown in \tabref{tab:libben:1}.

Thus, I claim that Fuzzy Forward Lexical Activation offers a simple mechanism for the activation of sublexical elements of a word. It renders hierarchical structure epiphenomenal, but at the same time offers an explanation for why English language users have multiple interpretation for ambiguous stimuli and left-branching and right-branching interpretations for words such as \textit{unlockable}.

\subsection{Action based lexical development is situation specific}\label{sec:libben:4.3}

It is important to note that the approach to sublexical structure discussed here is, by definition, linked to the specific experience that a language user has with language processing and the specific conditions under which language processing is taking place at the time of measurement.  Thus, for example, in this study, we did not observe a point at which overlaying alternative parses of ambiguous novel compounds are collapsed. It was expected that this might be observable by inspecting the interaction of response type (keypress vs. word naming) and type of ambiguous novel compounds (with sound change vs. without sound change). The reasoning behind this was that, in the word naming task, a choice between parsing alternatives would have to be made for stimuli such as \textit{babelarch}, which have different pronunciations, depending on the parsing choice.  The fact that this interaction was not observed may be related to the specific conditions of the experiment (e.g., the high density of ambiguous structures or perhaps the ability of participants to ``reset'' between the recognition and production components of each trial).

In addition to exploring the effects of varying task demands using stimuli of this sort, it would be valuable to investigate language demands.  It seems reasonable to expect that the “look-right to the end” feature of Fuzzy Forward Lexical Activation is developed as English language users adapt to the demands and opportunities created by the English writing system. It is very likely that this is a language-specific adaptation. For German, for example, it might be expected that language users might not create final substrings that must reach to the end of the word. The reason for this is that German has unspaced tri-constituent (and longer) compounds that the English writing system does not allow. Considerations such as these enhance the probability, in my view, that the conclusions we draw concerning language processing have enhanced ecological validity.  If we accept the view that words are patterns of action, rather than static representations, then we must also expect that their psycholinguistic instantiations will correspond with individual variability in language experience.

\section*{Acknowledgments}
The development of this chapter was supported by the Social Sciences and Humanities Research Council of Canada Partnership Grant 895-2016-1008 ``Words in the World''.

{\sloppy\printbibliography[heading=subbibliography,notkeyword=this]}
\end{document}

ext: tex


text:
\chapter{Implementation}\label{chap:implementation}
There are two software components that comprise this work, one for clustering with \dbscan{}, which also creates the graphs of cluster metrics, and another for the \kraplong{} (\krap{}).
Future work will incorporate \krap{} into \cplop{} for \mstlong{}.

\section{Graphing Cluster Metrics}
The clustering code is comprised of two main parts: the clustering library from \cite{johnson2015density} and a series of scripts to graph the cluster metrics shown in \autoref{chap:clustering}.
The clustering library queries a local instance of the \cplop{} database, performs the clustering, and saves the resulting clusters in a series of \pickle{}, \json{}, and \csv{} files.
The graphing code then parses the clusters, counting the species in each cluster and calculating the purity in order to build the series of graphs.
All of this code is written in \python{} and uses \matplotlib{} for graphing.
The clustering library is described in \cite{johnson2015density}and found at \url{https://github.com/ejohns32/Thesis-Code}.
The code written for this work does not change any of it, but instead adds code to control relevant pieces and graph the metrics.

\section{The \kraplong{}}
The code for the \kraplong{} (\krap{}) is a \java{} library that performs the evaluation described in \autoref{sec:evaluation:krap}.
It queries a local instance of the \cplop{} database and for each \cplop{} \isol{}, it performs cross-validation with holdout for a range of \k{} values, \a{} values, and with each resolution strategy.
It saves the classification results as a \csv{}, which a \python{} script graphs using \matplotlib{}.
The code resides at \url{https://github.com/jmcgover/k-rap} as well as relevant documentation.

max_stars_repo_name: jmcgover/thesis

max_issues_repo_name: jmcgover/thesis

max_forks_repo_name: jmcgover/thesis


text:
%.*****************************************************************>
%.* VAXTAP Reference Guide - Front Material                       *>
%.*  Last Mod.   26 Jan 1992 09:15  mg                            *>
%.*****************************************************************>

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%    Tile page                                                     %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\Ptitle#1{\special{ps: /Printstring (#1) def}
\epsfbox{/user/goossens/cnasall/cnastit.eps}}
\begin{titlepage}
\vspace*{-23mm}
\mbox{\epsfysize30mm\epsfbox{/usr/local/lib/tex/ps/cern15.eps}}
\hfill
\raise8mm\hbox{\Large\bf CERN Program Library Long Writeup Z312}
\hfill\mbox{}
\begin{center}
\mbox{}\\[10mm]
\mbox{\Ptitle{VAXTAP}}\\[2cm]
{\LARGE VAX/VMS}\\[1cm]
{\LARGE Tape Handling Package}\\[2cm]
{\LARGE Version 1.20 (December 1992)}\\[3cm]
{\Large Application Software Group}\\[1cm]
{\Large Computers and Network Division}\\[2cm]
\end{center}
\vfill
\begin{center}\Large CERN Geneva, Switzerland\end{center}
\end{titlepage}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%    Copyright  page                                               %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\thispagestyle{empty}
\framebox[\textwidth][t]{\hfill\begin{minipage}{0.92\textwidth}%
\vspace*{3mm}\begin{center}Copyright Notice\end{center}
\parskip\baselineskip
{\bf VAXTAP -- VAX Tape Handling Package}

CERN Program Library entry {\bf Q123}

Copyright CERN, Geneva 1992

Copyright and any other appropriate legal protection of these
computer programs and associated documentation reserved in all
countries of the world.

These programs or documentation may not be reproduced by any
method without prior written consent of the Director-General
of CERN or his delegate.

Permission for the usage of any programs described herein is
granted apriori to those scientific institutes associated with
the CERN experimental program or with whom CERN has concluded
a scientific collaboration agreement.

Requests for information should be addressed to:
\vspace*{-.5\baselineskip}
\begin{center}
\tt\begin{tabular}{l}
CERN Program Library Office              \\
CERN-CN Division                         \\
CH-1211 Geneva 23                        \\
Switzerland                              \\
Tel.      +41 22 767 4951                \\
Fax.      +41 22 767 7155                \\
Bitnet:   CERNLIB@CERNVM                 \\
DECnet:   VXCERN::CERNLIB (node 22.190)  \\
Internet: CERNLIB@CERNVM.CERN.CH
\end{tabular}
\end{center}
\vspace*{2mm}
\end{minipage}\hfill}%end of minipage in framebox
\vspace{6mm}

{\bf Trademark notice: All trademarks appearing in this guide are acknowledged
as such.}
\vfill
\begin{tabular}{l@{\quad}l@{\quad}>{\tt}l}
{\em Contact Person\/}:        & Jamie Shiers /CN    & (JAMIE\atsign CERNVM.CERN
.CH)\\[1mm]
{\em Technical Realization\/}: & Michel Goossens /CN & (GOOSSENS\atsign CERNVM.C
ERN.CH)\\[2cm]
\end{tabular}
\newpage

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%    Introductory material                                         %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pagenumbering{roman}
\setcounter{page}{1}

\Filename{H2vaxfront-Preliminary-remarks}
\section*{Preliminary remarks}

This {\bf Complete Reference} of
the VAXTAP package consists of three parts:
\begin{OL}
\item An {\bf overview} of the system.
\item A {\bf user guide}, describing each command in detail.
\item An {\bf installation and management guide}.
\end{OL}

\begin{center}
\fbox{\parbox{12cm}{Throughout this manual, commands to be {\bf entered}
are {\tt\underline{underlined}}}}
\end{center}

\index{underlining}
\index{user input}

\Filename{H2vaxfront-Acknowledgements}
\section*{Acknowledgements}

\par This document has been produced using \LaTeX{} with
the {\tt CERNMAN} style option.
All pictures shown are produced with PAW and are included in
PostScript\cite{bib-POST} format in the manual.
\newpage
\Filename{H2vaxfront-Related-Documents}
\section*{Related Documents}
\par This document can be complemented by the following documents:
\begin{UL}
\item The FATMEN Report - DD/89/15\cite{bib-FATREP}
\item FATMEN User Guide~\cite{bib-FATMEN}
\item TMS - The CERN Tape Management System (to be published)
\end{UL}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%    Tables of contents ...                                        %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\tableofcontents
\listoffigures
\listoftables

max_stars_repo_name: berghaus/cernlib-docs

max_issues_repo_name: berghaus/cernlib-docs

max_forks_repo_name: berghaus/cernlib-docs


text:
\section{Literature Review}
    It describes the state-of-the-art body and analyzes the most representative studies related to the research project. It must include a summary of methodological and practical gaps identified by authors that clearly positions the main contribution of the research.

max_stars_repo_path: Sections/2.Literature review.tex

max_stars_repo_name: daynoryamil/Academic-Journal-Template

max_issues_repo_path: Sections/2.Literature review.tex

max_issues_repo_name: daynoryamil/Manuscript-Template

max_forks_repo_path: Sections/2.Literature review.tex

max_forks_repo_name: daynoryamil/Manuscript-Template


text:
\section{Lines}\label{s:lines}
In this section we will discuss how to represent lines and a wide variety of applications.

\subsection{Line representation}\label{ss:line-rep}
Lines are sets of points $(x,y)$ in the plane which obey an equation of the form $ax+by=c$, with at least one of $a$ and $b$ nonzero. $a$ and $b$ determine the direction of the line, while $c$ determines its position.

\centerFig{line0}

Equation $ax+by=c$ can be interpreted geometrically through dot product: if we consider $(a,b)$ as a vector, then the equation becomes $(a,b)\cdot(x,y) = c$. This vector is perpendicular to the line, which makes sense: we saw in \ref{ss:dot} that the dot product remains constant when the second vector moves perpendicular to the first.

\centerFig{line1}

The way we'll represent lines in code is based on another interpretation. Let's take vector $(b,-a)$, which is parallel to the line. Then the equation becomes a cross product $(b,-a)\times(x,y) = c$. Indeed, we saw in \ref{ss:cross} that the cross product remains constant when the second vector moves parallel to the first.

\centerFig{line2}

In this way, finding the equation of a line going through two points $P$ and $Q$ is easy: define the direction vector $\dir = (b,-a) = \vv{PQ}$, then find $c$ as $\dir\times P$.
\begin{lstlisting}
struct line {
    pt v; T c;
    // From direction vector v and offset c
    line(pt v, T c) : v(v), c(c) {}
    // From equation ax+by=c
    line(T a, T b, T c) : v({b,-a}), c(c) {}
    // From points P and Q
    line(pt p, pt q) : v(q-p), c(cross(v,p)) {}

    // Will be defined later:
    // - these work with T = int
    T side(pt p);
    double dist(pt p);
    line perpThrough(pt p);
    bool cmpProj(pt p, pt q);
    line translate(pt t);
    // - these require T = double
    void shiftLeft(double dist);
    pt proj(pt p);
    pt refl(pt p);
}
\end{lstlisting}

A line will always have some implicit orientation, with two sides: the ``positive side'' of the line ($ax+by-c > 0$) is on the left of $\dir$, while the ``negative side'' ($ax+by-c < 0$) is on the right of $\dir$.
In our implementation, this orientation is determined by the points that were used to create the line.
We will represent it by an arrow at the end of the line. The figure below shows the differences that occur when creating a line as \lstinline|line(p,q)| or \lstinline|line(q,p)|.

\centerFig{line3}

\subsection{Side and distance}\label{ss:side-dist}
One interesting operation on lines is to find the value of $ax+by-c$ for a given point $(x,y)$. For line $l$ and point $P=(x,y)$, we will denote this operation as
\[\side_l(P) \coloneqq ax+by-c = \dir \times P - c.\]

As we saw above, it can be used to determine which side of the line a certain point is, and $\side_l(P) = 0$ if and only if $P$ is on $l$ (we will use this property a few times). You may notice that $\side_{PQ}(R)$ is actually equal to $\orient(P,Q,R)$.

\centerFig{line4}

\begin{lstlisting}
T side(pt p) {return cross(v,p)-c;}
\end{lstlisting}

The $\side_l(P)$ operation also gives the distance to $l$, up to a constant factor: the bigger $\side_l(P)$ is, the further from line $l$. In fact, we can prove that $|\side_l(P)|$ is $\norm{v}$ times the distance between $P$ and $l$ (this should make sense if you've read the ``mathy insight'' in section~\ref{ss:cross}).

\centerFig{line5}

This gives an easy implementation of distance:
\begin{lstlisting}
double dist(pt p) {return abs(side(p)) / abs(v);}
\end{lstlisting}
The squared distance can be useful to check if a point is within a certain integer distance of a line, because when using integers the result is exact if it is an integer.
\begin{lstlisting}
double sqDist(pt p) {return side(p)*side(p) / (double)sq(v);}
\end{lstlisting}

\subsection{Perpendicular through a point}\label{perpThrough}
Two lines are perpendicular if and only if their direction vectors are perpendicular. Let's say we have a line $l$ of direction vector $\vv{v}$. To find a line perpendicular to line $l$ and which goes through a certain point $P$, we could define its direction vector as $\perpop(\dir)$ (that is, $\vv{v}$ rotated by $90\degree$ counter-clockwise, see section~\ref{ss:rotation}) and then try to work out $c$. However, it's simpler to just compute it as the line from $P$ to $P + \perpop(\dir)$.

\centerFig{line6}

\begin{lstlisting}
line perpThrough(pt p) {return {p, p + perp(v)};}
\end{lstlisting}

\subsection{Sorting along a line}\label{ss:sort-line}
One subtask that often needs to be done in geometry problems is, given points on a line $l$, to sort them in the order they appear on the line, following the direction of $\vv{v}$.% If the line is created as \lstinline|line(p,q)|, they should be sorted so that $P$ comes before $Q$.

\centerFig{line7}

We can use the dot product to figure out the order of two points: a point $A$ comes before a point $B$ if $\vv{v} \cdot A < \vv{v} \cdot B$. So we can a comparator out of it.
\begin{lstlisting}
bool cmpProj(pt p, pt q) {
    return dot(v,p) < dot(v,q);
}
\end{lstlisting}
In fact, this comparator is more powerful than we need: it is not limited to points on $l$ and can compare two points by their orthogonal projection\footnote{If you don't know what an orthogonal projection is, read section~\ref{ss:proj-refl}.} on $l$. This should make sense if you have read the ``mathy insight'' in section~\ref{ss:dot}.

\subsection{Translating a line}
If we want to translate a line $l$ by vector $\vv{t}$, the direction vector $\dir$ remains the same but we have to adapt $c$.

\centerFig{line8}

To find its new value $c'$, we can see that for some point $P$ on $l$, then $P+\vv{t}$ must be on the translated line. So we have
\begin{align*}
\side_l(P) &= \vv{v} \times P - c = 0\\
\side_{l'}\left(P + \vv{t}\right) &= \vv{v} \times \left(P + \vv{t}\right) - c' = 0
\end{align*}
which allows us to find $c'$:
\[c' = \dir \times (P+\vv{t}) = \dir\times P + \dir\times\vv{t} = c + \dir\times\vv{t}\]
\begin{lstlisting}
line translate(pt t) {return {v, c + cross(v,t)};}
\end{lstlisting}

A closely related task is shifting line $l$ to the left by a certain distance $\delta$ (or to the right by $-\delta$).

\centerFig{line9}

This is equivalent to translating by a vector of norm $\delta$ perpendicular to the line, which we can compute as
\[\vv{t} = (\delta/\norm{\dir})\perpop(\dir)\]
so in this case $c'$ becomes
\begin{align*}
c' &= c + \dir\times\vv{t}\\
&= c + (\delta/\norm{\dir})(\dir\times\perpop(\dir))\\
&= c + (\delta/\norm{\dir})\norm{\dir}^2\\
&= c + \delta\norm{\dir}
\end{align*}

\begin{lstlisting}
line shiftLeft(double dist) {return {v, c + dist*abs(v)};}
\end{lstlisting}

\subsection{Line intersection}\label{line-line}
There is a unique intersection point between two lines $l_1$ and $l_2$ if and only if $\dirof{l_1} \times \dirof{l_2} \neq 0$. If it exists, we will show that it is equal to
\[P = \frac{c_{l_1}\dirof{l_2} - c_{l_2}\dirof{l_1}}{\dirof{l_1} \times \dirof{l_2}}\]

\centerFig{line10}

We only show that it lies on $l_1$ (it should be easy to see that the expression is actually symmetric in $l_1$ and $l_2$). It suffices to see that $\side_{l_1}(P) = 0$:
\begin{align*}
\side_{l_1}(P) &= \dirof{l_1} \times \left(\frac{c_{l_1}\dirof{l_2} - c_{l_2}\dirof{l_1}}{\dirof{l_1} \times \dirof{l_2}}\right)-c_{l_1} \\
&=\frac{c_{l_1}(\dirof{l_1}\times\dirof{l_2}) - c_{l_2}(\dirof{l_1}\times\dirof{l_1}) - c_{l_1}(\dirof{l_1}\times\dirof{l_2})}{\dirof{l_1} \times \dirof{l_2}} \\
&=\frac{-c_{l_2}(\dirof{l_1}\times\dirof{l_1})}{\dirof{l_1} \times \dirof{l_2}} \\
&=0
\end{align*}

\begin{lstlisting}
bool inter(line l1, line l2, pt &out) {
    T d = cross(l1.v, l2.v);
    if (d == 0) return false;
    out = (l2.v*l1.c - l1.v*l2.c) / d; // requires floating-point coordinates
    return true;
}
\end{lstlisting}

\subsection{Orthogonal projection and reflection}\label{ss:proj-refl}
The orthogonal projection of a point $P$ on a line $l$ is the point on $l$ that is closest to $P$. The reflection of point $P$ by line $l$ is the point on the other side of $l$ that is at the same distance and has the same orthogonal projection.

\centerFig{line11}

To compute the orthogonal projection of $P$, we need to move $P$ perpendicularly to $l$ until it is on the line.
%, that is, until we reach some point $P'$ such that $\side_l(P')=0$.
In other words, we need to find the factor $k$ such that $\side_l(P+k\perpop(\dir)) = 0$.

We compute
\begin{align*}
\side_l(P + k\perpop(\dir))
&= \dir \times (P + k\perpop(\dir)) - c\\
&= \dir \times P + \dir \times k\perpop(\dir) - c\\
&= (\dir \times P - c) + k (\dir \times \perpop(\dir))\\
&= \side_l(P) + k \norm{\dir}^2
\end{align*}
so we find $k = -\side_l(P) / \norm{\dir}^2$.
\begin{lstlisting}
pt proj(pt p) {return p - perp(v)*side(p)/sq(v);}
\end{lstlisting}

To find the reflection, we need to move $P$ in the same direction but twice the distance:
\begin{lstlisting}
pt refl(pt p) {return p - perp(v)*2*side(p)/sq(v);}
\end{lstlisting}

\subsection{Angle bisectors}
An angle bisector of two (non-parallel) lines $l_1$ and $l_2$ is a line that forms equal angles with $l_1$ and $l_2$. We define the \term{internal bisector} $\lint$ as the line whose direction vector points between the direction vectors of $l_1$ and $l_2$, and the \term{external bisector} $\lext$ as the other one. They are shown in the figure below.

\centerFig{line12}

An important property of bisectors is that their points are at equal distances from the original lines $l_1$ and $l_2$. In fact, if we give a sign to the distance depending on which side of the line we are on, we can say that $\lint$ is the line whose points are at opposite distances from $l_1$ and $l_2$ while $\lext$ is the line whose points are at equal distances from $l_1$ and $l_2$.

For some line $l$ can compute this signed distance as $\side_l(P)/\normv{v}$ (in section~\ref{ss:side-dist} we used the absolute value of this to compute the distance). So $\lint$ should be the line of all points for which
\begin{align*}
&\frac{\side_{l_1}(P)}{\norm{\dirof{l_1}}} = -\frac{\side_{l_2}(P)}{\norm{\dirof{l_2}}}\\[.3cm]
\Leftrightarrow\quad &\frac{\dirof{l_1}\times P - c_{l_1}}{\norm{\dirof{l_1}}} = - \frac{\dirof{l_2}\times P - c_{l_2}}{\norm{\dirof{l_2}}}\\[.3cm]
\Leftrightarrow\quad &\left(\frac{\dirof{l_1}}{\norm{\dirof{l_1}}} + \frac{\dirof{l_2}}{\norm{\dirof{l_2}}}\right) \times P
- \left(\frac{c_{l_1}}{\norm{\dirof{l_1}}} + \frac{c_{l_2}}{\norm{\dirof{l_2}}}\right) = 0
\end{align*}

This is exactly an expression of the form $\side_l(P) = \vv{v} \times P - c = 0$ which defines the points on a line. So it means that we have found the $\vv{v}$ and $c$ that characterize $\lint$:
\begin{align*}
\vv{v} &= \frac{\dirof{l_1}}{\norm{\dirof{l_1}}} + \frac{\dirof{l_2}}{\norm{\dirof{l_2}}}\\[.2cm]
c &= \frac{c_{l_1}}{\norm{\dirof{l_1}}} + \frac{c_{l_2}}{\norm{\dirof{l_2}}}
\end{align*}

The reasoning is very similar for $\lext$, the only difference being signs. Both can be implemented as follows.
\begin{lstlisting}
line bisector(line l1, line l2, bool interior) {
    assert(cross(l1.v, l2.v) != 0); // l1 and l2 cannot be parallel!
    double sign = interior ? 1 : -1;
    return {l2.v/abs(l2.v) + l1.v/abs(l1.v) * sign,
            l2.c/abs(l2.v) + l1.c/abs(l1.v) * sign};
}
\end{lstlisting}

max_stars_repo_name: cbarnson/UVa

max_stars_repo_licenses: Unlicense MIT

max_issues_repo_name: cbarnson/UVa

max_issues_repo_licenses: Unlicense MIT

max_forks_repo_name: cbarnson/UVa

max_forks_repo_licenses: Unlicense MIT