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.
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.