Résumé | I will present a complexity measure named sensing cost, designed for automata and transducters. It measures the average amount of information from the environment that must be read by the system at each time instant, in a random environment. It is then natural to look for minimally sensing automata for a given language, or minimally-sensing transducers as solutions of synthesis problems. I will present results along these lines, as well as open problems that remain to be tackled.
This is joint work with Shaull Almagor and Orna Kupferman. |