Seminar Details
2006-12-05 (14.00 pm) : "How to track an agent in a network ?"
At Euler building
Organized by Mathematical Engineering
Speaker :
Jungers, Raphaël M.
Abstract :
Consider an agent moving from node to node in a directed graph
whose edges are colored. The agent knows the colored graph but does not know where he is,
and he tries to reconstruct his position in the graph based on the color sequence he observes.
We say that an edgecolored directed graph is observable if there is some observation time length
after which, whatever the color sequence observed, the agent is able to determine his position in the
graph and is able to do so for all subsequent times. This framework leads to several interesting questions:
How can the agent deduce his position from the sequence of colors he observes? Will he be able to do so in all case?
How to assign colors in a graph so that he will be able to compute his position efficiently?
This problem is related with well studied problems in several fields
of engineering, including Hidden Markov Models, Discret Events Systems in control theory, and
Local Automata in the theory of automata and formal languages . We review and connect the main results
arising from those areas, and present some new complexity results on the design question.