Normalization of ternary generalized pseudostandard words

DOI10.1016/J.TCS.2019.02.010MaRDI QIDQ2420613zbMATH OpenOpenAlexWikidataFDO

Authors Josef Florian, Tereza Veselá, L'ubomíra Dvořáková

Publication date 6 June 2019

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1807.07248

zbMATH Keywords

palindromepseudopalindromepalindromic closurepseudostandard wordstandard Sturmian wordgeneralized pseudostandard wordstandard episturmian word

Mathematics Subject Classification ID

Combinatorics on words (68R15)

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.

Recommendations

• On generalized pseudostandard words over binary alphabets
• Palindromic closures using multiple antimorphisms
• On periodicity of generalized pseudostandard words
• A new estimate on complexity of binary generalized pseudostandard words
• On some problems related to palindrome closure
• Reconstructing words from a \(\sigma\)-palindromic language
• Bubble-flip -- a new generation algorithm for prefix normal words
• On the fixed points of the iterated pseudopalindromic closure operator
• Bubble-flip -- a new generation algorithm for prefix normal words
• The pseudopalindromic completion of regular languages

Cites work

• A new estimate on complexity of binary generalized pseudostandard words
• Episturmian words and some constructions of de Luca and Rauzy
• Fixed points of morphisms among binary generalized pseudostandard words
• On generalized pseudostandard words over binary alphabets
• On periodicity of generalized pseudostandard words
• On some problems related to palindrome closure
• On the fixed points of the iterated pseudopalindromic closure operator
• Palindromic closures using multiple antimorphisms
• Pseudopalindrome closure operators in free monoids
• Sturmian words: structure, combinatorics, and their arithmetics

Cited in

(3)

• On periodicity of generalized pseudostandard words
• tgpc
• On generalized pseudostandard words over binary alphabets

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)