Regular Sensing
===============

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 {\em 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 {\em sensing cost of an automaton\/} is then its
expected sensing, under a uniform distribution of the alphabet, and
the {\em 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 show that for finite words, size and sensing are related, and
minimal sensing is attained by minimal automata. Thus, a unique
minimal-sensing deterministic automaton exists, and is based on the
language's right-congruence relation.  For infinite words, the minimal
sensing may be the limit of an infinite sequence of automata. We show
that the unique limit of such sequences can be characterized by the
language's right-congruence relation, which enables us to find the
sensing cost of $\omega$-regular languages in polynomial time. Also,
interestingly, the sensing cost is independent of the acceptance
condition. This is in contrast with the size measure, where the size
of a minimal deterministic automaton for an $\omega$-regular language
depends on the acceptance condition, a unique minimal automaton need
not exists, and the problem of finding one is NP-complete. We also
study the affect of standard operations (e.g., union, concatenation,
etc.) on the sensing cost of automata and languages.