- Up -
Next >>
Table of Contents
Table of Contents
1 Finite State Automata
1.1 Finite State Recognizers and Generators
1.1.1 A Simple Machine that can laugh
1.1.2 Finite State Automata
1.2 Some Examples
1.3 Deterministic vs. Non-deterministic FSAs
1.4 FSAs in Prolog
1.4.1 Representing FSAs in Prolog
1.4.2 A Recognizer and Generator for FSAs without Jump Arcs
1.4.3 A Recognizer and Generator for FSAs with Jump Arcs
1.5 Finite State Methods in Computational Linguistics and their Limitations
1.6 The Prolog Files
1.7 Practical Session
1.8 Exercises and Solutions
1.8.1 Exercises
1.9 Further Reading
2 Finite State Parsers and Transducers
2.1 Building Structure while Recognizing
2.1.1 Finite State Parsers
2.1.2 An Example
2.1.3 Separating out the Lexicon
2.2 Finite State Transducers
2.2.1 What are Finite State Transducers?
2.2.2 FSTs in Prolog
2.3 An Application: Morphology
2.3.1 Morphology
2.3.2 Morphological Parsing
2.3.3 From the Surface to the Intermediate Form
2.3.4 From the Intermediate Form to the Morphological Structure
2.3.5 Combining the two Transducers
2.3.6 Putting it in Prolog
2.3.7 Further Reading
2.4 The Complete Programs
2.5 Practical Session
2.6 Exercises
3 Regular Languages
3.1 Regular Languages and Relations
3.1.1 FSAs, Regular Expressions, and Regular Languages
3.1.2 Examples of Regular Expressions
3.1.3 Definition of Regular Expressions
3.1.4 Regular Expressions and FSAs
3.1.5 From Regular Expressions to FSAs
3.1.6 Regular Relations and Rewriting Rules
3.2 Properties of Regular Languages
3.2.1 Concatenation, Kleene Closure and Union
3.2.2 Intersection, Complementation
3.2.3 The ``Pumping Lemma''
3.3 Implementing Operations on FSAs
3.3.1 The
scan
-Predicate
3.3.2 Implementation of
scan/1
3.3.3
scan_state/2
3.3.4 Recursion
3.3.5 Intersection
3.3.6 Union
3.4 The Complete Code
3.5 Practical Session
3.6 Exercises
3.7 Further Reading
4 Finite State Technologies for Dialogue Processing
4.1 Dialogue Processing
4.1.1 Introduction
4.1.2 General Dialogue characteristics
4.1.3 General Dialogue characteristics: Examples
4.2 FSA-based dialogue systems
4.2.1 Processing dialogue with finite state systems
4.2.2 A simple FSA example
4.2.3 Extending FSA
4.2.4 Grounding extension
Grounding Extension 1
Grounding Extension 2
Grounding Extension 3
And what about Repair?
4.3 An in-depth look at the speaking elevator
4.3.1 The Saarbrücken CL department's Speaking Elevator
4.3.2 How does the dialogue progress?
4.3.3 An additional memory
4.3.4 How long does the system wait for a response?
4.3.5 How does the elevator deal with unrecognised utterances or inconsistent input?
4.3.6 And what happens if the elevator does understand the input?
4.3.7 How is the user input confirmed?
4.3.8 During the trip...
4.3.9 What happens when there is ambiguous input?
4.3.10 Speaking elevator reference
4.4 Examples of required behaviour
4.4.1 Turn-taking
4.4.2 Adjacency pairs and insertions
4.4.3 Grounding
4.4.4 Dialogue context
4.4.5 Ellipsis
4.4.6 Reference resolution
4.4.7 Mixed initiative
4.5 Dialogue characteristic and extension of the elevator
4.5.1 Turn-taking
4.5.2 Adjacency pairs and insertions
4.5.3 Grounding
4.5.4 Dialogue context
4.5.5 Ellipsis
4.5.6 Reference resolution
4.5.7 Mixed initiative
4.6 Summary and Outlook
4.6.1 Advantages and disadvantages
4.6.2 The CSLU tool
4.6.3 Beyond finite state techniques
4.7 Exercises
5 Context Free Grammars
5.1 Context Free Grammars
5.1.1 The Basics
5.1.2 The Tree Admissibility Interpretation
5.1.3 A Little Grammar of English
5.2 DCGs
5.2.1 DCGs are a natural notation for context free grammars
5.2.2 DCGs are really Syntactic Sugar for Difference Lists
5.2.3 DCGs give us a Natural Notation for Features
5.3 DCGs for Long Distance Dependencies
5.3.1 Relative Clauses
5.3.2 A First DCG
5.3.3 A Second DCG
5.3.4 Gap Threading
5.3.5 Questions
5.3.6 Occurs-Check
5.4 Pros and Cons of DCGs
5.5 The Complete Code
5.6 Exercises
6 Parsing: Bottom-Up and Top-Down
6.1 Bottom-Up Parsing and Recognition
6.2 Bottom-Up Recognition in Prolog
6.3 An Example Run
6.4 How Well Have we Done?
6.4.1 Implementation
6.4.2 Algorithmic Problems
6.4.3 [Sidetrack] Using a Chart
6.5 Top Down Parsing and Recognition
6.5.1 The General Idea
6.5.2 With Depth-First Search
6.5.3 With Breadth-First Search
6.6 Top Down Recognition in Prolog
6.6.1 The Code
6.6.2 A Quick Evaluation
6.7 Top Down Parsing in Prolog
6.8 The Code
6.9 Practical Session
6.9.1 Bottom Up
6.9.2 Top Down
6.10 Exercises
6.10.1 Bottom-Up
6.10.2 Top-Down
6.10.3 Midterm Project
7 Left-Corner Parsing
7.1 Introduction Left-Corner Parsing
7.1.1 Going Wrong with Top-down Parsing
7.1.2 Going Wrong with Bottom-up Parsing
7.1.3 Combining Top-down and Bottom-up Information
7.2 A Left-Corner Recognizer in Prolog
7.3 Using Left-corner Tables
7.4 The Code
7.5 Practical Session
7.6 Exercises
8 Passive Chart Parsing
8.1 Motivation
8.2 A Bottom-Up Recognizer Using a Passive Chart
8.2.1 An Example
8.2.2 Being Complete
8.3 Some Prolog Revision
8.3.1 Database manipulation
8.3.2 Failure Driven Loops
8.4 Passive Chart Recognition in Prolog
8.4.1 Representing the Chart
8.4.2 The Algorithm
8.4.3 An Example
8.5 The Code
8.6 Exercise
9 Active Chart Parsing
9.1 Active Edges
9.2 The Fundamental Rule
9.3 Using an Agenda
9.4 A General Algorithm for Active Chart Parsing
9.5 Bottom-up Active Chart Parsing
9.5.1 An Example
9.5.2 An Example (continued)
9.5.3 Putting it into Prolog
findall/3
Representing the Arcs
Bottom Up Active Chart Recognition
Bottom Up Active Chart Recognition (continued)
9.6 The Code
9.7 Top-Down Active Chart Parsing
9.7.1 Top-down rule selection
9.7.2 Initializing Chart and Agenda
9.7.3 An Example
9.8 Exercise
10 Semantic Construction
10.1 Introduction
10.2 First-Order Logic: Basic Concepts
10.2.1 Vocabularies
10.2.2 First-Order Languages
10.2.3 Building Formulas
10.2.4 Bound and Free Variables
10.2.5 Notation
10.2.6 Representing formulas in Prolog
10.3 Building Meaning Representations
10.3.1 Being Systematic
10.3.2 Being Systematic (II)
10.3.3 Three Tasks
10.3.4 From Syntax to Semantics
10.4 The Lambda Calculus
10.4.1 Lambda-Abstraction
10.4.2 Reducing Complex Expressions
10.4.3 Using Lambdas
10.4.4 Advanced Topics: Proper Names and Transitive Verbs
10.4.5 The Moral
10.4.6 What's next
10.4.7 [Sidetrack:] Accidental Bindings
10.4.8 [Sidetrack:] Alpha-Conversion
10.5 Implementing Lambda Calculus
10.5.1 Representations
10.5.2 Extending the DCG
10.5.3 The Lexicon
10.5.4 A First Run
10.5.5 Beta-Conversion
10.5.6 Beta-Conversion Continued
10.5.7 Running the Program
10.6 Exercises
Code Index
Bibliography
Index
- Up -
Next >>
Kristina Striegnitz
,
Patrick Blackburn
,
Katrin Erk
,
Stephan Walter
,
Aljoscha Burchardt
and
Dimitra Tsovaltzi
Version 1.2.5 (20030212)