{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,29]],"date-time":"2025-11-29T07:55:54Z","timestamp":1764402954091},"reference-count":20,"publisher":"World Scientific Pub Co Pte Lt","issue":"06n07","funder":[{"name":"European Research Council under the European Union's 7th Framework Programme","award":["FP7\/2007-2013","278410"],"award-info":[{"award-number":["FP7\/2007-2013","278410"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2019,9]]},"abstract":"<jats:p> The size of deterministic automata required for recognizing regular and [Formula: see text]-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 [Formula: see text]-regular languages, as well as applications of the study in practice, especially in the monitoring and synthesis of reactive systems. <\/jats:p>","DOI":"10.1142\/s0129054119400203","type":"journal-article","created":{"date-parts":[[2019,9,19]],"date-time":"2019-09-19T03:06:43Z","timestamp":1568862403000},"page":"831-873","source":"Crossref","is-referenced-by-count":2,"title":["Sensing as a Complexity Measure"],"prefix":"10.1142","volume":"30","author":[{"given":"Shaull","family":"Almagor","sequence":"first","affiliation":[{"name":"Department of Computer Science, Oxford University, Oxford, OX1 3QD, UK"}]},{"given":"Denis","family":"Kuperberg","sequence":"additional","affiliation":[{"name":"CNRS, ENS Lyon, Universit\u00e9 de Lyon, LIP, Lyon 69364, France"}]},{"given":"Orna","family":"Kupferman","sequence":"additional","affiliation":[{"name":"School of Engineering and Computer Science, The Hebrew University, Jerusalem 9190416, Israel"}]}],"member":"219","published-online":{"date-parts":[[2019,9,19]]},"reference":[{"key":"S0129054119400203BIB001","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-54862-8_37"},{"key":"S0129054119400203BIB002","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2013.09.007"},{"key":"S0129054119400203BIB003","first-page":"161","volume-title":"Proc. 34th FST & TCS, LIPIcs","volume":"29","author":"Almagor S.","year":"2014"},{"key":"S0129054119400203BIB004","first-page":"380","volume-title":"Proc. 35th FST & TCS, LIPIcs","volume":"35","author":"Almagor S.","year":"2015"},{"key":"S0129054119400203BIB005","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-24310-3_11"},{"key":"S0129054119400203BIB006","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-78929-1_6"},{"key":"S0129054119400203BIB007","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2006.871582"},{"key":"S0129054119400203BIB009","volume-title":"Introduction to Probability","author":"Grinstead C.","year":"1997"},{"key":"S0129054119400203BIB010","first-page":"498","volume-title":"9th LICS","author":"Goubault J.","year":"1994"},{"issue":"2","key":"S0129054119400203BIB011","first-page":"18","volume":"6","author":"Havelund K.","year":"2004","journal-title":"STT&T"},{"key":"S0129054119400203BIB013","doi-asserted-by":"publisher","DOI":"10.2307\/421091"},{"key":"S0129054119400203BIB014","doi-asserted-by":"publisher","DOI":"10.1016\/S0065-2458(08)60342-3"},{"key":"S0129054119400203BIB015","doi-asserted-by":"publisher","DOI":"10.4064\/aa-82-4-365-377"},{"key":"S0129054119400203BIB016","doi-asserted-by":"publisher","DOI":"10.1145\/1989284.1989314"},{"key":"S0129054119400203BIB017","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0028571"},{"key":"S0129054119400203BIB018","doi-asserted-by":"publisher","DOI":"10.1145\/75277.75293"},{"key":"S0129054119400203BIB019","volume-title":"Markov Decision Processes: Discrete Stochastic Dynamic Programming","author":"Puterman M. L.","year":"2014"},{"key":"S0129054119400203BIB020","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(08)80035-1"},{"key":"S0129054119400203BIB021","series-title":"LIPIcs","first-page":"400","volume-title":"Proc. 30th FST & TCS","volume":"8","author":"Schewe S.","year":"2010"},{"key":"S0129054119400203BIB022","doi-asserted-by":"publisher","DOI":"10.1007\/BF01211865"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054119400203","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,19]],"date-time":"2019-09-19T03:07:38Z","timestamp":1568862458000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054119400203"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,9]]},"references-count":20,"journal-issue":{"issue":"06n07","published-print":{"date-parts":[[2019,9]]}},"alternative-id":["10.1142\/S0129054119400203"],"URL":"https:\/\/doi.org\/10.1142\/s0129054119400203","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,9]]}}}