Normalization of ternary generalized pseudostandard words

Abstract: This paper focuses on generalized pseudostandard words, defined by de Luca and De Luca in 2006. In every step of the construction, the involutory antimorphism to be applied for the pseudopalindromic closure changes and is given by a so called directive bi-sequence. The concept of a normalized form of directive bi-sequences was introduced by Blondin-Mass'e et al. in 2013 and an algorithm for finding the normalized directive bi-sequence over a binary alphabet was provided. In this paper, we present an algorithm to find the normalized form of any directive bi-sequence over a ternary alphabet. Moreover, the algorithm was implemented in Python language and carefully tested, and is now publicly available in a module for working with ternary generalized pseudostandard words.

Review text

The paper deals with generalized pseudostandard words. Generalized pseudostandard words are defined as follows: Let \(\Delta=(\delta_n)\) be an infinite sequence of letters and let \(\Theta=(\theta_n)\) be an infinite sequence of involutory antimorphisms. The generalized pseudostandard word generated by the directive bi-sequence \((\Delta,\Theta)\) is the limit of the sequence of words \((w_n)\), where \(w_0\) is the empty word and \(w_{n+1} \) is the shortest \(\theta_{n+1}\)-palindrome starting with \(w_n\cdot \delta_{n+1}\). Generalized pseudostandard words are a generalization of standard Sturmian, standard episturmian and pseudostandard words. A generalized pseudostandard word may be generated by different directive bi-sequences. The directive bi-sequence \((\Delta,\Theta)\) is called normalized if the sequence \((w_n)\) contains all pseudopalindromic prefixes of its limit. Every directive bi-sequence can be normalized; the problem is therefore to give an algorithmic procedure to find the normalization. In this paper, the authors give such an algorithm in the case of an alphabet of size \(3\), thus generalizing the solution given for binary alphabets in [\textit{A. B. Massé} et al., J. Integer Seq. 16, No. 2, Article 13.2.11, 28 p. (2013; Zbl 1310.68175)]. Alongside the theoretical work, the authors implemented and tested the new normalization algorithm. The documented code and examples are publicly available at \url{https://github.com/velkater/tgpc}.

Recommendations

Cites work

Cited in

(3)

Describes a project that uses

Uses Software

Python

This page was built for publication: Normalization of ternary generalized pseudostandard words

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2420613)