Sign-up schedule for this speaker is at http://www.cs.utexas

.edu/department/webevent/utcs/events/cgi/list_events.cgi

Type of Talk: UTCS Colloquium

Speaker/Affiliation: Gerard Huet/INR

IA Paris-Rocquencourt

Date/Time: Monday, October 12, 2009, 3:00 p.

m.

Location: TAY  3.128

Host: Jayadev Misra

Talk Ti

tle: "Relational Programming"

Talk Abstract:

We pre

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.

Speaker Bio:
Gerard Huet is a Director of Research at INRIA Paris-R

ocquencourt. His
research interests span a broad range: logic, comput

ation theory,
algorithmics, formal methods, programming languages,
software
engineering, linguistics engineering, knowledge engineerin

g,
applications of computers in humanities, arts, social sciences a

nd
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

rd.