Regular Sensing

Prelegent(ci)

Denis Kuperberg

Afiliacja

Uniwersytet Warszawski

Termin

29 stycznia 2014 14:15

Pokój

p. 5870

Tytuł w języku angielskim

joint work with Shaull Almagor and Orna Kupferman

Seminarium

Seminarium „Teoria automatów”

---

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.
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 attained only as a limit, by an infinite sequence of automata. We show that the optimal 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.

---