Logic Seminar
Organizer: Laurențiu Leuștean
Talks
Wednesday, June 11, 2014
10:30 am in Hall "Miron Nicolescu", IMAR
JeanYves Beziau (Federal University of Rio de Janeiro)
Paraconsistent Logic, the Square of Opposition and
Universal Logic
Abstract: In this talk I will explain how I have started my research in mathematical logic on paraconsistent logics,
logics which rejected the principle of non contradiction, mainly developed by the Brazilian logician Newton da
Costa. These logics are challenging both from the mathematical and the philosophical point of view, the question is
to have a proper understanding of the notions of contradiction and negation. The theory of oppositions emerging
from the square of opposition is a useful tool giving a general perspective that is fully reached in the realm of
universal logic,a general theory of logical systems that has been developed these last 20 years.
Tuesday, June 3, 2014
15:00 am in Room 309310 "Gheorghe Vranceanu", IMAR
Florin Manea (Kiel University)
Finding generalised periodicities in words
Abstract
Tuesday, May 20, 2014
15:00 am in Room 309310 "Gheorghe Vranceanu", IMAR
Serban Basarab (IMAR)
The ubiquity of trees: from relative quantifier elimination to deformations of
groups and rings II
Tuesday, May 13, 2014
15:00 am in Room 309310 "Gheorghe Vranceanu", IMAR
Serban Basarab (IMAR)
The ubiquity of trees: from relative quantifier elimination to deformations of
groups and rings
Abstract: We consider some relevant contexts where trees and more general arboreal
structures are induced by natural deformations of certain algebraic structures
as valued fields, Prüfer ring extensions, etc. Some intimate connections
between the induced arboreal structures and the arithmetic and geometric
properties of the original algebraic structures are discussed.
References:
Serban Basarab, Embedding theorems for actions on generalized trees, I
, arXiv:1003.4652 [math.GR], 2010.
Serban Basarab, Arithmeticarboreal residue structures induced
by Prüfer extensions : An axiomatic approach, arXiv:1011.0855 [math.AC], 2010.
Serban Basarab, A more general framework for coGalois theory,
arXiv:1311.0697 [math.GR], 2013.
Tuesday, May 6, 2014
15:00 am in Room 309310 "Gheorghe Vranceanu", IMAR
Silviu Velica (Faculty of Philosophy, University of Bucharest)
Independencefriendly logic and the Monty Hall problem
Abstract: In the first part of the presentation, I will give a short introduction
to gametheoretical semantics for firstorder logic, then move on to the semantics for independencefriendly logic.
After this introduction, a short discussion on the Monty Hall problem will follow, showing how it has been solved before.
Finally, I will give the formalization of the Monty Hall scenario and prove that the resulting formula has the same
value as the probability distribution in the standard solution.
Tuesday, April 29, 2014
15:00 am in Room 309310 "Gheorghe Vranceanu", IMAR
Sergiu Rudeanu (Faculty of Mathematics and Computer Science, University of Bucharest)
Boolean syllogistics
Abstract: The traditional classification of syllogisms into 4 figures is pertinent
to the formal aspect of reasoning rather than to its essence. It seems to us more appropriate
to observe that there are 32 syllogistic moods (grouped, if required, into 4 classes corresponding
to 4 general formulae, each of them including 8 moods); each mood can be given 4 equivalent forms,
corresponding to the 4 traditional figures. A few concluding remarks are devoted to the criticisms
of the moods Darapti, Felapton, Bramantip and Fesapo.
Tuesday, April 1, 2014
15:00 am in Room 309310 "Gheorghe Vranceanu", IMAR
Mihai Prunescu (IMAR)
Some progress in 3SAT
Abstract: Matthias Müller published on the net a C++ code and a text describing the implemented algorithm.
He claimed that the algorithm "maybe" solves the NPcomplete problem 3SAT in polynomial time.
The program decided correctly so far the solvability for all instances that have been checked.
This intriguing fact must be understood.
In order to achieve this goal, we introduce the graph of all possible 3SAT clauses with edges connecting every two nonconflicting clauses.
We prove that a 3SAT instance I is satisfiable if and only if there is a maximal clique of the clause graph that does not intersect I.
References:
Mihai Prunescu, About a surprising computer program of Matthias Müller, preprint, 2014.
Tuesday, March 18, 2014
15:00 am in Room 309310 "Gheorghe Vranceanu", IMAR
Serafina Lapenta (Universita' degli studi della Basilicata)
BakerBeynon duality for Riesz MValgebras
Abstract
Thursday, March 6, 2014
12:00 am in Room 309310 "Gheorghe Vranceanu", IMAR
Ruxandra Olimid (Faculty of Mathematics and Computer Science, University of Bucharest)
Secret sharing and secretsharing based group key establishment
Abstract: First, we introduce the cryptographic notion of secret sharing, describe a
few simple schemes and reason about their security. Second, we review some recent secret
sharingbased group key establishment protocols and explore their vulnerabilities.
Thursday, February 6, 2014
12:00 am in Room 309310 "Gheorghe Vranceanu", IMAR
Alexandru Dragomir (Faculty of Philosophy, University of Bucharest)
Public Announcement Logic
Abstract: (1) I will begin my presentation with a very short introduction to Epistemic
Logic. (2) Further, I will present the syntax and semantics of Public Announcement Logic, with
an emphasis on the notion of modeltransformers, and the solution to the Muddy Children Puzzle
(as they are presented in H. van Ditmarsch, B. Kooi and W. van der Hoek's "Dynamic Epistemic Logic").
(3) I will present T. Hoshi's notion of a protocol for Public Announcement Logic and analyze the idea
of introducing operators for changing protocols.
Thursday, January 23, 2014
12:00 am in Room 309310 "Gheorghe Vranceanu", IMAR
Mihai Prunescu (IMAR)
Unit Cost Complexity II
Thursday, January 16, 2014
12:00 am in Room 309310 "Gheorghe Vranceanu", IMAR
Mihai Prunescu (IMAR)
Unit Cost Complexity I
Abstract: We present the complexity approach started by Blum, Cooker, Shub and Smale
for the reals and generalized by Poizat for arbitrary structures. In this approach, a structure
has P = NP for unit cost computations if and only if there is an internal algorithm of fast
(polynomial time) elimination for the existential quantifier block in formulas E x f(x, y, a),
where a is a parameter tuple from the structure. Infinite abelian groups and infinite boolean
rings have the property P =/= NP. Unit cost Knapsack over ordered abelian semigroups with
cancelation is in P if and only if P = NP classically. If time permits, we will sketch the
construction of a structure with the property P = NP in the sense of unit cost computations.
References:
Mihai Prunescu, Fast
Quantifier Elimination Means P = NP . Final version in:
Lecture Notes in Computer Science 3988 (2006), 459470.
Mihai Prunescu,
Structure with fast elimination of quantifiers . Final version in: J. Symbolic Logic 71 (2006), 321328.
Thursday, December 19, 2013
12:00 am in Room 309310 "Gheorghe Vranceanu", IMAR
Ionut Tutu
(Royal Holloway University of London)
Modeltheoretic foundations of logic programming
Abstract: We review the mathematical foundations of conventional logic programming and advance an
abstract algebraic framework for it that is grounded on the institution theory of Goguen and Burstall.
The proposed conceptual structure relies on institutional generalisations of logicprogramming notions such
as variable, substitution, local sentence, interpretation of variables, and satisfaction. It supports in this way not only a
definition of logic programs that is independent of the underlying institution, but also the development of an
equally abstract description of their execution.
Thursday, December 12, 2013
12:00 am in Room 309310 "Gheorghe Vranceanu", IMAR
Claudia Chirita (Faculty of Mathematics and Computer Science, University of Bucharest)
Introduction to Descriptive Complexity III
Thursday, December 5, 2013
12:00 am in Room 309310 "Gheorghe Vranceanu", IMAR
Claudia Chirita (Faculty of Mathematics and Computer Science, University of Bucharest)
Introduction to Descriptive Complexity II
Thursday, November 28, 2013
12:00 am in Room 309310 "Gheorghe Vranceanu", IMAR
Claudia Chirita (Faculty of Mathematics and Computer Science, University of Bucharest)
Introduction to Descriptive Complexity
Abstract: We briefly review some of the most important results in descriptive
complexity theory, an area of research whose purpose is to describe complexity classes in
terms of modeltheoretic constructs (mainly fragments of first or secondorder logic).
Our presentation is aimed towards a logical perspective on the P vs. NP problem.
Thursday, November 14, 2013
12:00 am in Room 309310 "Gheorghe Vranceanu", IMAR
Mihai Prunescu (IMAR)
Recurent and automatic ndimensional sequences over finite alphabets II
Thursday, November 14, 2013
12:00 am in Room 309310 "Gheorghe Vranceanu", IMAR
Mihai Prunescu (IMAR)
Recurent and automatic ndimensional sequences over finite alphabets II
Thursday, November 7, 2013
12:00 am in Room 309310 "Gheorghe Vranceanu", IMAR
Mihai Prunescu (IMAR)
Recurent and automatic ndimensional sequences over finite
alphabets
Abstract: Recurrent ndimensional sequences over finite alphabets generalize objects
appearing in computer experiments, like evolution diagrams of cellular automata. This area of
research developed constantly in the last 60 years and contains classical works like those of
Wilson, Conway or Wolfram's "new kind of science", but did never become a mainstream. This can
be partially explained by the fact that we lack mathematical notions to describe or approximate
phenomena which are intuitively seen or recognized in those objects. Words like "fractal", "chaos",
"dynamics", "attractor" are often used in commenting or describing such phenomena, but mostly
in a nonrigorous way. Another reason might lie in the fact that recurrent ndimensional
sequences build a Turingcomplete class of objects, so the variety inside the class is really big.
Automatic ndimensional sequences are sequences over finite alphabets produced by deterministic
finite automata with output, in the sense that a value a(x) is obtained after pushing in
the automaton a word representing the coordinates x in some chosen base of numeration.
It is not known which recurrent ndimensional sequences are automatic, but some progress in
this direction will be presented in this talk. Also some some remarcable recurrent 2dimensional sequences will be shown.
Thursday, October 31, 2013
12:00 am in Room 306307 "Constantin Banica", IMAR
Tommaso Flaminio (Dept. of Theoretical and Applied Science,
Universita dell'Insubria)
A general approach to de Finetti's criterion for uncertainty measures on manyvalued events
Abstract
