PULC Course

(This page is under construction)

The purpose of the course is to give tools that can be used to construct a computer system that can solve logic puzzles from their textual description. 

Course pre-conditions:

  • A course on discrete mathematics
  • A course on data structures and algorithms
  • A course on automata theory and formal languages
  • A course on object oriented programming
  • A course on logic (such as: mathematical logic, logic for computer science)
  • Not required but good background: a course on compilers, a course on artificial intelligence


  • Each student will write lecture notes for part of a lecture.
  • Groups of 2 students will either program an additional component in the open-source system, or analyze a linguistic phenomenon and enhance the system’s knowledge (in various levels) to handle that phenomenon.


  1. Introduction: The field of Natural Language Processing, “shallow” vs. “deep” processing, comprehension tasks, overview of what’s needed for a logic puzzle solver, overview of a collaborative open-source system
  2. Tokenization, segmentation, parts of speech, morphological processing, brief mention of part of speech taggers
  3. Syntactic analysis, tree-structures and feature-structures, syntactic theories (Chomskian, HPSG, LFG), syntactic processing using a chart parser
  4. Syntactic phenomena, including: agreement, gaps, relative clauses, …, ellipsis
  5. Brief review / overview of logic, logical languages, logical semantics, model theory, proof theory, the lambda calculus, type theory
  6. A meaning representation language for natural languages – handling various phenomena (individuals, relations, quantifiers, events, collectives, time)
  7. Calculating meaning representations from syntactic analyses: Montague grammar, scope ambiguity and various proposals (quasi-logical forms, MRS, hole semantics), and Glue Semantics, an algorithm for calculating meaning representations using Glue Semantics
  8. Management of ambiguities: the problem of early statistical choice, packed representations, the Free-Choice Space methodology, applications to morphology, syntax, semantics
  9. Advanced syntactic/semantic phenomena (representation and computation): anaphora, comparatives, same/different, reciprocals
  10. Using automated reasoning (theorem prover, model builder) to calculate results, and using a finite constraint-satisfaction solver. Considering presuppositions and implicatures.
  11. Lexical semantics, ontology, and world knowledge, temporal and spacial reasoning
  12. Buffer for adding details that were skipped for lack of time
  13. 5-minute presentation by each group about their work
  14. Addressing implementation issues and questions. Further topics as time allows

See also: 2011 Workshop