{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T02:39:01Z","timestamp":1777516741923,"version":"3.51.4"},"reference-count":28,"publisher":"SAGE Publications","issue":"2","license":[{"start":{"date-parts":[[2017,3,1]],"date-time":"2017-03-01T00:00:00Z","timestamp":1488326400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["Computability"],"published-print":{"date-parts":[[2017,3,16]]},"abstract":"<jats:p>We provide an automata-theoretic approach to analyzing an abstract channel modeled by a transducer and to characterizing its lossy rates. In particular, we look at related decision problems and show the boundaries between the decidable and undecidable cases. We conduct experiments on several channels and use Lempel\u2013Ziv algorithms to estimate lossy rates of these channels.<\/jats:p>","DOI":"10.3233\/com-150050","type":"journal-article","created":{"date-parts":[[2017,3,10]],"date-time":"2017-03-10T10:39:33Z","timestamp":1489142373000},"page":"165-181","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":0,"title":["Lossiness of communication channels modeled by transducers"],"prefix":"10.1177","volume":"6","author":[{"given":"Oscar H.","family":"Ibarra","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of California, Santa Barbara, CA 93106, USA."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Cewei","family":"Cui","sequence":"additional","affiliation":[{"name":"School of Electrical Engineering & Computer Science, Washington State University, Pullman, WA 99164, USA."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhe","family":"Dang","sequence":"additional","affiliation":[{"name":"School of Electrical Engineering & Computer Science, Washington State University, Pullman, WA 99164, USA."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas R.","family":"Fischer","sequence":"additional","affiliation":[{"name":"School of Electrical Engineering & Computer Science, Washington State University, Pullman, WA 99164, USA."}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[2017,3,1]]},"reference":[{"key":"ref001","unstructured":"http:\/\/www.gzip.org\/."},{"key":"ref002","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90010-8"},{"key":"ref003","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04081-8_6"},{"key":"ref004","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(58)90082-2"},{"key":"ref005","unstructured":"T.M.Cover and J.A.Thomas, Elements of Information Theory, 2nd edn, Wiley-Interscience, 2006."},{"key":"ref006","unstructured":"C.Cui, Z.Dang and T.R.Fischer, Bit rate of programs, CoRR, 2013."},{"key":"ref007","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2013.05.040"},{"key":"ref008","doi-asserted-by":"crossref","unstructured":"C.Cui, Z.Dang, T.R.Fischer and O.H.Ibarra, Information rate of some classes of non-regular languages: An automata-theoretic approach, in: MFCS\u201914, Lecture Notes in Computer Science, Vol. 8634, Springer, 2014.","DOI":"10.1007\/978-3-662-44522-8_20"},{"key":"ref009","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00743-0"},{"key":"ref010","doi-asserted-by":"crossref","unstructured":"Z.Dang, O.H.Ibarra, T.Bultan, R.A.Kemmerer and J.Su, Binary reachability analysis of discrete pushdown timed automata, in: CAV\u201900: Proceedings of International Conference on Computer Aided Verification, Lecture Notes in Computer Science, Vol. 1855, Springer, 2000, pp.\u00a069\u201384.","DOI":"10.1007\/10722167_9"},{"key":"ref011","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-09039-9_4"},{"key":"ref012","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(81)90028-3"},{"key":"ref013","doi-asserted-by":"publisher","DOI":"10.1007\/BF01744569"},{"key":"ref014","unstructured":"J.E.Hopcroft, R.Motwani and J.D.Ullman, Introduction to Automata Theory, Languages, and Computation, 1st edn, Addison-Wesley, 1979."},{"key":"ref015","doi-asserted-by":"publisher","DOI":"10.1145\/322047.322058"},{"key":"ref016","doi-asserted-by":"crossref","unstructured":"O.H.Ibarra, Z.Dang, O.Egecioglu and G.Saxena, Characterizations of catalytic membrane computing systems, in: Proceedings of the 28th International Symposium on Mathematical Foundations of Computer Science (MFCS 2003), Lecture Notes in Computer Science, Vol. 2747, Springer, 2003, pp.\u00a0480\u2013489.","DOI":"10.1007\/978-3-540-45138-9_42"},{"issue":"2","key":"ref017","first-page":"175","volume":"17","author":"Kaminger F.P.","year":"1970","journal-title":"Inf. Comput."},{"key":"ref018","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(70)90105-1"},{"key":"ref019","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.03.012"},{"key":"ref020","unstructured":"G.Paun, Membrane Computing, an Introduction, Springer-Verlag, 2002."},{"key":"ref021","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-07407-4_22"},{"key":"ref022","unstructured":"C.E.Shannon and W.Weaver, The Mathematical Theory of Communication, University of Illinois Press, 1949."},{"key":"ref023","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-46011-X_12"},{"issue":"2","key":"ref024","first-page":"196","volume":"25","author":"Wang E.","year":"2014","journal-title":"Int\u2019l. J. Foundations of Computer Science"},{"issue":"9","key":"ref025","first-page":"749","volume":"27","author":"Weber A.","year":"1990","journal-title":"Acta Inf."},{"key":"ref026","unstructured":"K.Wich, Ambiguity functions of context-free grammars and languages, PhD thesis, 2004."},{"key":"ref027","doi-asserted-by":"crossref","unstructured":"G.Xie, Z.Dang and O.H.Ibarra, A solvable class of quadratic Diophantine equations with applications to verification of infinite state systems, in: Proceedings of the 30th International Colloquium on Automata, Languages and Programming (ICALP 2003), Lecture Notes in Computer Science, Vol. 2719, Springer, 2003, pp.\u00a0668\u2013680.","DOI":"10.1007\/3-540-45061-0_53"},{"key":"ref028","unstructured":"L.Yang, C.Cui, Z.Dang and T.R.Fischer, An information-theoretic complexity metric for labeled graphs, 2011, in review."}],"container-title":["Computability"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/COM-150050","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.3233\/COM-150050","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/COM-150050","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T15:59:51Z","timestamp":1777391991000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/full\/10.3233\/COM-150050"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,3,1]]},"references-count":28,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,3,16]]}},"alternative-id":["10.3233\/COM-150050"],"URL":"https:\/\/doi.org\/10.3233\/com-150050","relation":{},"ISSN":["2211-3568","2211-3576"],"issn-type":[{"value":"2211-3568","type":"print"},{"value":"2211-3576","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,3,1]]}}}