• In Moodle: Programming with Haskell
• Bitte um Zeitangaben! Doodle-Poll bis Freitag ausfüllen bitte!

We continued to discuss Haskell implementation. We also discussed the linguistic relevance of computational linguistics.

a handout (with compiling code) | examples (and code)

We discussed Haskell implementation issues.

a (slightly revised) handout

We dug deeper into differences between models regarding their ability to derive languages with crossing dependencies, and identified various empirical data that would decide between our models.

Question

do copies have a simpler internal syntax than do non-copies? (Kanazawa & Salvati, 2010)

i.e. can we enforce nested dependencies inside of copies? if so, the MTT model cannot generate such copies. if not, this is a stunning verification of a deep prediction of the MTT model.

Question

can you have recursive copying? (Kobele, 2006)

i.e. can you have copies contained in copies (contained in copies)? if so, the MBUTT model cannot generate such copies. If not, this is a verification of a deep prediction of the MBUTT/MTT models.

Question

can you have non-exact copying?

i.e. can you copy structure, without copying words? if so, the non-linear transducer model cannot generate such copies. If not, this is a verification of a deep prediction of the MBUTT/MTT models.

We spoke about the generative capacity of these various kinds of tree transducers. In particular, we discussed crossing dependencies in natural language (Swiss German, Mandarin Chinese), and identified the copy language as a simplified model of a pattern that requires some way of enforcing crossing dependencies to derive. We discussed how to derive the copy language using

• mbutts (tuples of trees)
• mtts (tree contexts)
• minimalist grammars (movement)
• non-linear tree transducers (copying)

We discussed interpreting input subtrees as tree contexts to model the yield function. We considered how these transducer models were different instantiations of the same formalism.

a (preliminary) handout

We discussed how to model movement using tuples of trees as the interpretations of input subtrees. We introduced a simple form of Minimalist grammar, and showed how to transduce from derivation to derived trees.

background on minimalist grammars: Stabler (1997) Derivational Minimalism

We discussed tree homomorphisms, and tree transducers. We introduced tree contexts as the translations of nodes.

We discussed top down and bottom up tree automata.

an exceptional reference: TATA

No Class

No Class

We described various subclasses of functions computable in our models

• ISL
  • each state is just a letter, representing the last input read
    • all arcs reading a letter go to the appropriately named state
  • generalization to last k inputs read
    • each state is a sequence of (up to) k letters
    • in state (a,b,c) reading d go to (b,c,d)
• L/R-OSL
  • each state is a letter, representing the last output written
  • can generalize to last k outputs written
• weakly deterministic
  • composition of a left with a right sequential transducer with the same alphabets
  • definition:
    • no additional letters can use additional letters to encode contextual information
    • no length increase can encode additional letters using multiple old letters!

Sour grapes harmony is a supposedly pathological phenomenon which can be described in OT, but is (presumably) not weakly deterministic.

We discussed transducer composition using an example from Lomongo. We discussed progressive and regressive processes in natural language, noting that regressive harmony processes could not be described using our model, which operates from left-to-right. We showed that it could be described by our model, were it to operate from right-to-left.

Edit <2019-01-17 Thu>

Here are some pointers to the literature on sequential transducers:

• Choffrut (2001) Minimizing Subsequential Transducers: A survey
• Akram, de la Higuera, Eckert (2012) Actively Learning Probabilistic Subsequential Transducers
  • Akram's (2012) TUM Dissertation on Learning Probabilistic Subsequential Transducers
• 'Lothaire' (2004) Applied Combinatorics on Words (pp 43 - 50)
• Chandlee, Eyraud, Heinz (2014) Learning Strictly Local Subsequential Functions
• Chandlee, Heinz (2012) Bounded Copying is Subsequential
• Chandlee, Heinz, Jardine (2018) Input strictly local opaque maps

Edit <2019-01-14 Mon>

I have modified the DFST module, and the model language project, so as to implement a distinction between left-to-right and right-to-left transductions at the type level. The only effect this has for you is that you need to create transducers using the functions mkForwardTransducer and mkBackwardTransducer.

We discussed how to formalize transducers. Here is another model language project, this time using transducers.

Dfst module | code

Special class session run by Max Polter

We motivated studying processes in various domains of linguistics. We looked at an example from the Bantu language Lomongo, where various processes (nonlow vowels gliding before vowels, the first vowel in a sequence of two vowels deletes, and inter-vocalic voiced consonant deletion) interact to derive the surface forms.

We discussed adding output to our finite automata, and did some exercises in class.

No Class (Dies Akademicus)

We discussed a model language project.

Dfsa module | code

We discussed using the Maybe data type to represent partiality, and defined a function which completed a partial DFA.

We discussed the cross-product construction.

No Class (Vorlesungsfrei)

We showed how to implement finite state automata in Haskell.

notes | code

We introduced finite state automata formally.

We introduced finite state automata informally with examples, as machines which listen to one word at a time, possibly changing their memory state in response.

We discussed how Haskell determines whether expressions are well-typed (and if so, what type they have). We also explored user-defined types, both using the type keyword for defining abbreviations for types we can already express, and using the data keyword, for new data types.

Today we discussed polymorphism, and type class constraints.

No Class (Reformationstag)

We talked about types in Haskell (Int, Char, String) as well as certain type constructors (->, ,). We defined functions over trees in a recursive manner.

Today we discussed function composition, and observed that functions over a set had a monoidal structure (with respect to composition and the identity function). We also explored two formalizations of trees.

notes

Today we went over the homework, and explored an alternative, inductive, definition of strings.

notes

Today we went over familiar set theoretic notions, before presenting formal descriptions of strings.

notes

notes