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.
We address the reachability problem in acyclic networks of pushdown systems.
We consider communication based either on shared memory or on message passing
through unbounded lossy channels. We prove mainly that the reachability
problem between recognizable sets of configurations (i.e., definable by a
finite union of products of finite-state automata) is decidable for such
networks, and that for lossy channel pushdown networks, the channel language
is effectively recognizable. This fact holds although the set of reachable
configurations (including stack contents) for a network of depth (at least) 2
is not rational in general (i.e., not definable by a multi-tape finite
automaton). Moreover, we prove that for a network of depth 1, the reachability
set is rational and effectively constructible (under an additional condition
on the topology for lossy channel networks).
This is a joint work with Mohamed
Faouzi Atig and Ahmed Bouajjani.