Below you can see a list of past talks at the Logic Seminar in this season. For forthcoming talks, see the main page.
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.
Thursday, March 27, 2025
Cezar Câmpeanu (University of Prince Edward Island)
Distinguishability Operation, Properties and Perspectives
Abstract:
The distinguishability operation was formally introduced by C. Câmpeanu, N. Moreira, and R. Reis in a paper presented in Kassel, Germany, at NCMA 2014. However, distinguishing between words and states was also considered in some informal way in a paper by E. F. Moore in 1959. This approach has inspired defining a new distinguishability operation in 2024, a result published in the Theoretical Computer Science Journal. In this talk, the historical perspective of this operation will be presented, including future developments, its properties, and the state complexity of this operation on regular languages.
Thursday, March 13, 2025
Mihai Prunescu (University of Bucharest and IMAR and ILDS)
Applications of C-recursive sequences to number theory
Abstract:
We emphasize some applications of C-recursive sequences in number theory, including the solutions of the Pell equation, the computation of the greatest common divisor of two natural numbers, and counting Mersenne primes (respectively Fermat primes). Based on joint work with Lorenzo Sauras-Altuzarra and with Joseph Shunia and on work in progress.
Thursday, February 27, 2025
Marian Călborean (University of Bucharest)
Trees, algorithms and logics II: Theoretical issues raised by a full theorem prover for Graham Priest’s An Introduction to Non-classical Logic
Abstract:
Following the “Logic and software” 2024 course (Faculty of Philosophy, Bucharest), a theorem prover written in Rust was developed for most of the numerous logics (propositional and quantified) in Graham Priest’s 2008 An Introduction to Non Classical Logic: From if to is which use the tableaux method of proof (Beth 1955). Theoretical issues include soundness and completeness, efficiency and its measurement, the philosophical adequacy of the programmed notion of logic, the reducing of an alternative try-and-error procedure to SAT and a general framework of generating logics based on the calculator structure. This is joint work with Andrei Dobrescu.
Thursday, December 12, 2024
Adriana Bălan (National University of Science and Technology Politehnica Bucharest)
Regularity and complete distributivity in fuzzy metric spaces and formal contexts
Abstract:
Invertibility is an ubiquitous concept in Mathematics. In this talk, I will discuss the relationship between two seemingly unrelated notions of invertibility: regularity of multi-valued relations and complete distributivity of (complete) fuzzy metric spaces.
References:
[1] A. Bălan, On the tensor product of quantale-enriched completely distributive categories. Accepted for publication in Fundamental Structures in Computational and Pure Mathematics, Trends in Mathematics, Springer (2025).
Thursday, December 5, 2024
Andrei Sipoș (University of Bucharest and IMAR)
Around Herbrand’s Theorem II
Abstract:
We present our extension [2] to first-order arithmetic of Gerhardy and Kohlenbach’s proof [1] of Herbrand’s Theorem.
References:
[1] P. Gerhardy, U. Kohlenbach, Extracting Herbrand disjunctions by functional interpretation. Arch. Math. Logic 44, 633–644, 2005.
[2] A. Sipoș, On extracting variable Herbrand disjunctions. Studia Logica 110, 1115–1134, 2022.
Thursday, November 28, 2024
Andrei Sipoș (University of Bucharest and IMAR)
Around Herbrand’s Theorem I
Abstract:
We present Gerhardy and Kohlenbach’s proof [1] of Herbrand’s Theorem for first-order logic, which uses the Dialectica interpretation.
References:
[1] P. Gerhardy, U. Kohlenbach, Extracting Herbrand disjunctions by functional interpretation. Arch. Math. Logic 44, 633–644, 2005.
Thursday, November 21, 2024
Dafina Trufaș (University of Bucharest and ILDS)
Intuitionistic propositional logic II
Abstract:
We present two proofs of the completeness theorem for Intuitionistic Propositional Logic, corresponding to Kripke and to Heyting algebras semantics, respectively. Furthermore, the equivalence between the two validity notions is established.
Thursday, November 14, 2024
Dafina Trufaș (University of Bucharest and ILDS)
Intuitionistic propositional logic I
Abstract:
We present two proofs of the completeness theorem for Intuitionistic Propositional Logic, corresponding to Kripke and to Heyting algebras semantics, respectively. Furthermore, the equivalence between the two validity notions is established.
Thursday, October 31, 2024
Mihai Prunescu (University of Bucharest and IMAR and ILDS)
Arithmetic Terms III
Abstract:
We present other two representations of the C-recursive sequences by the speaker and new approaches to the prime numbers. The latter is joint work in progress with Lorenzo Sauras-Altuzarra and Joseph Shunia.
Thursday, October 17, 2024
Horațiu Cheval (University of Bucharest and ILDS)
Proof mining and applications to optimization and nonlinear analysis
Abstract:
We present the main results from [1], obtained as part of the program of proof mining, consisting of quantitative information on the asymptotic behavior of iterations from optimization and nonlinear analysis. We begin with a brief introduction to proof mining, after which we present results concerning the Tikhonov-Mann and modified Halpern iterations for finding fixed points of nonexpansive mappings in a very general nonlinear setting, where the main quantitative content we get takes the form of uniform rates of asymptotic regularity. This then generalizes to iterations for approximating common fixed points of families of nonexpansive mappings, for which we again compute rates of asymptotic regularity, as well as rates of metastability. Finally, we obtain linear rates of asymptotic regularity for a variety of iterations encountered in the optimization literature.
References:
[1] H. Cheval. Proof mining and applications to optimization and nonlinear analysis. PhD Thesis, submitted, 2024.