{"id":12752,"date":"2021-11-20T18:37:37","date_gmt":"2021-11-20T23:37:37","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=12752"},"modified":"2026-06-02T14:59:26","modified_gmt":"2026-06-02T18:59:26","slug":"tr-256-string-recognition-on-anonymous-rings","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1994\/tr-256-string-recognition-on-anonymous-rings\/","title":{"rendered":"TR-256: String Recognition on Anonymous Rings"},"content":{"rendered":"\n<section class=\"w-screen px-6 cu-section cu-section--white ml-offset-center md:px-8 lg:px-14\">\n    <div class=\"space-y-6 cu-max-w-child-5xl  md:space-y-10 cu-prose-first-last\">\n\n            <div class=\"cu-textmedia flex flex-col lg:flex-row mx-auto gap-6 md:gap-10 my-6 md:my-12 first:mt-0 max-w-5xl\">\n        <div class=\"justify-start cu-textmedia-content cu-prose-first-last\" style=\"flex: 0 0 100%;\">\n            <header class=\"font-light prose-xl cu-pageheader md:prose-2xl cu-component-updated cu-prose-first-last\">\n                                    <h1 class=\"cu-prose-first-last font-semibold !mt-2 mb-4 md:mb-6 relative after:absolute after:h-px after:bottom-0 after:bg-cu-red after:left-px text-3xl md:text-4xl lg:text-5xl lg:leading-[3.5rem] pb-5 after:w-10 text-cu-black-700 not-prose\">\n                        TR-256: String Recognition on Anonymous Rings\n                    <\/h1>\n                \n                                \n                            <\/header>\n\n                    <\/div>\n\n            <\/div>\n\n    <\/div>\n<\/section>\n\n<p>Carleton University<br>\n<a href=\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1994\/\">Technical Report<\/a> <strong>TR-256<\/strong><br>\nNovember 1994<\/p>\n\n\n\n<h2 id=\"string-recognition-on-anonymous-rings\" class=\"wp-block-heading tr_t1\">String Recognition on Anonymous Rings<\/h2>\n\n\n\n<div class=\"tr_t3\">\n<div class=\"tr_t3\">\n<div class=\"tr_t3\">Evangelos Kranakis, Danny Krizanc , Flaminia L. Luccio<\/div>\n<\/div>\n<\/div>\n\n\n\n<div>\n<h3>Abstract<\/h3>\n<\/div>\n\n\n\n<p>We consider the problem of recognizing whether a given binary string of length n is equal (up to rotation) to the input of an anonymous oriented ring of n processors. Previous algorithms for this problem have been &#8220;global&#8221; and do not take into account &#8220;local&#8221; patterns occurring in the string. Such patterns may be repetitive or discriminating, and can be used to provide e\u000ecient algorithms for recognizing strings. In this paper we give new upper and lower bounds on the bit complexity of string recognition. For the case of periodic strings, near optimal bounds are given which depend on the period of the string. For the case of a randomly chosen string, an optimal algorithm for the problem is given. In particular, we show that almost all strings can be recog- nized by communicating \u0002(n log n) bits. It is interesting to note that Kolmogorov complexity theory is used in the proof of our upper bound, rather than its traditional application to the proof of lower bounds.<\/p>\n\n\n\n<p><a href=\"https:\/\/carleton.ca\/scs\/wp-content\/uploads\/sites\/260\/TR256.pdf\">TR-256.pdf<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Carleton University Technical Report TR-256 November 1994 String Recognition on Anonymous Rings Evangelos Kranakis, Danny Krizanc , Flaminia L. Luccio Abstract We consider the problem of recognizing whether a given binary string of length n is equal (up to rotation) to the input of an anonymous oriented ring of n processors. Previous algorithms for this [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"parent":11914,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_acf_changed":false,"_cu_dining_location_slug":"","footnotes":"","_links_to":"","_links_to_target":""},"cu_page_type":[],"class_list":["post-12752","page","type-page","status-publish","hentry"],"acf":{"cu_post_thumbnail":false},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12752","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/comments?post=12752"}],"version-history":[{"count":1,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12752\/revisions"}],"predecessor-version":[{"id":12753,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12752\/revisions\/12753"}],"up":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/11914"}],"wp:attachment":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/media?parent=12752"}],"wp:term":[{"taxonomy":"cu_page_type","embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/cu_page_type?post=12752"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}