Sensing as a Complexity Measure

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.
Type de document :
Communication dans un congrès
Giovanni Pighizzini; Cezar Câmpeanu. 19th International Conference on Descriptional Complexity of Formal Systems (DCFS), Jul 2017, Milano, Italy. Springer International Publishing, Lecture Notes in Computer Science, LNCS-10316, pp.3-15, 2017, Descriptional Complexity of Formal Systems. 〈10.1007/978-3-319-60252-3_1〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01657019
Contributeur : Hal Ifip <>
Soumis le : mercredi 6 décembre 2017 - 11:44:56
Dernière modification le : jeudi 7 décembre 2017 - 01:15:38

Fichier

 Accès restreint
Fichier visible le : 2020-01-01

Connectez-vous pour demander l'accès au fichier

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Shaull Almagor, Denis Kuperberg, Orna Kupferman. Sensing as a Complexity Measure. Giovanni Pighizzini; Cezar Câmpeanu. 19th International Conference on Descriptional Complexity of Formal Systems (DCFS), Jul 2017, Milano, Italy. Springer International Publishing, Lecture Notes in Computer Science, LNCS-10316, pp.3-15, 2017, Descriptional Complexity of Formal Systems. 〈10.1007/978-3-319-60252-3_1〉. 〈hal-01657019〉

Partager

Métriques

Consultations de la notice

11