2026-09-08T02:22:00Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26414 2026-09-05T19:42:52Z ddc:004 open_access

Permutation Patterns in Streams Berendsohn, Benjamin Aram permutations pattern matching streaming Permutation patterns and pattern avoidance are central, well-studied concepts in combinatorics and computer science. Given two permutations τ and π, the pattern matching problem (PPM) asks whether τ contains π. This problem arises in various contexts in computer science and statistics and has been studied extensively in exact-, parameterized-, approximate-, property-testing- and other formulations. In this paper, we study pattern matching in a streaming setting, when the input τ is revealed sequentially, one element at a time. There is extensive work on the space complexity of various statistics in streams of integers. The novelty of our setting is that the input stream is a permutation, which allows inferring some information about future inputs. Our algorithms crucially take advantage of this fact, while existing lower bound techniques become difficult to apply. We show that the complexity of the problem changes dramatically depending on the pattern π. The space requirement is: - Θ(klog{n}) for the monotone patterns π = 12…k, or π = k…21, - 𝒪(√{nlog{n}}) for π ∈ {312,132}, - 𝒪(√n log n) for π ∈ {231,213}, - Θ̃_π(n) for all other π. If τ is an arbitrary sequence of integers (not necessary a permutation), we show that the complexity is Θ̃_π(n) in all except the first (monotone) cases. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Benjamin Aram Berendsohn 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.25 urn:nbn:de:0030-drops-264144 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.25 eng https://creativecommons.org/licenses/by/4.0/legalcode