@article{doi:10.1142/S0129054119400203,
    Abstract = {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.},
    Author = {Almagor, Shaull and Kuperberg, Denis and Kupferman, Orna},
    EPrint = {https://doi.org/10.1142/S0129054119400203},
    File = {Sensing as a Complexity Measure - almagor2019 - a - f.pdf},
    Journal = {International Journal of Foundations of Computer Science},
    Number = {06n07},
    Pages = {831-873},
    Title = {Sensing as a Complexity Measure},
    URL = {https://doi.org/10.1142/S0129054119400203},
    Volume = {30},
    Year = {2019},
    bdsk-url-1 = {https://doi.org/10.1142/S0129054119400203},
    date-added = {2020-05-13 15:31:23 +0200},
    date-modified = {2020-05-13 15:31:23 +0200},
    doi = {10.1142/S0129054119400203}
}

@article{doi:10.1142/S0129054119400203, Abstract = {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.}, Author = {Almagor, Shaull and Kuperberg, Denis and Kupferman, Orna}, EPrint = {https://doi.org/10.1142/S0129054119400203}, File = {Sensing as a Complexity Measure - almagor2019 - a - f.pdf}, Journal = {International Journal of Foundations of Computer Science}, Number = {06n07}, Pages = {831-873}, Title = {Sensing as a Complexity Measure}, URL = {https://doi.org/10.1142/S0129054119400203}, Volume = {30}, Year = {2019}, bdsk-url-1 = {https://doi.org/10.1142/S0129054119400203}, date-added = {2020-05-13 15:31:23 +0200}, date-modified = {2020-05-13 15:31:23 +0200}, doi = {10.1142/S0129054119400203} }