%0 Conference Proceedings
%T Sensing as a Complexity Measure
%+ Oxford Brookes University
%+ Laboratoire de l'Informatique du Parallélisme (LIP)
%+ The Hebrew University of Jerusalem (HUJ)
%A Almagor, Shaull
%A Kuperberg, Denis
%A Kupferman, Orna
%Z Part 1: Invited Papers
%< avec comité de lecture
%( Lecture Notes in Computer Science
%B 19th International Conference on Descriptional Complexity of Formal Systems (DCFS)
%C Milano, Italy
%Y Giovanni Pighizzini
%Y Cezar Câmpeanu
%I Springer International Publishing
%3 Descriptional Complexity of Formal Systems
%V LNCS-10316
%P 3-15
%8 2017-07-03
%D 2017
%R 10.1007/978-3-319-60252-3_1
%Z Computer Science [cs]Conference papers
%X 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 study the sensing cost of regular and $\omega $-regular languages, as well as applications of the study in practice, especially in the monitoring and synthesis of reactive systems.
%G English
%Z TC 1
%Z WG 1.2
%2 https://inria.hal.science/hal-01657019/document
%2 https://inria.hal.science/hal-01657019/file/440206_1_En_1_Chapter.pdf
%L hal-01657019
%U https://inria.hal.science/hal-01657019
%~ ENS-LYON
%~ CNRS
%~ INRIA
%~ UNIV-LYON1
%~ LIP_PLUME
%~ IFIP-LNCS
%~ IFIP
%~ IFIP-TC
%~ IFIP-TC1
%~ IFIP-WG
%~ INRIA2017
%~ IFIP-DCFS
%~ IFIP-WG1-2
%~ IFIP-LNCS-10316
%~ INRIA-AUT
%~ UDL
%~ UNIV-LYON
%~ INRIA-ROYAUMEUNI