CTL310s2008: Kurssin kuvaus (myös WebOodissa)

Kohderyhmä: The course is targeted for students who are interested in the intersection of formal language theory and natural language processing, or advanced issues in finite-state methodology.

Ajoitus: The course is intended for advanced / graduate level studies but a student with a sufficient background in formal methods can take the course earlier.

Edeltävät opinnot: The student has to have some familiarity with formal grammars, finite-state automata or transducers, predicate logic and stringology. The student has to have an ability to write regular expressions and simple algorithms using formal languages.

Tavoite: The intended learning outcome (ILO) of this course is that the student is able to synthesize regular expressions and predicate logic and use their combination critically when addressing various problems in automata based natural language processing.

Sisältö: The course is based on the teacher's recent research on non-classical regular operations and their applications in computational linguistics and computer science. We proceed as follows:

  1. Regular expressions, finite automata and monadic second order logic
  2. First-order logic and star-free regular expressions, predicate logic with substring variables
  3. Implications, rules and generalized restriction (GR)
  4. Closure properties and complexities of GR
  5. Contextual rules and other applications of GR
  6. Language generation with the framework
  7. Bracketed GR-based rules and grammar systems

We will jump from regular expressions and first-order variables for string positions to the Generalized Restriction (GR) framework (Yli-Jyrä 2007) that lends itself for compiling various rules and grammars into transducers. The structure of the framework will be presented both through regular expressions with logic-based extensions and first-order predicate logics with regular-expression based extensions. In connection to the framework, its main applications, open research problems and probable further extensions are discussed during the course.

The GR framework is useful in capturing the semantics of many formalisms previously used in finite-state processing and in presenting new, more general formalisms that involve complex and discontinuous contexts. The framework is computationally attractive alternative for defining * phonological and morphological grammars * context-free and non-context-free parsing * machine learning and language generation.

Oppimateriaali ja kirjallisuus:

  • A selection of articles on the connection between logic and regular expressions, as well as on approaches to contextual rules and formalisms.
  • Yli-Jyrä, A. (2007). Applications of Diamonded Double Negation. In post-proceedings of FSMNLP 2007.

Opetustavat: The teacher will give interactive lectures on fundamental and tricky areas. The students will study the material and present at least two times quick summaries, applications and reflections on some selected reading. The students participate into critical discussions during the course.

Suoritustavat: The student will write a reflective essay on an application of generalized restriction and present it during the course. Each student will listen critically and comment on one of some other student's presentations that as been designated earlier.

Arviointi: 0-5. The assessment is based on the intended learning outcomes.

Vastuuhenkilö: Anssi Yli-Jyrä


  • Shared basis of concepts
  • logiikan ja transduktorien yhteys
  • GR:n sovellukset ja tehokkuus

AnssiYliJyra - 2008-10-31
Topic revision: r3 - 2009-02-08 - AnssiYliJyra
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2018 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback