UTCS Colloquium: Gerard Huet/INRIA Paris-Rocquencourt:"Relational Programming," TAY 3.128, Monday, October 12, 2009, 3:00 p.m.
Sign-up schedule for this speaker is at http://www.cs.utexas
Type of Talk: UTCS Colloquium
Speaker/Affiliation: Gerard Huet/INR
Date/Time: Monday, October 12, 2009, 3:00 p.
Location: TAY 3.128
Host: Jayadev Misra
tle: "Relational Programming"
sent in this talk a new paradigm for relational programming, using a conce
pt of "Effective Eilenberg Machines". Eilenberg machines were d
efined 35 years ago by Samuel Eilenberg as a generalisation of finite state
automata, which has not so far attracted the attention we think it rightl
y deserves. An Eilenberg machine consists in two components. Its control co
mponent is similar to a non-deterministic finite state automaton, whose tr
ansitions are labeled with symbols from a set of action generators. Its com
putation component consists in a semantic attachment of actions generators
to binary relations over some data domain. These relations are effectively
presented as algorithms mapping a data value to a lazily computed stream of
related data values. Such machines are doubly non-deterministic, and may
be simulated by a sequential reactive engine which completely explores the
state space. Various meta-theoretic properties lead to a variety of explora
tion strategies. For instance, an important family of Finite Eilenberg Mac
hines enjoy an efficient simulation by
a purely iterative bottom-up se
arch. Effective Eilenberg Machines define a characteristic relation over th
eir data domain, which may be
used as semantic assignment for higher-
level machines, leading to a concept of composition of modular machines. A
high level language extending regular expressions permits the applicative
description of the control component, compiling into finite-state automata
. An equational semantics axiomatizes the machine actions within V. Pratt''
s action algebras, an equational variety which is a conservative extension
of Kleene algebras. This conceptual apparatus has been developed as joint
research with Benoît Razet.
In a second part of the talk
, we present applications of this methodology to computational linguistics.
The Zen toolkit provides i
an OCaml library of inductive data structu
res and applicative algorithms, allowing concise and efficient implementat
ion of lexicons, morpho-phonemic transformations, and shallow parsers. An
application to a Sanskrit segmenting tagger will be demonstrated.
Gerard Huet is a Director of Research at INRIA Paris-R
research interests span a broad range: logic, comput
algorithmics, formal methods, programming languages,
engineering, linguistics engineering, knowledge engineerin
applications of computers in humanities, arts, social sciences a
life sciences. He has been involved in such ground-breaking work as
the development of the Caml functional programming language, the
Coq proof assistant, and the Zen toolkit for finite-state computation.
He has won many awards, among them: Herbrand award, Honorary do
by Chalmers University in Göteborg and the the EATCS Awa
- Awards & Honors
- About Us
- Student Engagement and Support
- Masters Program
- Ph.D. Program
- Financial Information
- Prospective Students
- Incoming Students
- Current Students
- Curricular Practical Training
- Grad Student Talks
- UTCS Direct