LSV Seminar
The LSV seminar takes place on Tuesday at 11:00 AM. The usual location is the conference room at Pavillon des Jardins (venue). If you wish to be informed by e-mail about upcoming seminars, please contact Stéphane Le Roux and Matthias Fuegger.
The seminar is open to public and does not require any form of registration.
Past Seminars
Regular graphs: a perfect model for infinite state systems?
- Date
- Tuesday, February 10 2009 at 11:00AM
- Place
- Salle de Conférence (Pavillon des Jardins)
- Speaker
- Christophe Morvan (Université de Marne-la-Vallée, France)
There are dozens of models for infinite state systems. Indeed, Turing machine,
cellular automata, pushdown systems, Petri nets, or process algebras are only
major examples of such systems.
Most of these systems do not provide the simplicity and efficiency of finite
state systems. Finite graphs, or finite state automata, are the corner stone
of computer science, it is still a very active field of research with
countless applications. Infinite state systems lack that kind of universal and
simple framework.
Graph grammars were initially used to produce infinite sets of graphs. But in
the early 90's, Courcelle used deterministic graph grammars to characterise a
general class of infinite graphs: regular graphs. Recently Caucal built up a
nice toolbox for studying regular graphs, and with Hassen they provided an
elegant extension of visibly pushdown automata, which captures every
deterministic context-free language.
In this talk we will present a survey on regular graphs, including a
discussion on the extensions of visibly pushdown automata. We will present, as
well, an ongoing work with Nathalie Bertrand aiming at generalising
probabilistic pushdown automata to this graph grammar setting.