(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
Requirements:
- 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.
Syllabus:
- 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
- Tokenization, segmentation, parts of speech, morphological processing, brief mention of part of speech taggers
- Syntactic analysis, tree-structures and feature-structures, syntactic theories (Chomskian, HPSG, LFG), syntactic processing using a chart parser
- Syntactic phenomena, including: agreement, gaps, relative clauses, …, ellipsis
- Brief review / overview of logic, logical languages, logical semantics, model theory, proof theory, the lambda calculus, type theory
- A meaning representation language for natural languages – handling various phenomena (individuals, relations, quantifiers, events, collectives, time)
- 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
- Management of ambiguities: the problem of early statistical choice, packed representations, the Free-Choice Space methodology, applications to morphology, syntax, semantics
- Advanced syntactic/semantic phenomena (representation and computation): anaphora, comparatives, same/different, reciprocals
- Using automated reasoning (theorem prover, model builder) to calculate results, and using a finite constraint-satisfaction solver. Considering presuppositions and implicatures.
- Lexical semantics, ontology, and world knowledge, temporal and spacial reasoning
- Buffer for adding details that were skipped for lack of time
- 5-minute presentation by each group about their work
- Addressing implementation issues and questions. Further topics as time allows
See also: 2011 Workshop