On April 10, 2025 at 14:00 EEST, Gabriel Istrate (University of Bucharest) will give a talk in the Logic Seminar.
Title: A Language-Theoretic Approach to the Heapability of Signed Permutations
Abstract:
We investigate a signed version of the Hammersley process, a discrete process on words related to a property of integer sequences called heapability [1]. The specific version that we investigate corresponds to a version of this property for signed sequences. We give a characterization of the words that can appear in the signed Hammersley process. In particular we show that the language of such words is the intersection of two one-counter languages.
The results in this talk (and additional references) may be found in the paper [2].
References:
[1] J. Byers, B. Heeringa, M. Mitzenmacher, G. Zervas, Heapable sequences and subseqeuences. In: Proceedings of the Eighth Workshop on Analytic Algorithmics and Combinatorics (ANALCO 2011), SIAM Press, 2011, pp. 33–44.
[2] G. Istrate, A Language-Theoretic Approach to the Heapability of Signed Permutations. Prague Stringology Conference 2024, pp. 71–85.
The talk will take place physically at FMI (Academiei 14), Hall 214 “Google”.