Sensing as a Complexity Measure

The size of deterministic automata required for recognizing regular and $\omega$-regular languages is a well-studied measure for the complexity of languages. We introduce and study a new complexity measure, based on the sensing required for recognizing the language. Intuitively, the sensing cost quantifies the detail in which a random input word has to be read in order to decide its membership in the language. Technically, we consider languages over an alphabet $2^{P}$, for a finite set $P$ of signals. A signal $p \in P$ is sensed in a state of the automaton if transitions from the state depend on its value. The sensing cost of an automaton is then its expected sensing, under a uniform distribution of the alphabet, and the sensing cost of a language is the infimum of the sensing costs of deterministic automata for the language. Beyond the theoretical interest in regular sensing, it corresponds to natural and practical questions in the design of finite-state monitors, as well as controllers and transducers.

We study regular sensing for languages of finite and infinite words, as well as applications in monitoring and synthesis. In the first, the goal is to design a monitor that examines all computations and minimizes the expected average number of sensors used in the monitoring process. In the second, our goal is to design a transducer that realizes the specification for all input sequences and minimizes the expected average number of sensors used for reading the inputs.

Joint work with Shaull Almagor and Denis Kuperberg.