2026-09-27T04:28:23Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25950 2026-09-23T23:56:40Z ddc:004 open_access

On Occurrence-Preserving Morphisms Kishi, Kaisei Guo, Peaker Urbina, Cristian Bannai, Hideo Property-preserving morphisms interference-free morphisms recognizable morphisms injective morphisms Fibonacci words Thue-Morse words minimal unique substrings (MUSs) net occurrences A morphism is a mapping that transforms words through letter-wise substitution, where each symbol is consistently replaced by a fixed word. In the field of combinatorics on words, one topic that has attracted considerable attention is the characterization of morphisms that preserve specific properties, such as overlap-freeness, square-freeness, lexicographic order, and primitivity. Continuing this direction, we initiate the study on occurrence-preserving morphisms, which address the following fundamental question: given a morphism ϕ, two words u and v, and k ≥ 1, under what conditions does the number of occurrences of u in v equal the number of occurrences of ϕ^k(u) in ϕ^k(v)? To answer this question, we introduce the notion of interference-free morphisms, examine their properties, and uncover a connection to recognizable morphisms. We then present a precise characterization of occurrence-preserving morphisms in terms of interference-freeness. As applications of our characterization, we first show that there exists a bijection between the starting positions of the occurrences of u in v and those of ϕ^k(u) in ϕ^k(v). We then apply the characterization to the Fibonacci and Thue-Morse words to identify their minimal unique substrings (MUSs). Finally, we exploit the connection between MUSs and net occurrences to simplify existing proofs on net occurrences in these words. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kaisei Kishi and Peaker Guo and Cristian Urbina and Hideo Bannai 2026 Is Part Of LIPIcs, Volume 369, 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2026.24 urn:nbn:de:0030-drops-259504 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2026.24 eng https://creativecommons.org/licenses/by/4.0/legalcode