On the Zeta Function of a Periodic-Finite-Type Shift

Akiko MANADA; Navin KASHYAP

doi:10.1587/transfun.E96.A.1024

On the Zeta Function of a Periodic-Finite-Type Shift

Akiko MANADA, Navin KASHYAP

Full Text Views

0

Share
Cite this

Summary :

Periodic-finite-type shifts (PFT's) are sofic shifts which forbid the appearance of finitely many pre-specified words in a periodic manner. The class of PFT's strictly includes the class of shifts of finite type (SFT's). The zeta function of a PFT is a generating function for the number of periodic sequences in the shift. For a general sofic shift, there exists a formula, attributed to Manning and Bowen, which computes the zeta function of the shift from certain auxiliary graphs constructed from a presentation of the shift. In this paper, we derive an interesting alternative formula computable from certain “word-based graphs” constructed from the periodically-forbidden word description of the PFT. The advantages of our formula over the Manning-Bowen formula are discussed.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E96-A No.6 pp.1024-1031

Publication Date: 2013/06/01

Publicized

Online ISSN: 1745-1337

DOI: 10.1587/transfun.E96.A.1024

Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)

Category

Authors

Akiko MANADA
The University of Electro-Communications
Navin KASHYAP
Indian Institute of Science

Keyword

periodic-finite-type shift, zeta function, word-based graph, Mobius inversion formula

Cite this

Copy

Akiko MANADA, Navin KASHYAP, "On the Zeta Function of a Periodic-Finite-Type Shift" in IEICE TRANSACTIONS on Fundamentals, vol. E96-A, no. 6, pp. 1024-1031, June 2013, doi: 10.1587/transfun.E96.A.1024.
Abstract: Periodic-finite-type shifts (PFT's) are sofic shifts which forbid the appearance of finitely many pre-specified words in a periodic manner. The class of PFT's strictly includes the class of shifts of finite type (SFT's). The zeta function of a PFT is a generating function for the number of periodic sequences in the shift. For a general sofic shift, there exists a formula, attributed to Manning and Bowen, which computes the zeta function of the shift from certain auxiliary graphs constructed from a presentation of the shift. In this paper, we derive an interesting alternative formula computable from certain “word-based graphs” constructed from the periodically-forbidden word description of the PFT. The advantages of our formula over the Manning-Bowen formula are discussed.
URL: https://globals.ieice.org/en_transactions/fundamentals/10.1587/transfun.E96.A.1024/_p

Copy

@ARTICLE{e96-a_6_1024,
author={Akiko MANADA, Navin KASHYAP, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={On the Zeta Function of a Periodic-Finite-Type Shift},
year={2013},
volume={E96-A},
number={6},
pages={1024-1031},
abstract={Periodic-finite-type shifts (PFT's) are sofic shifts which forbid the appearance of finitely many pre-specified words in a periodic manner. The class of PFT's strictly includes the class of shifts of finite type (SFT's). The zeta function of a PFT is a generating function for the number of periodic sequences in the shift. For a general sofic shift, there exists a formula, attributed to Manning and Bowen, which computes the zeta function of the shift from certain auxiliary graphs constructed from a presentation of the shift. In this paper, we derive an interesting alternative formula computable from certain “word-based graphs” constructed from the periodically-forbidden word description of the PFT. The advantages of our formula over the Manning-Bowen formula are discussed.},
keywords={},
doi={10.1587/transfun.E96.A.1024},
ISSN={1745-1337},
month={June},}

Copy

TY - JOUR
TI - On the Zeta Function of a Periodic-Finite-Type Shift
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1024
EP - 1031
AU - Akiko MANADA
AU - Navin KASHYAP
PY - 2013
DO - 10.1587/transfun.E96.A.1024
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E96-A
IS - 6
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - June 2013
AB - Periodic-finite-type shifts (PFT's) are sofic shifts which forbid the appearance of finitely many pre-specified words in a periodic manner. The class of PFT's strictly includes the class of shifts of finite type (SFT's). The zeta function of a PFT is a generating function for the number of periodic sequences in the shift. For a general sofic shift, there exists a formula, attributed to Manning and Bowen, which computes the zeta function of the shift from certain auxiliary graphs constructed from a presentation of the shift. In this paper, we derive an interesting alternative formula computable from certain “word-based graphs” constructed from the periodically-forbidden word description of the PFT. The advantages of our formula over the Manning-Bowen formula are discussed.
ER -