Hostname: page-component-78c5997874-fbnjt Total loading time: 0 Render date: 2024-11-09T06:35:05.911Z Has data issue: false hasContentIssue false

Suffix conjugates for a class of morphic subshifts

Published online by Cambridge University Press:  04 June 2014

JAMES D. CURRIE
Affiliation:
Department of Mathematics and Statistics, University of Winnipeg, 515 Portage Avenue, Winnipeg, MB R3B 2E9, Canada email [email protected], [email protected], [email protected]
NARAD RAMPERSAD
Affiliation:
Department of Mathematics and Statistics, University of Winnipeg, 515 Portage Avenue, Winnipeg, MB R3B 2E9, Canada email [email protected], [email protected], [email protected]
KALLE SAARI
Affiliation:
Department of Mathematics and Statistics, University of Winnipeg, 515 Portage Avenue, Winnipeg, MB R3B 2E9, Canada email [email protected], [email protected], [email protected]

Abstract

Let $A$ be a finite alphabet and $f:~A^{\ast }\rightarrow A^{\ast }$ be a morphism with an iterative fixed point $f^{{\it\omega}}({\it\alpha})$, where ${\it\alpha}\in A$. Consider the subshift $({\mathcal{X}},T)$, where ${\mathcal{X}}$ is the shift orbit closure of $f^{{\it\omega}}({\it\alpha})$ and $T:~{\mathcal{X}}\rightarrow {\mathcal{X}}$ is the shift map. Let $S$ be a finite alphabet that is in bijective correspondence via a mapping $c$ with the set of non-empty suffixes of the images $f(a)$ for $a\in A$. Let ${\mathcal{S}}\subset S^{\mathbb{N}}$ be the set of infinite words $\mathbf{s}=(s_{n})_{n\geq 0}$ such that ${\it\pi}(\mathbf{s}):=c(s_{0})f(c(s_{1}))f^{2}(c(s_{2}))\cdots \in {\mathcal{X}}$. We show that if $f$ is primitive, $f^{{\it\omega}}({\it\alpha})$ is aperiodic, and $f(A)$ is a suffix code, then there exists a mapping $H:~{\mathcal{S}}\rightarrow {\mathcal{S}}$ such that $({\mathcal{S}},H)$ is a topological dynamical system and ${\it\pi}:~({\mathcal{S}},H)\rightarrow ({\mathcal{X}},T)$ is a conjugacy; we call $({\mathcal{S}},H)$ the suffix conjugate of $({\mathcal{X}},T)$. In the special case where $f$ is the Fibonacci or Thue–Morse morphism, we show that the subshift $({\mathcal{S}},T)$ is sofic, that is, the language of ${\mathcal{S}}$ is regular.

Type
Research Article
Copyright
© Cambridge University Press, 2014 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Allouche, J.-P. and Shallit, J.. Automatic Sequences: Theory, Applications, and Generalizations. Cambridge University Press, Cambridge, 2003.CrossRefGoogle Scholar
Cassaigne, J. and Nicolas, F.. Factor complexity. Combinatorics, Automata and Number Theory. Eds. Berthé, V. and Rigo, M.. Cambridge University Press, Cambridge, 2010.Google Scholar
Cassaigne, J.. An algorithm to test if a given circular HD0L-language avoids a pattern. Information Processing ’94 (Hamburg, 1994), Vol. I (IFIP Trans. A Comput. Sci. Tech., A-51). North-Holland, Amsterdam, 1994, pp. 459464.Google Scholar
Canterini, V. and Siegel, A.. Automate des préfixes-suffixes associé à une substitution primitive. J. Théor. Nombres Bordeaux 13 (2001), 353369.CrossRefGoogle Scholar
Currie, J, Rampersad, N and Saari, K. Extremal words in the shift orbit closure of a morphic sequence. Proceedings of Developments in Language Theory 2013 (Lecture Notes in Computer Science, 7907). Springer, Berlin, 2013, pp. 143154.CrossRefGoogle Scholar
Holton, C. and Zamboni, L. Q.. Descendants of primitive substitutions. Theory Comput. Syst. 32 (1999), 133157.CrossRefGoogle Scholar
Holton, C. and Zamboni, L. Q.. Directed graphs and substitutions. Theory Comput. Syst. 34 (2001), 545564.CrossRefGoogle Scholar
Klouda, K.. Bispecial factors in circular non-pushy D0L languages. Theoret. Comput. Sci. 445 (2012), 6374.CrossRefGoogle Scholar
Kůrka, P.. Topological and Symbolic Dynamics. Société Mathématique de France, Paris, 2003.Google Scholar
Lind, D. and Marcus, B.. An Introduction to Symbolic Dynamics and Coding. Cambridge University Press, Cambridge, 1995.CrossRefGoogle Scholar
Lothaire, M.. Algebraic Combinatorics on Words (Encyclopedia of Mathematics and its Applications, 90). Cambridge University Press, Cambridge, 2002.CrossRefGoogle Scholar
Mignosi, F. and Séébold, P.. If a D0L language is k-power free then it is circular. Automata, Languages and Programming, 20th International Colloquium (Lecture Notes in Computer Science, 700). Springer, Berlin, 1993, pp. 507518.CrossRefGoogle Scholar
Mignosi, F., Restivo, A. and Sciortino, M.. Words and forbidden factors. Theoret. Comput. Sci. 273 (2002), 99117.CrossRefGoogle Scholar
Mossé, B.. Puissances de mots et reconnaissabilité des points fixes d’une substitution. Theoret. Comput. Sci. 99 (1992), 327334.CrossRefGoogle Scholar
Shallit, J.. Fife’s theorem revisited. Developments in Language Theory, 15th Int. Conf., DLT 2011 (Lecture Notes in Computer Science, 6795). Springer, Berlin, 2011, pp. 397405.Google Scholar
Shur, A.. Combinatorial complexity of rational languages. Discr. Anal. Oper. Res., Ser. 1 12(2) (2005), 7899 (in Russian).Google Scholar