The piecewise complexity h(u) of a word is the minimal length of subwords needed to exactly characterise u. Its piecewise minimality index <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="236_2025_480_Article_IEq1.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="33" /> </InlineMediaObject> <EquationSource Format="TEX">$\rho (u)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>ρ</mi> <mo stretchy="false">(</mo> <mi>u</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> is the smallest length k such that u is minimal among its order-k class <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="236_2025_480_Article_IEq2.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="28" /> </InlineMediaObject> <EquationSource Format="TEX">$[u]_k$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mrow> <mo stretchy="false">[</mo> <mi>u</mi> <mo stretchy="false">]</mo> </mrow> <mi>k</mi> </msub> </math></EquationSource> </InlineEquation> in Simon’s congruence. We initiate a study of these two descriptive complexity measures. Among other results, we provide efficient algorithms for computing h(u) and <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="236_2025_480_Article_IEq3.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="33" /> </InlineMediaObject> <EquationSource Format="TEX">$\rho (u)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>ρ</mi> <mo stretchy="false">(</mo> <mi>u</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> for a given word u.

On the piecewise complexity of words

期刊论文
发表日期：

2025年2月18日

查看全文

Philippe Schnoebelen,
Isa Vialard

摘要

The piecewise complexity h(u) of a word is the minimal length of subwords needed to exactly characterise u. Its piecewise minimality index $\rho (u)$ $ρ (u)$ is the smallest length k such that u is minimal among its order-k class $[u]_k$ ${[u]}_{k}$ in Simon’s congruence. We initiate a study of these two descriptive complexity measures. Among other results, we provide efficient algorithms for computing h(u) and $\rho (u)$ $ρ (u)$ for a given word u.