{"id":{"repo_id":"queens","oai_identifier":"oai:queensu.scholaris.ca:1974/2584"},"canonical_url":"https://search.dev.ndltd.org/etd/queens/oai:queensu.scholaris.ca:1974/2584","repository":{"repo_id":"queens","name":"Queens University","base_url":"https://qspace.library.queensu.ca/server/oai/request"},"display":{"title":"Minimal Presentations of Sofic Shifts and Properties of Periodic-Finite-Type Shifts","abstract":"Constrained codes have been used in data storage systems, such as magnetic tapes, CD’s and DVD’s, in order to reduce the likelihood of errors by predictable noise. The study of constrained codes is based on the study of sofic shifts, which are sets of bi-infinite sequences that can be presented using labeled directed graphs called presentations. In this thesis, we will primarily focus on two classes of sofic shifts, namely shifts of finite type (SFT’s) and periodic-finite-type shifts (PFT’s), and examine their properties. We first consider Shannon covers of sofic shifts. A Shannon cover of a sofic shift is a deterministic presentation with the smallest number of vertices among all deterministic presentations of the shift. Indeed, a Shannon cover is used as a canonical presentation of a sofic shift, and furthermore, it is used when computing the capacity of the shift or when constructing a finite-state encoder. We follow an algorithm by Crochemore, Mignosi and Restivo which constructs a deterministic presentation of an SFT and we see how to derive a Shannon cover from the presentation under their algorithm. Furthermore, as a method to determine whether a given deterministic presentation is a Shannon cover of a sofic shift, we will provide, based on research by Jonoska, a sufficient condition for a given presentation to have the smallest number of vertices among all presentations of the shift. We then move our focus towards PFT’s, and investigate new properties of PFT’s from various perspectives. We define three types of periods that can be associated with a PFT and do pairwise comparisons between them. Also, we consider the zeta function of a PFT, which is a generating function for the number of periodic sequences in the PFT, and present a simple formula to compute the zeta function of a PFT.","abstract_html":"Constrained codes have been used in data storage systems, such as magnetic tapes, CD’s and DVD’s, in order to reduce the likelihood of errors by predictable noise. The study of constrained codes is based on the study of sofic shifts, which are sets of bi-infinite sequences that can be presented using labeled directed graphs called presentations. In this thesis, we will primarily focus on two classes of sofic shifts, namely shifts of finite type (SFT’s) and periodic-finite-type shifts (PFT’s), and examine their properties. We first consider Shannon covers of sofic shifts. A Shannon cover of a sofic shift is a deterministic presentation with the smallest number of vertices among all deterministic presentations of the shift. Indeed, a Shannon cover is used as a canonical presentation of a sofic shift, and furthermore, it is used when computing the capacity of the shift or when constructing a finite-state encoder. We follow an algorithm by Crochemore, Mignosi and Restivo which constructs a deterministic presentation of an SFT and we see how to derive a Shannon cover from the presentation under their algorithm. Furthermore, as a method to determine whether a given deterministic presentation is a Shannon cover of a sofic shift, we will provide, based on research by Jonoska, a sufficient condition for a given presentation to have the smallest number of vertices among all presentations of the shift. We then move our focus towards PFT’s, and investigate new properties of PFT’s from various perspectives. We define three types of periods that can be associated with a PFT and do pairwise comparisons between them. Also, we consider the zeta function of a PFT, which is a generating function for the number of periodic sequences in the PFT, and present a simple formula to compute the zeta function of a PFT.","abstract_has_math":false,"creators":["Manada, Akiko"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":"Mathematics and Statistics","school":null,"contributors":[],"advisors":["Kashyap, Navin"],"committee_chairs":[],"committee_members":[],"year":2009,"date_issued":"2009-08-12T21:39:06Z","date_published":"2009-08-12T21:39:06Z","updated_at":"2026-07-27T20:35:17Z","subjects":["sofic shift","periodic-finite-type shift","shannon cover","shift of finite type","periods","zeta function"],"languages":["eng"],"rights":[],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/1974/2584","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.department","label":"Department","values":["Mathematics and Statistics"]},{"key":"dc:contributor.supervisor","label":"Supervisor","values":["Kashyap, Navin"]},{"key":"dc:creator","label":"Author","values":["Manada, Akiko"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2009-07-30 22:29:22.967","2009-08-08 14:08:36.876"]},{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2009-08-12T21:39:06Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2009-08-12T21:39:06Z"]},{"key":"dc:date.issued","label":"Date","values":["2009-08-12T21:39:06Z"]},{"key":"dc:type","label":"Dc Type","values":["thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["sofic shift","periodic-finite-type shift","shannon cover","shift of finite type","periods","zeta function"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["eng"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/1974/2584"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Thesis (Ph.D, Mathematics & Statistics) -- Queen's University, 2009-08-08 14:08:36.876"]},{"key":"dc:description.abstract","label":"Abstract","values":["Constrained codes have been used in data storage systems, such as magnetic tapes, CD’s and DVD’s, in order to reduce the likelihood of errors by predictable noise. The study of constrained codes is based on the study of sofic shifts, which are sets of bi-infinite sequences that can be presented using labeled directed graphs called presentations. In this thesis, we will primarily focus on two classes of sofic shifts, namely shifts of finite type (SFT’s) and periodic-finite-type shifts (PFT’s), and examine their properties. We first consider Shannon covers of sofic shifts. A Shannon cover of a sofic shift is a deterministic presentation with the smallest number of vertices among all deterministic presentations of the shift. Indeed, a Shannon cover is used as a canonical presentation of a sofic shift, and furthermore, it is used when computing the capacity of the shift or when constructing a finite-state encoder. We follow an algorithm by Crochemore, Mignosi and Restivo which constructs a deterministic presentation of an SFT and we see how to derive a Shannon cover from the presentation under their algorithm. Furthermore, as a method to determine whether a given deterministic presentation is a Shannon cover of a sofic shift, we will provide, based on research by Jonoska, a sufficient condition for a given presentation to have the smallest number of vertices among all presentations of the shift. We then move our focus towards PFT’s, and investigate new properties of PFT’s from various perspectives. We define three types of periods that can be associated with a PFT and do pairwise comparisons between them. Also, we consider the zeta function of a PFT, which is a generating function for the number of periodic sequences in the PFT, and present a simple formula to compute the zeta function of a PFT."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["PhD"]},{"key":"dc:format.mimetype","label":"Dc Format Mimetype","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Minimal Presentations of Sofic Shifts and Properties of Periodic-Finite-Type Shifts"]}]}],"canonical_facts":{"dc:contributor.department":["Mathematics and Statistics"],"dc:contributor.supervisor":["Kashyap, Navin"],"dc:creator":["Manada, Akiko"],"dc:date":["2009-07-30 22:29:22.967","2009-08-08 14:08:36.876"],"dc:date.accessioned":["2009-08-12T21:39:06Z"],"dc:date.available":["2009-08-12T21:39:06Z"],"dc:date.issued":["2009-08-12T21:39:06Z"],"dc:description":["Thesis (Ph.D, Mathematics & Statistics) -- Queen's University, 2009-08-08 14:08:36.876"],"dc:description.abstract":["Constrained codes have been used in data storage systems, such as magnetic tapes, CD’s and DVD’s, in order to reduce the likelihood of errors by predictable noise. The study of constrained codes is based on the study of sofic shifts, which are sets of bi-infinite sequences that can be presented using labeled directed graphs called presentations. In this thesis, we will primarily focus on two classes of sofic shifts, namely shifts of finite type (SFT’s) and periodic-finite-type shifts (PFT’s), and examine their properties. We first consider Shannon covers of sofic shifts. A Shannon cover of a sofic shift is a deterministic presentation with the smallest number of vertices among all deterministic presentations of the shift. Indeed, a Shannon cover is used as a canonical presentation of a sofic shift, and furthermore, it is used when computing the capacity of the shift or when constructing a finite-state encoder. We follow an algorithm by Crochemore, Mignosi and Restivo which constructs a deterministic presentation of an SFT and we see how to derive a Shannon cover from the presentation under their algorithm. Furthermore, as a method to determine whether a given deterministic presentation is a Shannon cover of a sofic shift, we will provide, based on research by Jonoska, a sufficient condition for a given presentation to have the smallest number of vertices among all presentations of the shift. We then move our focus towards PFT’s, and investigate new properties of PFT’s from various perspectives. We define three types of periods that can be associated with a PFT and do pairwise comparisons between them. Also, we consider the zeta function of a PFT, which is a generating function for the number of periodic sequences in the PFT, and present a simple formula to compute the zeta function of a PFT."],"dc:description.degree":["PhD"],"dc:format.mimetype":["application/pdf"],"dc:identifier.uri":["http://hdl.handle.net/1974/2584"],"dc:language.iso":["eng"],"dc:subject":["sofic shift","periodic-finite-type shift","shannon cover","shift of finite type","periods","zeta function"],"dc:title":["Minimal Presentations of Sofic Shifts and Properties of Periodic-Finite-Type Shifts"],"dc:type":["thesis"]},"updated_at":"2026-07-27T20:35:17Z"}