2026-08-21T18:34:53Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27405 2026-08-21T14:42:38Z ddc:004 open_access

Constant-Time Dynamic Enumeration of Word Infixes in a Regular Language Amarilli, Antoine Dziadek, Sven Segoufin, Luc regular language dynamic membership enumeration infix ZG automata For a fixed regular language L, the enumeration of L-infixes is the following task: we are given an input word w = a₁ ⋯ a_n and we must enumerate the infixes of w that belong to L, i.e., the pairs i ≤ j such that a_i ⋯ a_j ∈ L. We are interested in dynamic enumeration of L-infixes, where we must additionally support letter substitution updates on w (e.g., "replace the i-th letter of w by a letter a"). Each update changes the set of infixes to enumerate, and resets the enumeration state. We study for which regular languages L we can perform dynamic enumeration of L-infixes in constant delay (i.e., the next infix is always produced in constant time) and constant additional memory throughout the enumeration, while supporting each update in constant time. We show that, for languages L with a neutral letter, if the language L belongs to the class ZG and is extensible (i.e., if u ∈ L and u is a factor of v then v ∈ L), then dynamic enumeration of L-infixes can be achieved with a simple algorithm that ensures constant-time updates and constant delay, but not constant additional memory. Our main contribution is then to show an algorithm that additionally uses only constant additional memory, and applies to a more general class of semi-extensible ZG languages for which we give several equivalent characterizations. We further discuss whether our results can be generalized to larger language classes and show some (conditional) lower bounds. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Antoine Amarilli and Sven Dziadek and Luc Segoufin 2026 Is Part Of LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2026.24 urn:nbn:de:0030-drops-274050 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.24 eng https://creativecommons.org/licenses/by/4.0/legalcode