Computer Science 4750, Fall '25
Course Diary

---

Copyright 2025 by H.T. Wareham
All rights reserved

---

Week 1, (Course Project Proposal and Report Notes), Week 2, Week 3, (end of diary)

Tuesday, September 9 (Lecture #1) (FS)
[Class Notes]

• Went over course outline.
• Introduction: What is Natural Language?
  • A natural language is any language (be it spoken, signed, or written) used by human beings to communicate with each other.
  • There are ~7000 natural languages, with ~20 these languages, e.g., Mandarin, Spanish, English, Hindi, and Arabic, being spoken by more than 1% of the world's population.
  • Example: The natural languages spoken by students in this course.
  • Human language allows a complexity of expression and meaning that has to date not been seen in linguistic behaviour in animals, e.g., bird calls,, primate vocalizations, bee dances, which are more akin to lists of codewords with specific meanings that are not combined, e.g., "danger", "(this way to) food".
    • Gorilla ASL experiments suggest that it is not just the lack of an appropriate vocal apparatus -- the ability to combine words to form arbitrarily complex expressions is simply not present in animals.
    • Talking animals are for now firmly in the domain of fiction (and comedy).
  • Example: Not the Nine O'Clock News (1980): Gerald the Gorilla (Link)
  • The ability to acquire and effectively communicate with a natural language is one of the major hallmarks of human intelligence and sentience; those individuals who have for whatever reasons fail to develop this ability are often considered subhuman, e.g., feral children (the Wild Boy of Aveyron), the deaf (Children of a Lesser God, Helen Keller).
  • Example: The Miracle Worker (1962) [excerpt]
  • The ability to acquire and effectively communicate with a natural language is thus one of the major hallmarks of true artificial intelligence.
• Introduction: What is Natural Language Processing (NLP)?
  • NLP is the subfield of Artificial Intelligence (AI) concerned with the computations underlying the processing (recognition, generation, and acquisition) of natural human language (be it spoken, signed, or written).
    • NLP is distinguished from (though closely related to) the processing of artificial languages, e.g., computer languages, formal languages (regular, context-free, context-sensitive, etc).
  • NLP emerged in the early 1950's with the first commercial computers; originally focused on machine translation, but subsequently broadened to include all natural-language related tasks (J&M, Section 1.6; Kay (2003); see also BKL, Section 1.5 and Afterword).
  • Two flavors of NLP: strong and weak
    • The focus of Strong NLP is on discovering and implementing human-level language abilities using approximately the same mechanisms as human beings when they communicate; as such, it is more closely allied with classical linguistics (and hence often goes by the name "computational linguistics").
    • The focus of Weak NLP is on giving computers human-level language abilities by whatever means possible; as such, it is more closely allied with AI (and is often referred to by either "NLP" or more specific terms like "speech processing").
    • Weak NLP is nonetheless influenced by Strong NLP, and vice versa (to the extent that the mechanisms proposed in Weak NLP to get systems up and running help to revise and make more plausible the theories underlying Strong NLP).
    • In this course, we will look at both types of NLP, and distinguish them as necessary.
• Potential exam questions

Thursday, September 11

• Course Project Proposal and Report Notes
  Over the next 7 weeks, you should choose the topic of your course project (for inspiration, see the lists of presented student course projects in the last two weeks of the course diarys of previous offerings of CS 4750). This project can take the form of a literature survey on an NLP topic of interest to you or a software system implementing a particular NLP task. Each course project *** MUST *** be approved by the course instructor; please do this by chatting with your course instructor by October 31st. Course projects that are not approved prior to the submission of the associated project proposal (see below) will receive a mark of zero.

  Once a course project is approved, you must write and submit a printout of your project proposal to the course instructor by 9am on Tuesday, November 4. This proposal is worth 5 course marks. It should be about a page long and consist of a 3-paragraph proposal text (3.5 marks total) (with the first paragraph motivating why your topic is of interest (1 mark), the second summarizing previous work on this topic (1.5 marks), and the third summarizing the focus of your survey or the approach you will use in constructing your software system (1 mark)) followed by at least five full-information literature references particular to the topic of your project which must each be cited at least once in your proposal text (1.5 marks total) (0.3 marks per reference up to 5 references).

  Once the project proposal is submitted, you have until noon on Friday, December 5, to do your project and submit a printout of your project report. In general, In general, this project will entail (as a minimum) a 15-20 page report (double-spaced) with 10-30 literature references (for a literature-survey project) or a 5-8 page report (double-spaced) with 5-15 references in addition to the software (for a software project). All included references MUST be cited in the body of the report. Though purely Web-based references (e.g., blogs, reference manuals) are acceptable, please try where at all possible to obtain literature-based references, e.g., books, book chapters, journal papers, conference papers; in those cases, You MUST give full references listing all reference information appropriate to the type of reference, author names, publication year, full paper title, book title with editors, journal name, journal volume and number, publisher, page numbers.

  The length and reference-number requirements above may vary depending on the nature of the chosen project and whether or not this project is being done by one or more people; this should be settled with the course instructor. Ideally, the submitted project should be on the same topic as that described in your project proposal. However, it being an imperfect world, if any difficulties do arise, chat with your course instructor as soon as possible so appropriate action, e.g., revision of stated goals and/or scope of project, can be taken.

  If course enrollment is low enough (see the course outline), each project will also have an associated short in-class presentation scheduled in the last two weeks of course lectures. Details of talk format and scheduling will be posted in early November after project proposals are submitted and marked.

  Here's to each of you choosing and carrying out a fun course project!

Thursday, September 11 (Lecture #2) (FS)
[Class Notes]

• The Characteristics of Natural Language: Why Bother?
  • Natural language is the area of study of linguistics. We focus here on descriptive linguistics (which studies the languages actually spoken by people) as opposed to prescriptive linguistics (which enforces particular standards of language).
  • Example: My Fair Lady (1964) [excerpt]
  • Looking at what linguists have to say about the characteristics of natural language is very valuable in an NLP course for two reasons:
    1. Linguists have studied many languages and hence have described and proposed mechanisms for handling phenomena that may lie outside those handled by existing NLP systems (many of which have been developed to only handle English).
    2. Linguists have studied the full range of natural processes, from sound perception to meaning, in some cases for centuries (~2500 and 1300 years, respectively, in the case of Sanskrit and Arabic linguists), and have had insights that may be invaluable in mitigating known problems with existing NLP systems, e.g., Marcus and Davis (2019, 2021).
• The Characteristics of Natural Language: Overview
  • General model of language processing (adapted from BKL, Figure 1.5):

    

    • "A LangAct" is an utterance in spoken or signed communication or a sentence in written communication.
    • The topmost left-to-right tier encodes language recognition and the right-to-left tier immediately below encodes language production.
    • The knowledge required to perform each step (all of which must be acquired by a human individual to use language) is the third tier, and the lowest is the area or areas of linguistics devoted to each type of knowledge.
    • Three language-related processes are thus encoded in this diagram: recognition and production (explicitly) and acquisition (implicitly).
  • Whether one is modeling actual human language or implementing language abilities in machines, the mechanisms underlying each of language recognition, production, and acquisition must be able to both (1) handle actual human language inputs and outputs and (2) operate in a computationally efficient manner.
    • As we will see over the duration of this course, the need to satisfy both of these criteria is one of major explanations for how research has proceeded (and diverged) in Strong and Weak NLP.
• The Characteristics of Natural Language: Phonetics (J&M, Section 7)
  • Phonetics is the study of the actual sounds produced in human languages (phones), both from the perspectives of how they are produced by the human vocal apparatus (articulatory phonetics) and how they are characterized as sound waves (acoustic phonetics).
    • Acoustic phonetics is particularly important in artificial speech analysis and synthesis.
  • In many languages, the way words are written does not correspond to the way sounds are pronounced in those words, e.g., the sound corresponding to the letter "t" is pronounced differently in each of the words "toucan", "starfish", "kitten", and "butter" (see below). Hence, another way has to be used to describe the sounds people actually produce in speech.
  • The most common way of representing phones is to use special sound-alphabets, e.g., International Phonetic Alphabet (IPA) [charts], ARPAbet [Wikipedia] (J&M, Table 7.1).
    • By convention, symbols denoting phones are written in square brackets, e.g., [b], [t].
    • Symbols in these alphabets may be modified by diacritics indicating more specific features of individual sounds, e.g., aspiration or palatalization, or the utterances in which these sounds occur, e.g., primary and secondary stress, utterance intonation.
  • Another way of representing phones uses phonetic features based on how sounds are articulated in the human vocal tract, e.g.,
    • consonants, e.g., [p], [d], [g]:
      • voicing (unvoiced / voiced), e.g., [p] / [b]
      • place of articulation, e.g., bi-labial ([p]) / labio-dental ([f]) / alveolar ([t]) / velar [k] / glottal ([?])
      • manner of articulation, e.g., plosive ([t]) / nasal ([m]) / fricative ([s]) / affricate (plosive + fricative) [ks]) / tap)
    • vowels, e.g., [a], [e], [i], [o], [u]:
      • height
      • "width" (front / back)
      • roundedness (rounded / unrounded)
  • Each language has its own characteristic repertoire of sounds, and no natural language (let alone English) uses the full range of possible sounds.
  • Example: Xhosa tongue twisters (clicks)
  • Even within a language, sounds can vary depending on their context, due to constraints on the way articulators can move in the vocal tract when progressing between adjacent sounds (both within and between words) in an utterance.
    • Variation in pronouncing [t] (J&M, Table 7.9):
      • aspirated (in initial position), e.g., "toucan"
      • unaspirated (after [s]), e.g., "starfish"
      • glottal stop (after vowel and before [n], e.g., "kitten"
      • tap (between vowels), e.g., "butter"
    • word-final [t]/[d] palatalization (J&M, Table 7.10), e.g., "set your", "not yet", "did you"
    • Word-final [t]/[d] deletion (J&M, Table 7.10) e.g., "find him", "and we", "draft the"
  • Variation in sounds can also depend on a variety of other factors, e.g., rate of speech, word frequency, speaker's state of mind / gender / class / geographical location (J&M, Section 7.3.3).
  • As if all this wasn't bad enough, it is often very difficult to isolate individual sounds and words from acoustic speech signals

Tuesday, September 16 (Lecture #3) (FS)
[Class Notes]

• The Characteristics of Natural Language: Phonology (Bird (2010)) (Youtube)
  • Phonology is the study of the systematic and allowable ways in which sounds are realized and can occur together in human languages.
  • Each language has its own set of semantically-indistinguishable sound-variants, e.g., [pat] and [p^hat] are the same word in English but different words in Hindi.
    • The semantically-indistinguishable variants of a sound in a language are a phoneme in that language.
    • By convention, symbols denoting phonemes are surrounded by right slashes, e.g., /b/, /t/.
    • To continue the example above, [p] and [p^h] are part of phoneme /p/ in English but are separate phonemes /p/ and /p^h/ in Hindi.
    • By definition, phonemes are both abstractions of phones and language-specific.
  • Variation in how phonemes are realized as phones is often systematic, e.g., formation of plurals in English:

    mop	mops	[s]
    pot	pots	[s]
    pick	picks	[s]
    kiss	kisses	[(e)s]
    mob	mobs	[z]
    pod	pods	[z]
    pig	pigs	[z]
    pita	pitas	[z]
    razz	razzes	[(e)z]

    Note that the phonetic form of the plural-morpheme /s/ is a function of the last sound (and in particular, the voicing of the last sound) in the word being pluralized. A similar voicing of /s/ often (but not always) occurs between vowels, e.g., "Stasi" vs. "Streisand".

  • Such systematicity may involve non-adjacent sounds, e.g., vowel harmony in the formation of plurals in Turkish (Kenstowicz (1994), p. 25):

    dal	dallar	``branch''
    kol	kollar	``arm''
    kul	kullar	``slave''
    yel	yeller	``wind''
    dis	disler	``tooth''
    g"ul	g"uller	``race''

    The form of the vowel in the plural-morpheme /lar/ is a function of the vowel in the word being pluralized.

  • It is tempting to think that such variation is encoded in the lexicon, such that each possible form of a word and its pronunciation are stored. However, such variation is typically productive wrt new words (e.g., nonsense words, loanwords), which suggests that variation is instead the result of processes that transform abstract underlying lexical forms to concrete surface pronounced forms.
    • Plural of nonsense words in English, e.g., blicket / blickets, farg / fargs, klis / klisses.
    • Unlimited concatenated morpheme vowel Harmony in Turkish (Sproat (1992), p. 44):
      c"opl"uklerimizdekilerdenmiydi =>
      c"op + l"uk + ler + imiz + de + ki + ler + den + mi + y + di
      ``was it from those that were in our garbage cans?''

      In Turkish, complete utterances can consist of a single word in which the subject of the utterance is a root-morpheme (in this case, [c"op], "garbage") and all other (usually syntactic, in languages like English) relations are indicated by suffix-morphemes. As noted above, the vowels in the suffix morphemes are all subject to vowel harmony. Given the in principle unbounded number of possible word-utterance in Turkish, it is impossible to store them (let alone their versions as modified by vowel harmony) in a lexicon.

    • Variation in English [r] according Cantonese phonology in Chinenglish (Demers and Farmer (1991), Exercise 3.10):
      • [r] deletion (before consonant or final sound in word), e.g., "tart", "party", "guitar", "bar", "sergeant" (see also Boston English)
      • [r] pronounced as [l] (before a vowel), e.g. "strawberry","brandy", "aspirin", "Listerine", "curry".

      These rules can also hold when a Cantonese speaker writes English text, e.g., "Phone Let Kloss."

    • Modification of English loanwords in Japanese (Lovins (1973)):

      dosutoru	``duster''
      sutoroberri`	`strawberry''
      kurippaa`	`clippers''
      sutoraiki	``strike''
      katsuretsu	``cutlet''
      parusu	``pulse''
      gurafu	``graph''

      Japanese has a single phoneme /r/ for the liquid-phones [l] and [r]; moreover, it also allows only very restricted types of multi-consonant clusters. Hence, when words that violate these constraints are borrowed from another language, those words are changed by the modification to [r] or deletion of [l] and the insertion of vowels to break up invalid multi-consonant clusters.

  • There are also similar systematicities in allowable syllable structures as well as the placement of word stress, e.g., English penultimate ([ma + ri' + a]) vs. Polish antepenultimate ([ma' + ri + a]) word-stress. Such matters are the province of metrical phonology.
  • Each language has its own phonology, which consists of the phonemes of that language, constraints on allowable sequences of phonemes (phonotactics), and descriptions of how phonemes are instantiated as phones in particular contexts.
    • As shown by the examples above, the systematicities within a language's phonology must be consistent with (but are by no means limited to those dictated solely by) vocal-tract articulator physics, e.g., consonant clusters in Japanese.
  • Courtesy of underlying phonological representations and processes, one is never sure if an observed phonetic representation corresponds directly to the underlying representation or is some process-mediated modification of that representation, e.g., we are never sure if an observed phone corresponds to an "identical" phoneme in the underlying representation. This introduces one type of ambiguity into natural language processing.
• The Characteristics of Natural Language: Morphology (Trost (2003); Sproat (1992), Chapter 2)
  • Morphology is the study of the systematic and allowable ways in which symbol-string/meaning pieces are organized into words in human languages.
  • A symbol-string/meaning-piece is called a morpheme.
    • Two broad classes of morphemes: roots and affixes.
    • A root is a morpheme that can exist alone as word or is the meaning-core of a word, e.g., tree (noun), walk (verb), bright (adjective).
    • An affix is a morpheme that cannot exist independently as a word, and only appears in language as part of word, e.g., -s (plural), -ed (past tense; 3rd person), -ness (nominalizer).
  • A word is essentially a root combined with zero or more affixes. Depending on the type of root, the affixes perform particular functions, e.g., affixes mark plurals in nouns and subject number and tense in verbs in English.
  • Morphemes are language-specific and are stored in a language's lexicon. The morphology of a language consists of a lexicon and a specification of how morphemes are combined to form words (morphotactics).
  • Morpheme order typically matters, e.g., uncommonly, commonunly*, unlycommon* (English)
  • There are a number of ways in which roots and affixes can be combined in human languages (Trost (2003), Sections 2.4.2 and 2.4.3):
    • Prefix: An affix attached to the front of the root, e.g.,, the negative marker un- for adjectives in English (uncommon, infeasible, immature).
    • Suffix: An affix attached to the back of the root, e.g.,, the plural marker -s for nouns in English (pots, pods, dishes).
    • Circumfix: A prefix-suffix pair that must both attach to the root, e.g.,, the past participle marker ge-/-t for verbs in German (gesagt "said", gelaufen "ran").
    • Infix: An affix inserted at a specific position in a root, e.g., the -um- verbalizer for nouns and adjectives in Bontoc (Philippines):

      /fikas/	"strong"	/fumikas/	"to be strong"
      /kilad/	"red"	/kumilad/	"to be red"
      /fusl/	"enemy"	/fumusl/	"to be an enemy"

    • Template Infix: An affix consisting of a sequence of elements that are inserted at specific positions into a root (root-and-template morphology), e.g., active and passive markers -a-a- and -u-i- for the root ktb ("write") in Arabic:

      katab	kutib	"to write"
      kattab	kuttib	"cause to write"
      ka:tab	ku:tib	"correspond"
      taka:tab	tuku:tib	"write each other"

    • Reduplication: An affix consisting of a whole or partial copy of the root that can be prefix, infix, or suffix to the root, e.g., formation of the habitual-repetitive in Javanese:

      /adus/	"take a bath"	/odasadus/
      /bali/	"return"	/bolabali/
      /bozen/	"tired of"	/bozanbozen/
      /dolan/	"recreate"	/dolandolen/

      (MEANINGFUL WHISPER: Do you see anything that makes reduplication qualitatively different from all other phonological and morphological processes that we have considered here? (Hint: a^n b^n => ww))

  • As with phonological variation, there are several lines of evidence which suggest that morphological variation is not purely stored in the lexicon but rather the result of processes operating on underlying forms:
    • Productive morphological combination simulating complete utterances in words, e.g., Turkish example above.
    • Morphology operating over new words in a language, e.g., blicket -> blickets, television -> televise -> televised / televising, barbacoa (Spanish) -> barbecue (English) -> barbecues.
  • As if all this didn't make things difficult enough, different morphemes need not have different surface forms, e.g, variants of "book"
    "Where is my book?" (noun)
    "I will book our vacation." (verb: to arrange)
    "He doth book no argument in this matter, Milord." (verb: to tolerate)

  • Courtesy of phonological transformations operating both within and between morphemes and the non-uniqueness of surface forms noted above, one is never sure if an observed surface representation corresponds directly to the underlying representation or is a modification of that representation, e.g., is [blints] the plural of "blint" or does it refer to a traditional Jewish cheese-stuffed pancake? This introduces another type of ambiguity into natural language processing.

Thursday, September 18 (Lecture #4) (FS)
[Class Notes]

• The Characteristics of Natural Language: Syntax (BKL, Section 8; J&M, Chapter 12; Kaplan (2003))
  • Syntax is the study of the systematic and allowable ways in which words are organized into utterances (spoken) and sentences (written) in human languages.
  • Two fundamental facts of natural language syntax (J&M, pp. 385-386):
    • constituency: a group of one or more (most often, adjacent) words may behave as a single unit called a constituent, e.g., "fox", "dog", "jumped", "the quick brown fox", "the lazy dog", and "jumped over the lazy dog" are constituents in the utterance "the quick brown fox jumped over the lazy dog".
    • grammatical relations: constituents relate in systematic manners to other constituents in a utterance, e.g. "the quick brown fox" and "the lazy dog" are the subject and object, respectively, in the utterance "The quick brown fox jumped over the lazy dog".

  • Constituents typically have associated grammatical classes whose members may have different structures but perform equivalent grammatical functions, e.g., noun phrase, determiner, verb phrase.
    • Analogous to the manner in which phonemes are built up from phones, constituents are grouped into grammatical classes based on whether or not the members can be substituted for each other to create grammatical utterances, e.g., Given that "the quick brown fox", "an airplane", "John", "Alice from the second house down the lane", and "the man who Liberty Valence" can all be substituted for X in the utterance "X jumped over the lazy dog" to create grammatical (if somewhat puzzling) utterances, all are examples of a common constituent class (in this case, noun phrases).
    • There are typically multiple hierarchical levels of constituents in an utterance, e.g.,
      

      "[[the [quick [brown [fox]]]] [jumped over [the [lazy [dog]]]]]".

  • Grammatical relations can express what constituents can co-occur in an utterance (subcategorization) or the semantic relationships between constituents (dependency).
    • Some languages encode grammatical relations primarily by word order, e.g., "John visited Mary" (English); others primarily use morphology, e.g., "John-ga Mary-o tazune-ta", "Mary-o John-ga tazune-ta" (Japanese) (Kaplan (2003), p. 71).
    • Even in languages that primarily use word order and have equivalent grammatical classes, orders of grammatical classes may differ across languages, e.g, each of the six possible orderings of subject, object, and verb in basic transitive-verb utterances occur in at least one human language. though the frequencies of these orders vary greatly (Tomlin (1986), p. 22):

      SOV	"She him loves."	45%	Pashto, Latin, Japanese, Afrikaans
      SVO	"She loves him."	42%	English, Hausa, Mandarin, Russian
      VSO	"Loves she him."	9%	Hebrew, Irish, Zapotec, Tuareg
      VOS	"Loves him she."	3%	Malagasy, Baure
      OVS	"Him loves she."	1%	Apalai, Hixkaryana
      OSV	"Him she loves."	< 1%	Warao

    • Grammatical relations can hold over arbitrary distances in a utterances, e.g., "The man who knew the solder that killed the sailor who sailed as first mate on the S.S. Warsaw and visited my ex-sister-in-law Louise's best friend in Paris last month died." (garden-path utterances)
    • Grammatical relations may even be recursively embedded, e.g., "The cat the dog the rat the elephant admired bit chased likes tuna fish." (J&M, p. 536)

      (MEANINGFUL WHISPER: Is such embedding of constituents qualitatively different from other syntactic patterns considered above? (Hint: a^n b^n))

  • Syntax is language-specific. Building on a language's morphology, the syntax is a specification called a grammar of how words are combined to form utterances in that language.
    • Languages such Japanese and Turkish (see above) that use word-internal morphology to a greater degree than word order to encode grammatical relations and dependencies are said to have a morphosyntax.
  • Analogous to phonological and morphological variation, the fact that syntax operates productively to generate a potentially infinite number of utterances over a finite lexicon suggests that syntactic patterns are not purely stored in the grammar but are rather the result of grammatical processes operating on underlying forms.
  • As if all this didn't make things difficult enough, utterances expressing very different meanings need not have different surface forms, e.g,
    "Is your refrigerator running?"
    "Put the block in the box on the table."
    "This morning I shot an elephant in my pajamas."
    

    Hence, ambiguity inherent in grammars and lexicons adds yet another type of ambiguity into natural language processing (BKL, pp. 317-318).

• The Characteristics of Natural Language: Semantics, Discourse, and Pragmatics (Lappin (2003); Leech and Weisser (2003); Ramsay (2003))
  • Semantics is the study of the manner in which meaning is associated with utterances in human language; discourse and pragmatics focus, respectively, on how meaning is maintained and modified over the course of multi-person dialogues and how these people chose different individual-utterance and dialogue styles to communicate effectively.
  • Meaning seems to be very closely related to syntactic structure in individual utterances; however, the meaning of an utterance can vary dramatically depending on the spatio-temporal nature of the discourse and the goals of the communicators, e.g., "It's cold outside." (statement of fact spoken in Hawaii; statement of fact spoken on the International Space Station; implicit order to close window).
  • Various mechanisms are used to maintain and direct focus within an ongoing discourse (Ramsay (2003), Section 6.4):
    • Different syntactic variants with subtly different meanings, e.g., "Ralph stole my bike" vs "My bike was stolen by Ralph".
    • Different utterance intonation-emphasis, e.g., "I didn't steal your bike" vs "I didn't steal your BIKE" vs "I didn't steal YOUR bike" vs "I didn't STEAL your bike".
    • Syntactic variants which presuppose a particular premise, e.g., "How long have you been beating your wife?"
    • Syntactic variants which imply something by not explicitly mentioning it, e.g., "Some people left the party at midnight" (-> and some of them didn't), "I believe that she loves me" (-> but I'm not sure that she does).
  • Another mechanism for structuring discourse is to use references (anaphora) to previously discussed entities (Mitkov (2003a)).
    • There are many kinds of anaphora (Mitkov (2003a), Section 14.1.2):
      • Pronominal anaphora, e.g., "A knee jerked between Ralph's legs and he fell sideways busying himself with his pain as the fight rolled over him."
      • Adverb anaphora, e.g., "We shall go to McDonald's and meet you there."
      • Zero anaphora, e.g., "Amy looked at her test score but was disappointed with the results."
      • Nominal anaphora (direct), e.g., "Keane plays football for Manchester United. Irishman Keane has three years left in his current contract."
      • Nominal anaphora (indirect), e.g., "Although the store had just opened, the food hall was full and customers were lined up at the cash registers."
    • Though a convenient conversational shorthand, anaphora can be (if not carefully used) ambiguous, e.g.,
      "The man stared at the male wolf. He salivated at the thought of his next meal."
      "Place part A on Assembly B. Slide it to the right."
      "Put the doohickey by the whatchamacallit over there."
      

  • As demonstrated above, utterance meaning depends not only the individual utterances, but on the context in which those utterance occur (including knowledge of both the past utterances in a dialogue and the possibly unknown and dynamic goals and knowledge of all participants in the discourse), which adds yet another layer of ambiguity into natural language processing ...
    • That being said, there is also an enormous amount of redundancy in natural language communication that allows interpretation of partial signals, e.g., noisy channels, signal corruption.
    • Example: Not the Nine O'Clock News (1980): Abou Ben Adhem (Link)
• It seems then that natural language, by virtue of its structure and use, encodes both a lot of ambiguity and variation, as well as a wide variety of grammatical structures at all levels.
  • The amount and type of ambiguity and variation that must be accommodated by mechanisms in a natural language processing system varies depending on the goals of the system:
    • If the system must operate fluently on unstructured input relative to unstructured conversational domains, every form of ambiguity and variation mentioned above must be dealt with.
    • If the system must operate only relative to a restricted set of conversational forms and topics, e.g., a telephone-accessed airline flight status information system (especially one that asks questions in a structured manner to control user inputs), the amount of ambiguity (and to a degree variation) at the discourse, syntax, and morphological levels can be dramatically restricted.
    • If the system in addition operates relative to a single known user relative to which that system can be trained, e.g., an on-line personal assistant, the amount of ambiguity at the phonological and phonetic levels (as well as variation at all levels) can also be dramatically restricted.
  • The types of grammatical structures that must be accommodated by mechanisms in a natural language processing system varies depending on the goals of the system:
    • If the goal is to operate fluently within an economically dominant language, e.g., English, Mandarin, Arabic, Hindi, then one can focus on mechanisms tailored specifically to the types of structures in that language (though to achieve fluent communication, extra attention will have to be paid to fine-grained structure within that language).
    • If the goal is to help preserve languages that have less economic dominance or are rapidly dying out ("rescue linguistics"), e.g., Danish, Manx, Warao, Apalai, then one requires mechanisms that can handle many types of structure (though less attention may be required to fine-grained structure within that language, especially in the case of time-constrained rescue linguistics).
• In any case, there is a final set of computational characteristics of natural language that must be either accommodated (in the case by strong NLP systems) or circumvented by clever means (in the case of narrow NLP systems).
• The Characteristics of Natural Language: Natural Language Operation and Acquisition
  • Human beings (both adults and children) use language effectively with the aid of finite and ultimately limited computational devices, e.g., our brains.
  • Utterances are generated and comprehended relatively quickly in most everyday situations, cf., bad telephone connections active construction sites.
  • Generation and performance acquisition degrades more or less gracefully with the increasing complexity and length of utterances.
  • Example: Prototypical natural language acquisition device
  • Given exposure to a human language, any child can acquire the phonological, morphological, and semantic (if not total lexical) knowledge of that language within four to seven years.
    • This exposure does not need to be simplified, cf., Motherese.
    • This exposure does not need to be comprehensive or exhaustive, with many examples of each possible phenomena in the language.
    • Individual utterances in this exposure need not be either grammatical or have their grammaticality-status stated.
    • Produced utterances by the child need not be assessed for grammaticality or corrected.
  • Given exposure to any human language, any human being can acquire that language, and children under the age of 10 years are superbly good at this. In addition:
    • If children are exposed to two distinct language simultaneously, they will acquire both languages, i.e., they will become bilingual.
    • If children are exposed to a pidgin created by combining elements of two or more languages, they will regularize the unsystematic parts of the pidgin to create a proper hybrid language (creole).

Tuesday, September 23 (Lecture #5) (FS)
[Nederhof (1996); Class Notes]

• Given all the characteristics of natural language discussed in the previous lectures and their explicit and implied constraints on what an NLP system must do, what then are appropriate computational mechanisms for implementing NLP systems? It is appropriate to consider first what linguists, the folk who have been studying natural language for the longest time, have to say on this matter.
• NLP Mechanisms: The View from Linguistics
  • Given that linguistic signals are expressed as temporal (acoustic and signed speech) and spatial (written sequences) sequences of elements, there must be a way of representing such sequences.
    • Sequence elements can be atomic (e.g., symbols) or have their own internal structure (e.g., feature matrices, form-meaning bundles (morphemes)); for simplicity, assume for now that elements are symbols.
    • There are at least two types of such sequences representing underlying and surface forms.
    • Where necessary, hierarchical levels of structure such as syntactic parse trees can be encoded as sequences by using appropriate interpolated and nested brackets, e.g., "[[the quick brown fox] [[jumped over] [the lazy brown dog]]]"
  • The existence of lexicons implies mechanisms for representing sets of element-sequences, as well as accessing and modifying the members of those sets.
  • The various processes operating between underlying and surface forms presuppose mechanisms implementing those processes.
    • Two broad classes of linguistic process-systems:
      • Rule-based: Individual processes are rules that specify transformations of one form to another form, e.g., add voice to the noun-final plural morpheme /s/ if the last sound in the noun is voiced.
      • Constraint-based: Individual processes are constraints that specify valid structures in surface and underlying forms, e.g., the voicing of the surface form of the noun-final plural morpheme must match the voicing of the final sound in the noun being pluralized.
    • In rule-based systems, rules are applied in a specified order to transform an underlying form to its associated surface form for utterance production, and in reverse fashion to transform a surface form to its associated underlying form(s) for utterance comprehension (ambiguity creating the possibility of multiple such associated forms).
    • In constraint-based systems, constraints are applied simultaneously to an underlying (surface) form to create associated composite surface-underlying form(s) in the case of utterance generation (comprehension).
    • In both types of systems, the processes being implemented can be viewed as functions. Given the various types of ambiguity we have seen, these functions are at least one-many. Moreover, each type of process (e.g., phonology, morphology, syntax, semantics) can be seen as separate functions that are applied consecutively.
      • Natural language can also be seen as a single function that is the composition of these individual functions. This is the view taken by many neural network implementations of NLP (which will be discussed later in the course).
      • Great care must be taken in establishing what parameters are necessary as input to these functions and that such parameters are available. For example, a syntax function can get by with a morphological analysis of an utterance, but a semantics function would seem to require as input not only possible syntactic analyses of an utterance but also discourse context and models of discourse participant knowledge and intentions.
  • Following practice in linguistics, we can assume that all natural language processes operate in a deterministic fashion. However, given the complexity of proposed processes and how they may interact, it may be useful as an intermediate stage in analyzing linguistic complexity to allow mechanisms that operate probabilistically, e.g., rules that have a specified probability of application, composed systems of rules that rank one-many outputs by their probability of occurrence.
    • This is analogous to the use of statistical mechanics to summarize and analyze the overall behavior of large groups of particles in physics.
    • Such mechanisms may be analysis end-points in themselves if it turns out that either the interaction of deterministic linguistic processes is too complex to untangle or there are genuinely probabilistic processes underlying natural language processing in humans.
    • Beware of over-simplification for the sake of engineering convenience and equating the model with the phenomena, e.g., complex deterministic one-many -> simplified probabilistic one-many -> simplified probabilistic one-one / most probable (the last of which is what neural-network-based NLP systems do).
• NLP Mechanisms: Finite-state grammars, automata, and transducers
  • Regular (finite-state) Grammars (HU79, Section 9.1; J&M, Section 2.2; Martin-Vide (2003), Section 8.2.4)
    • Originated in the Linguistics community; proposed by Chomsky in the 1950s as the lowest level of the Chomsky Hierarchy of grammars (Regular / Context-Free (Phrase Structure) / Context-Sensitive / Unrestricted).
    • Basic terminology: (production) rule, terminal, non-terminal, rule application, termination.
      • Rules are restricted such that left-hand side is a single non-terminal and the right-hand side is of length at least one and consists of zero or more terminal followed by at most one non-terminal.
      • Without loss of generality, we will focus on regular grammars with at most one terminal on the right-hand side.
    • Operation: generation / recognition of strings
      • Generation builds a string from left to right, adding symbols to the right-hand end of the string as one expands non-terminal symbols by the application of rules.
      • Recognition steps through a string from left to right, successively refining the initial S-symbol into a right-linear syntactic tree that effectively delete symbols as rules are applied.
      • Note that one need only keep track of one non-terminal symbol during both operations described above, namely, the last non-terminal generated / recognized.
    • Example: A regular grammar for the set of all strings over the alphabet {a,b} that consist of one or more concatenated copies of ab.

      S -> aA
      A -> bS
      A -> b
      

    • Example: A regular grammar for the set of all strings over the alphabet {a,b} that start with an a and end with a b (Version I).

      S -> aC
      C -> aC
      C -> bC
      C -> b
      

    • Example: A regular grammar for the set of all strings over the alphabet {a,b} that start with an a and end with a b (Version II).

      S -> aC
      C -> aC
      C -> bC
      C -> E
      E -> b
      

    • Example: A regular grammar for the set of all strings over the alphabet {a,b} that start with an a and end with a b (Version III).

      S -> aA
      A -> aA
      A -> bB
      A -> b
      B -> aA
      B -> bB
      B -> b
      

    • Example: A regular grammar implementing the constraint that the voicing of the surface form of the noun-final plural morpheme must match the voicing of the final sound in the noun being pluralized.

      S -> {*vcd}V
      S -> {*unvcd}U
      V -> {*vcd}V
      V -> {*unvcd}U
      V -> {P}z
      U -> {*vcd}V
      U -> {*unvcd}U
      U -> {P}s
      

Thursday, September 25 (Lecture #6) (FS)
[Nederhof (1996); Class Notes]

• NLP Mechanisms: Finite-state grammars, automata, and transducers (Cont'd)
  • Finite-state automata (FSA) (Martin-Vide (2003), Section 8.3.1; Nederhof (1996); Roche and Schabes (1997a), Section 1.2)
    • Originated in the Engineering community; inspired by the discrete finite neuron model proposed by McCullough and Pitts in 1943.
    • Basic Terminology: (start / finish) state, (symbol-labeled) transition, acceptance.
    • Operation: generation / recognition of strings
      • Generation builds a string from left to right, adding symbols to the right-hand end of the string as one progresses along a transition-path from the start state to a final state.
      • Recognition steps through a string from left to right, deleting symbols from the left-hand end of the string as one progresses along a transition-path from the start state to a final state.
      • Note that one need only keep track of one FSA-state during both operations described above, namely, the last state visited.
    • Example #1: A DFA for the set of all strings over the alphabet {a,b} that consist of one or more concatenated copies of ab.

      

    • Types of FSA:
      • Deterministic (DFA): At each state and for each symbol in the alphabet, there is at most one transition from that state labeled with that symbol.
      • Non-Deterministic (NFA): At each state, there may be more than one transition from that state labeled with a particular symbol and/or there may be transitions labeled with special symbol epsilon.
        • Revised notion of string acceptance: see if there is any path through the NFA that accepts the input string.
    • Example #2: An NFA for the set of all strings over the alphabet {a,b} that start with an a and end with a b (uses multiple same-label outward transitions).

      

    • DFA can recognize strings in time linear in the length of the input string, but may not be compact; NFA are compact but may require time exponential in the length of a string to recognize that string (need to follow all possible computational paths to check string acceptance).
    • Example #1: An NFA for the set of all strings over the alphabet {a,b} that start with an a and end with a b (uses epsilon-transitions).

      

    • Example #2: A DFA for the set of all strings over the alphabet {a,b} that start with an a and end with a b.

      

    • Example #3: A DFA implementing the constraint that the voicing of the noun-final plural morpheme must match the voicing of the final sound in the noun being pluralized.

      

    • Oddly enough, deterministic and non-deterministic FSA are equivalent in recognition power, i.e., there is a DFA for a particular set of strings iff there is an NFA for that set of strings.
      • Determinization algorithm (HMU01, Section 2.5.5)
        • Creates DFA from a |Q|-state NFA in O(|Q|^3 * 2^{|Q|}) time and O(2^{|Q|}) space.
        • DFA produced by this algorithm can be exponentially larger (in terms of the number of states) than the input NFA (HMU01, Section 2.3.6).
      • Minimization algorithm (HU79, pp. 67-71)
        • Creates minimal DFA from a |Q|-state DFA operating over alphabet Sigma in O(|Sigma||Q|^2) time; this is, however, potentially still exponential time if the input DFA was created by the determinization algorithm above.
        • This algorithm cannot be used to minimize NFA; indeed, there does not appear to be a subexponential time and space algorithm for minimizing NFA (HMU01, p. 163).
  • Regular grammars and finite-state automata are equivalent in recognition power, i.e, there is a DFA for a particular set of strings iff there is a regular grammar for that set of strings (HMU01, Section 4.3.1).
  • There is actually another notation, regular expressions, which is also equivalent in recognition power to regular grammars and finite-state automata.
    • A regular expression is essentially a way of expressing the left-to-right structure of each string in a set of strings in a linear fashion.
    • Example: A regular expression for the set of all strings over the alphabet {a,b} that consist of one or more concatenated copies of ab is (ab)^+, cf., (ab)^*.
    • Example: A regular expression for the set of all strings over the alphabet {a,b} that start with an a and end with a b is a(a|b)^*b.
  • Given the focus on defining and combining groups of simple to complex processes at the level of phonology and morphology and the structure of the lexicon in morphology, NLP applications use finite-state automata rather than regular grammars.
    • Regular expressions are frequently used to describe simple FSA, especially when these FSA are used as inputs to software packages, e.g., xFST (Beesley and Karttunen (2003)); however, they are not suited to describing the complex composite FSA created by combining multiple FSA in NLP applications.
• Regular grammars and finite-state automata encode sets of strings, and are hence good for encoding simple lexicons or simple (one-level) constraint-processes (more on this in the next lectures). However, how do we encode the relations or functions between pairs of strings in rule-process functions encoded in rule- processes or complex (two-level) constraint-processes?
• Finite-state transducers (FST) (J&M, Section 3.4, Mohri (1997); Roche and Schabes (1997a), Section 1.3)
  • Generalization of FSA in which each transition is labeled with a symbol-pair (either or both of which may be the special symbol epsilon).
    • The first symbol in each pair is called the lower symbol and the second is called the upper symbol.
    • The alphabet of all lower-symbols in an FST need not have a non-empty intersection with the alphabet of all upper-symbols in an FST.
  • Example #4: An FST for transforming between the set of all strings over the alphabet {a,b} that consist of l, l >= 0, concatenated copies of ab and the set of all strings over the alphabet {c,d} that consist of l, l >= 0, concatenated copies of cd.

    

  • Operation: generation / recognition of string-pairs, reconstruction of upper (lower) string associated with given lower (upper) string.
    • Generation of a string-pair builds that pair from left to right, adding symbol-pairs to the right-hand end of the string-pair as one progresses along a transition-path from the start state to a final state.
    • Recognition of a string-pair proceeds by stepping through that pair from left to right, deleting symbol-pairs from the left-hand end of the string-pair as one progresses along a transition-path from the start state to a final state.
    • Reconstruction of a string-pair associated with a given string builds the missing string of the pair from left to right, adding missing-string symbols to the right-hand end of the missing string as one progresses along a transition-path from the start state to a final state in accordance with the given string.
      • As the given string may be either the lower or upper string, there are two types of string-pair reconstructions.
      • Each reconstructed string-pair corresponds to a particular path through the FST guided by the given string.
      • Depending on the structure of the FST, there may be more than one path through the FST consistent with the given string, and hence more than one string-pair reconstruction.
    • Note that one need only keep track of one FST-state during all operations described above, namely, the last state visited.
  • Unlike FSA, there are many types of FST and many types of determinism; for each such type, there are different determinization and minimization algorithms (Kaplan and Kay (1994); Mohri (1997), 2004; Roche and Schabes (1997a), Section 1.3).
    • The most basic type of deterministic is an l/u-deterministic FST, such that for each state q in the FST and each lower/upper symbol-pair x/y, there is at most one transition outwards from q with label x/y.
  • Example #5: An FST for transforming between the set of all strings over the alphabet {a,b} that consist of l, l >= 0, concatenated copies of ab and the set of all strings over the alphabet {a,b} that consist of l, l >= 0, concatenated copies of aba.

    

  • In NLP applications, there is no standard association of lower and upper forms with more surface or more lexical forms -- it all depends on which direction you have formulated the rules as operating in. For example, in the following two examples (and in indeed all natural-language-based FST applications in this course (including notes, assignments, and exams)), the rules are stated in terms of transforming lexical into surface forms, which implies that the lower forms are lexical and the upper forms are surface.
  • Example #6: An FST implementing the rule that voice be added to the noun-final plural morpheme /s/ if the last sound in the noun is voiced.

    

  • Example #7: An FST implementing the rule that (1) voice be added to the noun-final plural morpheme /s/ if the last sound in the noun is voiced and (2) an extra vowel be added before the plural morpheme if the last sound in the noun is a fricative ([s],[z],[sh],[zh]), e.g., passes, dishes, buzzes.

References

• Abney, S.P. (1996) "Partial parsing via finite-state cascades." Natural Language Engineering, 2(4), 337-344.
• BBC News (2014) "Translation tech helps firms talk business round the world." (URL: Retrieved November 14, 2014)
• Baker, J.M., Deng, L., Glass, J., Khuanpur, S., Lee, C.-H., Morgan, N., and O'Shaughnessy, D. (2009a) "Research Developments and Directions in Speech Recognition and Understanding, Part 1." IEEE Signal Processing Magazine, 26(3), 75-80.
• Baker, J.M., Deng, L., Khuanpur, S., Lee, C.-H., Glass, J., Morgan, N., and O'Shaughnessy, D. (2009b) "Research Developments and Directions in Speech Recognition and Understanding, Part 2." IEEE Signal Processing Magazine, 26(6), 78-85.
• Barton, G.E., Berwick, R.C., and Ristad, E.S. (1987) Computational Complexity and Natural Language. MIT Press.
• Beesley, K.R. and and Karttunen, L. (2000) "Finite-state Non-concatenative Morphotactics." In SIGPHON 2000. 1-12. [PDF]
• Beesley, K.R. and and Karttunen, L. (2003) Finite-State Morphology. CSLI Publications.
• Bird, S. (2003) "Phonology." In R. Mitkov (ed.) (2003), pp. 3-24.
• Bird, S., Klein, E., and Loper, E. (2009) Natural Language Processing with Python. O'Reilly Media. [Abbreviated above as BKL]
• Carpenter, B. (2003) "Complexity." In R. Mitkov (ed.) (2003), pp. 178-200.
• Carroll, J. (2003) "Parsing." In R. Mitkov (ed.) (2003), pp. 233-248.
• Clark, A. and Lappin, S. (2011) Linguistic Nativism and the Poverty of the Stimulus. Blackwell.
• Colby, K.M. (1981) "Modeling a paranoid mind." Behavioral and Brain Sciences, 4(4), 515-534.
• Cusumano, M.A. (2025) "DeepSeek Inside: Origins, Technology, and Impact." Communications of the ACM, 68(7), 18-22. (PDF)
• Daciuk, J. (2002) "Comparison of Construction Algorithms for Minimal Acyclic, Deterministic, Finite-State Automata from Sets of Strings." In CIAA 2002. Lecture Notes in Computer Science no. 2608. Springer-Verlag; Berlin. 255-261. [PDF]
• Daciuk, J., Mihov, S., Watson, B.W., and Watson, R.E. (2000) "Incremental Construction of Acyclic Finite-State Automata." Computational Linguistics, 26(1), 3-16.
• Damerau, F.J. (1964) "A Technique for Computer Detection and Correction of Spelling Errors." Communications of the ACM, 7(3), 171-176.
• Demers, R.A. and Farmer, A.K. (1991) A Linguistic Workbook (2nd Edition). The MIT Press.
• Denning, P.J. (2023) "The Smallness of Large Language Models." Communications of the ACM, 66(9), 24-27. [Text]
• Du, M.W. and Chang, S.C. (1992) "A model and a fast algorithm for multiple errors spelling correction." Acta Informatica, 29, 281-302.
• Duffy, C. and Uzquiano, K. (2023) "Bot or not? How to tell when you're reading something written by AI." CNN. [Link]
• Dupont, P., Denis, F., and Esposito, Y. (2005) "Links between probabilistic automata and hidden Markov models: probability distributions, learning models, and induction algorithms." Pattern Recognition, 38, 1349-1371.
• Dutoit, T. and Stylianou, Y. (2003) "Text-to-Speech Synthesis." In R. Mitkov (ed.) (2003), pp. 323-338.
• Edwards, C. (2021) "The best of NLP." Communications of the ACM, 64(4), 9-11. [Text]
• Epstein, R. (2007) From Russia With Love: How I got fooled (and somewhat humiliated) by a computer." Scientific American Mind, October, 6-17.
• Eisenstein, J. (2019) Introduction to Natural Language Processing. The MIT Press.
• Gazdar, G. and Pullum, G.K. (1985) "Computationally Relevant Properties of Natural Languages and Their Grammars." Next Generation Computing, 3, 273-306. [PDF]
• Grana, J., Barcala, M., and Alonso, M.A. (2001) "Compilation Methods of Minimal Acyclic Finite-State Automata for Large Dictionaries." In CIAA 2001. Lecture Notes in Computer Science no. 2494. Springer-Verlag; Berlin. 135-148. [PDF]
• Greengard, S. (2023) "Computational Linguistics Finds Its Voice." Communications of the ACM, 66(2), 18-20. [Text]
• Greengard, S. (2023) "Distilling What We Know." Communications of the ACM, 66(9), 15-17. [Text]
• Grishman, R. (2003) "Information Extraction." In R. Mitkov (ed.) (2003), pp. 545-559
• Guest, O., Suarez, M., Muller, B.C.N., van Meerkerk, E., Beverborg, A.O.G., de Haan, R., Elizondo, A.R., Blokpoel, M., Scharfenberg, N., Kleinherenbrink, A., Camerino, I., Woensdregt, M., Monett, D., Brown, J., Avraamidou, L., Alenda-Demoutiez, J., Hermans, F., and van Rooij, I. (2025) "Against the Uncritical Adoption of 'AI' Technologies in Academia." Preprint. (PDF)
• Harabagiou, S. and Moldovan, D. (2003) "Question Answering." In R. Mitkov (ed.) (2003), pp. 560-582
• Hopcroft, J.E., Motwani, R., and Ullman, J.D. (2001) Introduction to Automata Theory, Languages, and Computation (Second Edition). Addison-Wesley. [Abbreviated above as HMU01]
• Hopcroft, J.E. and Ullman, J.D. (1979) Introduction to Automata Theory, Languages, and Computation. Addison-Wesley. [Abbreviated above as HU79]
• Hutchins, J. (2003) "Machine Translation: General Overview." In R. Mitkov (ed.) (2003), pp. 501-511.
• Indurkhya, N. and Damerau, F.J. (eds.) (2010) Handbook of Natural Language Processing (2nd Edition). Chapman and Hall / CRC.
• Jurafsky, D. and Martin, J.H. (2008) Speech and Natural Language Processing (2nd Edition). Prentice-Hall. [Abbreviated above as J&M]
• Jurafsky, D. and Martin, J.H. (2023) Speech and Natural Language Processing (3rd Edition). (Book Website) [Abbreviated above as J&M2]
• Kaplan, R. (2003) "Syntax." In R. Mitkov (ed.) (2003), pp. 70-90.
• Kaplan, R and Kay, M. (1994) "Regular Models of Phonological Rule Systems." Computational Linguistics, 20(3), 331-378. [PDF]
• Kaplan, R. and Kay, M. (1996) "Finite-state Methods in Natural Language Processing: Algorithms." Lecture notes. [PDF]
• Kari, L., Konstantinidis, S., Perron, S., Wozniak, G., and Xu, J. (2003) "Finite-state error edit-systems and difference measures for languages and words." Technical report 2003-01, Department of Mathematics and Computing Science, Saint Mary's University, Canada.
• Kay, M. (2003) "Introduction." In R. Mitkov (ed.) (2003), pp. xvii-xx.
• Kedia, A, and Rasu, M. (2020) Hands-On Python Natural Language Processing. Packt Publishing; Birmingham, UK.
• Kenstowicz, M.J. (1994) Phonology in Generative Grammar. Basil Blackwell.
• Kiraz, G.A. (2000) "Multi-tiered nonlinear morphology using multitape finite automata: A case study on Syriac and Arabic." Computational Linguistics, 26(1), 77-105. [PDF]
• Kruskal, J.B. (1984) "An Overview of Sequence Comparison." In D. Sankoff and J.B. Kruskal (eds.) Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison. Addison-Wesley; Reading, MA. 1-44.
• Lamel, L. and Gauvin, J.-L. R. (2003) "Speech Recognition." In R. Mitkov (ed.) (2003), pp. 305-322.
• Lappin, S. (2003) "Semantics." In R. Mitkov (ed.) (2003), pp. 91-111.
• Leech, G. and Weisser, M. (2003) "Pragmatics and Dialogue." In R. Mitkov (ed.) (2003), pp. 136-156.
• Li, H. (2022) "Language models: past, present, and future." Communications of the ACM, 65(7), 56-63. (HTML)
• Lovins, J.B. (1973) Loanwords and the Phonological Structure of Japanese. PhD thesis, University of Chicago.
• Lucchesi, C.L. and Kowaltowski, T. (1993) "Applications of finite automata representing large vocabularies." Software - Practice and Experience, 23(1), 15-20. [PDF]
• Manning, C. and Schutze, H. (1999) Foundations of Statistical Natural Language Processing. The MIT Press. [Abbreviated above as M&S]
• Marcus, G. and Davis, E. (2019) Rebooting AI: Building Artificial Intelligence We Can Trust. Pantheon Books; New York.
• Marcus, G. and Davis, E. (2021) "Insights for AI from the Human Mind", Communications of the ACM, 64(1), 38-41. [Text]
• Martin-Vide, C. (2003) "Formal Grammars and Languages." In R. Mitkov (ed.) (2003), pp. 157-177.
• Mihov, S. and Maurel, D. (2000) "Direct Construction of Minimal Acyclic Subsequential Transducers." In CIAA 2000. Lecture Notes in Computer Science no. 2088. Springer-Verlag; Berlin. 217-229.
• Mihov, S. and Schulz, K.U.. (2004) "Fast Approximate Search in Large Dictionaries." Computational Linguistics, 30(4), 451-477.
• Mitkov, R. (ed.) (2003) The Oxford Handbook of Computational Linguistics. Oxford University Press.
• Mitkov, R. (2003a) "Anaphora Resolution." In R. Mitkov (ed.) (2003), pp. 266-283.
• Mohri, M. (1996) "On some applications of finite-state automata theory to natural language processing." Natural Language Engineering, 2(1), 61-80.
• Mohri, M. (1997) "Finite-state transducers in language and speech processing." Computational Linguistics, 23(2), 269-311. [PDF]
• Mohri, M. (2004) "Weighted Finite-State Transducer Algorithms: An Overview." In Formal Languages and Applications. Studies in Fuzziness and Soft Computing no. 148. Physica-Verlag; Berlin. 551-564. [PDF]
• Mohri, M., Pereira, F., and Riley, M. (2000) "The Design Principles of a Weighted Finite-State Transducer Library." Theoretical Computer Science, 231, 17-32. [PDF]
• Mohri, M., Pereira, F., and Riley, M. (2002) "Weighted Finite-State Transducers in Speech Recognition." Computer Speech & Language, 16(1), 69-88. [PDF]
• Myers, E.W. and Miller, W. (1989) "Approximate Matching of Regular Expressions." Bulletin of Mathematical Biology, 51, 5-37.
• Nederhof, M.-J. (1996) "Introduction to Finite-State Techniques." Lecture notes. [PDF]
• Nederhof, M.-J. (2000) "Practical Experiments with Regular Approximation of Context-Free Languages." Computational Linguistics, 26(1), 17-44. [PDF]
• Oflazer, K. (1996) "Error-Tolerant Finite-State Recognition with Applications to Morphological Analysis and Spelling Correction." Computational Linguistics, 22(1), 73-89.
• Pereira, F. and Riley, M. (1997) "Speech Recognition by Composition of Weighted Finite-State Automata." In E. Roche and Y. Schabes (eds.) (1997), pp. 431-454.
• Ramsay, A. (2003) "Discourse." In R. Mitkov (ed.) (2003), pp. 112-135.
• Rao, D. and McMahan, B. (2019) Natural Language Processing with PyTorch: Build Intelligent Language Applications Using Deep Learning. O'Reilly; Boston, MA.
• Reis, E. S. D., Costa, C. A. D., Silveira, D. E. D., Bavaresco, R. S., Righi, R. D. R., Barbosa, J. L. V., and Federizzi, G. (2021) "Transformers aftermath: current research and rising trends." Communications of the ACM, 64(4), 154-163. [Text]
• Robson, D. (2023) ``Why we personify threatening events.'' BBC Future [Link]
• Roche, E. and Schabes, Y. (eds.) (1997) Finite-state Natural Language Processing. The MIT Press.
• Roche, E. and Schabes, Y. (1997a) "Introduction." In E. Roche and Y. Schabes (Eds.) (1997), pp. 1-66.
• Savary, A. (2002) "Typographical Nearest-Neighbor Search in a Finite-State Lexicon and Its Application to Spelling Correction." In CIAA 2002. Lecture Notes in Computer Science no. 2494. Springer-Verlag; Berlin. 251-260.
• Schmidhuber, J. (2015) "Deep learning in neural networks: An overview." Neural Networks, 61, 85-117.
• Somers, H. (2003) "Machine Translation: Latest Developments." In R. Mitkov (ed.) (2003), pp. 512-528.
• Sproat, R. (1992) Morphology and Computation. The MIT Press.
• Tellman, Z. (2023) "Designing a Framework for Conversational Interfaces." Communications of the ACM, 66(10), 44-7. [Text]
• Tomlin, R. (1986) Basic Word Order: Functional Principles. Croom Helm.
• Trost, H. (2003) "Morphology." In R. Mitkov (ed.) (2003), pp. 25-47.
• Tzoukermann, E., Klavans, J.L., and Strazalkowski, T. (2003) "Information Retrieval." In R. Mitkov (ed.) (2003), pp. 529-544.
• Vajjala, S., Majumder, B., Gupta, A., and Surana, H. (2019) Practical Natural Language Processing: A Comprehensive Guide to Building Real-world NLP Systems. O'Reilly; Boston, MA.
• Vidal, E., Thollard, F., Higuera, C., Casacuberta, F., and Carrasco, R.C. (2005a) "Probabilistic Finite-State Machines -- Part I." IEEE Transactions on Pattern Analysis and Machine Intelligence, 237(7), 1013-1025.
• Vidal, E., Thollard, F., Higuera, C., Casacuberta, F., and Carrasco, R.C. (2005b) "Probabilistic Finite-State Machines -- Part II." IEEE Transactions on Pattern Analysis and Machine Intelligence, 237(7), 1026-1039.
• Wareham, T. (1999) Systematic Parameterized Complexity Analysis in Computational Phonology. PhD thesis, Department of Computer Science, University of Victoria.
• Wareham, T. (2001) "The Parameterized Complexity of Intersection and Composition Operations on Sets of Finite-State Automata." In CIAA 2000. Lecture Notes in Computer Science no. 2088. Springer-Verlag; Berlin. 302-310. [PDF]
• Weizenbaum, J. (1966) "ELIZA - A computer program for the study of natural language communication between man and machine." Communications of the ACM, 9(1), 36-45.
• Weizenbaum, J. (1967) "Contextual understanding by computers." Communications of the ACM, 10(8), 474-480.
• Weizenbaum, J. (1979) Computer Power and Human Reason. W.H. Freeman.
• Yang, Y. and Piantadosi, S.T. (2022) "One model for the learning of language." Proceedings of the National Academy of Sciences 119(5), e2021865119 (12 pages).

Created: July 11, 2025
Last Modified: September 17, 2025