Logic Seminar

The Logic Seminar is a joint LOS/IMAR/ILDS seminar, featuring talks on mathematical logic, philosophical logic and logical aspects of computer science.

All seminars, except where otherwise indicated, will be on Thursdays between 14:00 and 16:00, Bucharest time. The seminars are held locally at Hall 214 (“Google”) of the Faculty of Mathematics and Computer Science, University of Bucharest, but can also be occasionally held remotely.

To receive announcements about the seminar, please send an email to logic-seminar@ilds.ro.

Organizers: Laurențiu Leuștean, Andrei Sipoș

Past Talks in 2024-2025

Thursday, April 10, 2025

Gabriel Istrate (University of Bucharest)

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.

Past Seminars