2026-10-05T13:47:21Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23548 2025-10-02T10:58:29Z ddc:004 open_access

A Tropical Approach to the Compositional Piecewise Complexity of Words and Compressed Words Schnoebelen, Philippe Veron, J. Vialard, Isa Tropical semiring Subwords and subsequences piecewise complexity SLP-compressed words We express the piecewise complexity of words using tools and concepts from tropical algebra. This allows us to define a notion of piecewise signature of a word that has size log(n)m^{O(1)} where m is the alphabet size and n is the length of the word. The piecewise signature of a concatenation can be computed from the signatures of its components, allowing a polynomial-time algorithm for computing the piecewise complexity of SLP-compressed words. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Philippe Schnoebelen and J. Veron and Isa Vialard 2025 Is Part Of LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2025.171 urn:nbn:de:0030-drops-235481 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.171 eng https://creativecommons.org/licenses/by/4.0/legalcode