On the piecewise complexity of words and periodic words

2023/11/26 by Praveen, M., Schnoebelen, Philippe, Vialard, Isa +1 · 1 citation
#FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL)

paper · doi:10.48550/arxiv.2311.15431

Abstract

The piecewise complexity h(u) of a word is the minimal length of subwords needed to exactly characterise u. Its piecewise minimality index ρ(u) is the smallest length k such that u is minimal among its order-k class [u]_k in Simon's congruence. We study these two measures and provide efficient algorithms for computing h(u) and ρ(u). We also provide efficient algorithms for the case where u is a periodic word, of the form u=vⁿ

Cited by

• Linear Time Subsequence and Supersequence Regex Matching

Related

• On the piecewise complexity of words
• Testing Simon's congruence
• On the index of Simon's congruence for piecewise testability
• On the shape of subword complexity sequences of finite words
• Cyclic Complexity of Words