Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata

https://hal.inria.fr/hal-01657019
Contributor : Hal Ifip <>
Submitted on : Wednesday, December 6, 2017 - 11:44:56 AM
Last modification on : Wednesday, November 20, 2019 - 2:58:18 AM

File

440206_1_En_1_Chapter.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

Shaull Almagor, Denis Kuperberg, Orna Kupferman. Sensing as a Complexity Measure. 19th International Conference on Descriptional Complexity of Formal Systems (DCFS), Jul 2017, Milano, Italy. pp.3-15, ⟨10.1007/978-3-319-60252-3_1⟩. ⟨hal-01657019⟩

Share

Metrics

Record views

243

Files downloads

105