Search Results

Documents authored by Veron, J.

Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2025.171
A Tropical Approach to the Compositional Piecewise Complexity of Words and Compressed Words

Authors: Philippe Schnoebelen, J. Veron, and Isa Vialard

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
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.
Cite as

Philippe Schnoebelen, J. Veron, and Isa Vialard. A Tropical Approach to the Compositional Piecewise Complexity of Words and Compressed Words. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 171:1-171:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{schnoebelen_et_al:LIPIcs.ICALP.2025.171,
  author =	{Schnoebelen, Philippe and Veron, J. and Vialard, Isa},
  title =	{{A Tropical Approach to the Compositional Piecewise Complexity of Words and Compressed Words}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{171:1--171:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.171},
  URN =		{urn:nbn:de:0030-drops-235481},
  doi =		{10.4230/LIPIcs.ICALP.2025.171},
  annote =	{Keywords: Tropical semiring, Subwords and subsequences, piecewise complexity, SLP-compressed words}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact