2024/12/21 by Philippe Schnoebelen, Schnoebelen, Philippe, Isa Vialard +1
Computer Science · #semigroups and automata theory #Authorship Attribution and Profiling #Coding theory and cryptography
paper · pdf · doi:10.48550/arxiv.2412.16560
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 initiate a study of these two descriptive complexity measures. Among other results we provide efficient algorithms for computing h(u) and ρ(u) for a given word u.