Regular graphs : a perfect model for infinite state systems?

Christophe Morvan
Université de Marne-la-Vallée, France
Friday, 17 October, 2008 (All day)

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 provides 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 this family (regular graphs), we will discuss on the extension of visibly pushdown automata. And finally we will present probabilistic regular graphs which are a slight, but nice generalisation of probabilistic pushdown automata (the last part being ongoing work with Nathalie Bertrand). We will try to illustrate that these graph grammars are, indeed, a perfect to for modeling infinite state systems.