Orna Kupferman

# 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.