Following the tradition, the first day of TAG+11 will be devoted to several tutorials, including:
Synchronous context-free grammars (CFGs), first proposed in the 1960s, have become a popular and powerful tool in machine translation, semantic parsing, and other areas of natural language processing. Synchronous tree-adjoining grammars (TAGs) were first proposed in the 1990s and are starting to see interesting applications. The theory behind synchronous grammars, and the algorithms that power their applications, are sometimes natural extensions of those of conventional grammars, but there are also some surprising twists and turns. I will give an introduction to synchronous CFGs and TAGs, present some of their key formal properties, and describe the main algorithms that use them. I will also describe some synchronous grammar formalisms beyond synchronous TAG, like synchronous hyperedge replacement grammars.
Tree-Adjoining Grammars from a psycholinguistic perspective
We will first review some psycholinguistic experiments that are revealing about certain properties of human language comprehension, such as to what degree sentence processing is incremental and possibly even connected, as well as studies that indicate that humans actively predict upcoming input. We will thereby cover syntactic as well as semantic and discourse-level effects. In the second part of the tutorial, I will discuss how these effects can be modelled using Tree-Adjoining Grammars.
LCFRS+: Linear Context-Free Rewriting Systems and Related Formalisms
Recently, there has been an increased interest in Linear Context-Free Rewriting Systems (LCFRSs), due to their mild context-sensitivitiy and their capacity to describe discontinuous constituents and non-projective dependencies. LCFRS research has particularly intensified in the area of parsing.
In this tutorial, LCFRSs will be motivated and introduced. Furthermore, closely related formalisms such as Multiple Context-Free Grammars (MCFG) and simple Range Concatentation Grammars (RCG) will be defined and related to LCFRS. The link between LCFRS and the notion of mild context-sensitivity will be discussed and, in this context, the question whether one might even want to go beyond LCFRS will be raised. The more powerful formalisms of (unrestricted) RCG and Literal Movement Grammars (LMG) will be introduced that both are natural extensions of LCFRS, depending on whether the LCFRS rules are understood as manipulating strings or manipulating concrete occurrences of substrings of some input string. The former leads to LMG while the latter leads to RCG.
The aim of the tutorial is to give an overview of the formal grammar landscape ranging from CFG to LCFRS, RCG and LMG, relating the different types of rewriting rules and the different language classes defined by these formalisms. The expressive power and the limitations of these grammars are illustrated by numerous examples.
Trees abound: A primer on tree automata and tree transducers
We introduce tree automata and tree transducers formally and on examples. We also link them to the (synchronous) grammar notions that are better known in NLP. We then proceed to review most of the basic tree automata and tree transducer results with tie-ins into current results obtained in the NLP community. Finally, we cover some interesting advanced results that so far received little interest from the NLP community.