Logic Seminar

---

Jean-Yves 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.

Florin Manea (Kiel University)
Finding generalised periodicities in words
Abstract

Serban Basarab (IMAR)
The ubiquity of trees: from relative quantifier elimination to deformations of groups and rings II

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, Arithmetic-arboreal 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.

Silviu Velica (Faculty of Philosophy, University of Bucharest)
Independence-friendly logic and the Monty Hall problem

Sergiu Rudeanu (Faculty of Mathematics and Computer Science, University of Bucharest)
Boolean syllogistics

Mihai Prunescu (IMAR)
Some progress in 3-SAT

Serafina Lapenta (Universita' degli studi della Basilicata)
Baker-Beynon duality for Riesz MV-algebras
Abstract

Ruxandra Olimid (Faculty of Mathematics and Computer Science, University of Bucharest)
Secret sharing and secret-sharing 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 sharing-based group key establishment protocols and explore their vulnerabilities.

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 model-transformers, 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.

Mihai Prunescu (IMAR)
Unit Cost Complexity II

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), 459-470.
Mihai Prunescu, Structure with fast elimination of quantifiers . Final version in: J. Symbolic Logic 71 (2006), 321-328.

Ionut Tutu (Royal Holloway University of London)
Model-theoretic 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 logic-programming 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.

Claudia Chirita (Faculty of Mathematics and Computer Science, University of Bucharest)
Introduction to Descriptive Complexity III

Claudia Chirita (Faculty of Mathematics and Computer Science, University of Bucharest)
Introduction to Descriptive Complexity II

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 model-theoretic constructs (mainly fragments of first- or second-order logic). Our presentation is aimed towards a logical perspective on the P vs. NP problem.

Mihai Prunescu (IMAR)
Recurent and automatic n-dimensional sequences over finite alphabets II

Mihai Prunescu (IMAR)
Recurent and automatic n-dimensional sequences over finite alphabets II

Mihai Prunescu (IMAR)
Recurent and automatic n-dimensional sequences over finite alphabets
Abstract: Recurrent n-dimensional 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 non-rigorous way. Another reason might lie in the fact that recurrent n-dimensional sequences build a Turing-complete class of objects, so the variety inside the class is really big.

Automatic n-dimensional 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 n-dimensional sequences are automatic, but some progress in this direction will be presented in this talk. Also some some remarcable recurrent 2-dimensional sequences will be shown.

Tommaso Flaminio (Dept. of Theoretical and Applied Science, Universita dell'Insubria)
A general approach to de Finetti's criterion for uncertainty measures on many-valued events
Abstract