{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,3]],"date-time":"2022-04-03T03:38:27Z","timestamp":1648957107210},"reference-count":8,"publisher":"World Scientific Pub Co Pte Lt","issue":"06","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2012,9]]},"abstract":"<jats:p> We investigate how two agents can communicate through a noisy medium modeled as a finite non deterministic transducer. The sender and the receiver are also described by finite transducers which can respectively encode and decode binary messages. When the communication is reliable, we call the encoder\/decoder pair a channel. <\/jats:p><jats:p> We study the channel synthesis problem which, given a transducer, asks whether or not such sender and receiver exist and builds them if the answer is positive. To that effect we introduce the structural notion of encoding state in a transducer which is a necessary condition for the existence of a channel. It is not, however, a sufficient condition. In fact, we prove that the problem is undecidable. Nonetheless, we obtain a synthesis procedure when the transducer is functional. We discuss these results in relation to security properties. <\/jats:p>","DOI":"10.1142\/s0129054112400503","type":"journal-article","created":{"date-parts":[[2012,11,25]],"date-time":"2012-11-25T22:26:33Z","timestamp":1353882393000},"page":"1241-1260","source":"Crossref","is-referenced-by-count":1,"title":["CHANNEL SYNTHESIS FOR FINITE TRANSDUCERS"],"prefix":"10.1142","volume":"23","author":[{"given":"GILLES","family":"BENATTAR","sequence":"first","affiliation":[{"name":"LUNAM Universit\u00e9, \u00c9cole Centrale de Nantes, IRCCyN, CNRS UMR 6597, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"B\u00c9ATRICE","family":"B\u00c9RARD","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Pierre &amp; Marie Curie, LIP6\/MoVe, CNRS UMR 7606, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"DIDIER","family":"LIME","sequence":"additional","affiliation":[{"name":"LUNAM Universit\u00e9, \u00c9cole Centrale de Nantes, IRCCyN, CNRS UMR 6597, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"JOHN","family":"MULLINS","sequence":"additional","affiliation":[{"name":"\u00c9cole Polytechnique de Montr\u00e9al, Department of Computer and Software Engineering, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"OLIVIER H.","family":"ROUX","sequence":"additional","affiliation":[{"name":"LUNAM Universit\u00e9, \u00c9cole Centrale de Nantes, IRCCyN, CNRS UMR 6597, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"MATHIEU","family":"SASSOLAS","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Pierre &amp; Marie Curie, LIP6\/MoVe, CNRS UMR 7606, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2012,11,25]]},"reference":[{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1147\/rd.91.0047"},{"key":"rf5","volume-title":"An introduction to the theory of computation","author":"Gurari E.","year":"1989"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-58131-6_43"},{"key":"rf7","volume-title":"Introduction to formal language theory","author":"Harrison M. A.","year":"1978"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1145\/362375.362389"},{"key":"rf12","series-title":"Encyclopedia of Mathematics","volume-title":"Combinatorics on words","volume":"17","author":"Lothaire M.","year":"1983"},{"key":"rf15","volume-title":"\u00c9l\u00e9ments de th\u00e9orie des automates","author":"Sakarovitch J.","year":"2003"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1504\/IJAMC.2007.014811"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054112400503","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T08:02:52Z","timestamp":1565078572000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054112400503"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,9]]},"references-count":8,"journal-issue":{"issue":"06","published-online":{"date-parts":[[2012,11,25]]},"published-print":{"date-parts":[[2012,9]]}},"alternative-id":["10.1142\/S0129054112400503"],"URL":"https:\/\/doi.org\/10.1142\/s0129054112400503","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,9]]}}}