# Logic, Algebra and Computer Science. Helena Rasiowa

## A Minisemester at Warsaw, December 2--22, 1996.

### Mohua Banerjee

Machine Intelligence Unit, Indian Statistical Institute, Calcutta
E-mail: miux9503@isical.ernet.in

Awfully cold, but sunny days. Over a 100 invited speakers from about 25 countries gathered at the Stefan Banach International Mathematical Center, to pay tribute to the memory of Helena Rasiowa. It was the first meeting on such a large scale since she passed away in 1994. The main organizers : Damian Niwi\'nski, Andrzej Skowron of the University of Warsaw, and Lech Polkowski of the Warsaw University of Technology.

The atmosphere was easy---unlike that in a standard conference---and the long span of the meeting gave one a lot of scope for academic interaction. Quite a few participants were close associates/students of Rasiowa, and so during conversations, one caught glimpses of the great personality as well. It was a privilege to be a part of the assembly and also, to present our work on rough logic that follows Rasiowa's style of investigation.

The participants were accommodated either at the Banach Center, or hotels of the University of Warsaw, and the organizers took great care to see to the comfort of each one (in particular that none froze!). In general too, considering the extremely hard time that the Polish are going through, one was amazed at the warmth exuded and help extended, even by the common person on the street.

An average day in the semester had two sessions including 6-8 speakers, getting at least 45 minutes each, and an {\it atelier\/} in the end---a follow-up session, speakers for which were decided by the participants themselves. The semester consisted of the following categories of talks: constructive mathematics, automated reasoning, logics of programs, modal and epistemic logic, multi-valued logic, philosophical roots of logic, lambda calculus, proof theory, finite model theory, algebraic and categorical methods in logic, reasoning about knowledge in intelligent systems, computation theory, computational complexity and concurrency. The list at the end of this report may give a sense of the variety of topics covered.

Among the audience, we had a number of bright young students (Polish, and others), shooting questions, and enjoying the proceedings. I remember a nice evening with some of them, trudging through the ice to a concert at the renowned Chopin School of Music, and then being amply rewarded by the concert itself---three well-performed piano concertos by students of the School. We also had long exchanges about the problems in our countries, specially those in the academic spheres. There did not seem to be many differences.

The opening lecture of the semester was delivered by Zdzislaw Pawlak, on rough sets: theory and applications. It was, as usual with the father' of rough sets, excellent. This was followed by an equally good tutorial by Petr Hajek, on deductive systems of fuzzy logic. He talked of fuzzy logic in the narrow' sense, which can be put under the umbrella of many-valued logics. Later, there were two more tutorials, by Jan Zytkow (principles and algorithms of automated discovery) and Erzsebet Csuhaj-Varju (formal language theoretic methods of parallel and distributed computing).

A few experts in linguistics graced the scene. Solomon Marcus, one of the two most senior participants (the other being Andrzej Grzegorczyk, contemporary of Rasiowa in the Warsaw School---he gave a talk against antipsychologism), beautifully outlined work on texts, contexts, intertexts and hypertexts, and dwelt upon the problem of bridging the four. The work of Maria-Semeniuk Polkowska, a student of Rasiowa, on distributional-algebraic models of natural language was presented in absentia. W. Buszkowski discussed minimal categorial grammars compatible with linguistic data and also put forth an important survey of various proof-theoretic methods applied in linguistics. Nguyen Cat Ho (a doctoral student of Rasiowa) spoke on linguistic-valued logic and deductive methods in linguistic reasoning about knowledge with vague concepts.

One full session was devoted to category theory. Adam Obtulowicz's work stood out---it was on triangular logic: a formal method of proving theorems for partial toposes. One may also mention the presentation by Mascari on a categorical approach to normalization of proofs (deriving from Girard's geometry of interaction).

The only talk on molecular computing was by Gheorghe Paun. He presented three classes of models based on matching, splicing and insertion/deletion, and characterizations of r.e. languages in each case, with the final claim of a theoretical proof of the possibility of designing universal programmable molecular computers.

Rudolph Wille added an interesting dimension to the meeting. He criticized the current frame of mathematical logic, spoke about restructuring it, activating more connections to reality. His formalizations were based on ideas developed by his group in formal concept analysis, while the philosophical basis was provided by Pragmatism of Ch. S. Peirce. Naturally, the hard-core' mathematicians and scientists protested, and somewhat rudely, one felt. That amounted to shutting out any dialogue, much to the (perceptible) dismay of Wille.

A notable piece of work was presented by Lech Polkowski and Andrzej Skowron (a scientific foster-child' of Rasiowa) on rough mereology---a theory of the relation of being a part in a degree. One may recall that classical mereology was proposed by Stanislaw Le\'sniewski, where the relation being a part of' is fundamental, in contrast to the primitive relation being an element of' in Cantor's set theory. Rough mereology is inspired by rough set theory---very naturally so, as in the perspective of this theory, one is able to perceive not individual constructs, but their collections. The basic notions here are of partial containment and a similarity measure among objects. Applications are sought in the control of complex systems.

The area of modal logic (pure and applied) had some big names. Arrow logic was dealt with in detail by Dimiter Vakarelov (another doctoral student of Rasiowa) ---he presented the Sofia approach. Maksimova (an associate of Rasiowa) discussed interrelationships of logical, algebraic and semantical properties for intermediate and normal modal logics. Farinas del Cerro deliberated on modal logic representations of diagrams and geometries. And there was Jon Barwise, speaking to a packed house. He gave two talks---one on interpolation, preservation and pebble games, the other on modal logic and non-well-founded sets. The latter, I suspect, most found more interesting (that there were not too many takers, is of course another matter). He sketched some neat theorems about an anti-founded universe, modal logic being used as a logic of description of sets in it.

The evening of December~18 saw a round table discussion chaired by Jan Komorowski, on how to teach logic. Participants described the courses in and the general attitude towards logic in their countries, after which there was a debate on an ideal course in logic. Some voiced an interesting idea of setting up a kind of logic lab, where students would learn to appreciate logic from the standpoint of its applications to real-life problems. This, of course, did not arouse much enthusiasm among the section wanting to teach logic in its entirety.

The session I enjoyed the most was the one on Saturday, December~14 (not to speak of the snug party afterwards!)---it was a retrospective session featuring Andrzej Skowron, Jan Wolenski and Albert Dragalin. Skowron emphasized that a logician should not stop at a completeness theorem' and ignore the fact that most of the logics being played around with are simply of no use while reasoning with real data (needless to say, the idea of a logic lab was supported by him). Dragalin's topic was foundations of mathematics today'---he listed some new trends that have arisen out of either impredicativity, lack of constructivity, or lack of feasibility in classical mathematics. Amidst these proceedings, a bouquet arrived from the colleagues and friends of Rasiowa at the University of North Carolina---that was a touching moment indeed.

The talk by Wolenski on the Polish School of logic was marvelous, like a documentary. It was a rapt audience, picturing the inception of the School, its flourish, the tensions within, and the contribution to the world of logic through the likes of Twardowski (the initiator---1895, Lvov), Lukasiewicz, Sierpinski, Ajdukiewicz, Le\'sniewski, Jaskowski, Kuratowski, Mazurkiewicz, Tarski, Lindenbaum, Mostowski, Sikorski (to name only a few!), and Rasiowa. The prime force driving the largest group of logicians working together in the world for such a long time, even through the strife-torn times of the war, is possibly best understood by the words of Tarski: religion divides people, logic brings them together'. Being asked to comment on the future of logic, Wolenski noted that logic was not corrupted' by computer science during the period of the School as it is now, but hoped that there were better days round the corner. `When logic would return to its pristine uselessness!', someone in the audience (tellingly) added.

And so, the three weeks flew past---wonderfully spent, notwithstanding the bitter cold (apparently the coldest December there in 30 years). Full credit to the organizers!

#### List (not exhaustive) of some more topics

• Many-valued logics
Infinite-valued resolution techniques: Daniele Mundici
Non-functionally complete n-valued systems: Luisa Iturrioz
Automated theorem proving in some n-valued systems: Piotr Borowik
• Other logics
Fixed-point logic: Joerg Flum
Recent results in logics with two variables: Martin Otto
Two-dimensional modal logics: V. Shehtman
• Proof theory
Strong normalization proofs for cut elimination in Gentzen's sequent calculi: E. Tahhan Bittar
• Algebra and logic
Links between universal algebra and logic: Bruno Courcelle
Satisfiability of inequalities in a poset: J. Tiuryn
• Constructive Mathematics
Constructive open mapping theorems: Douglas Bridges
Constructive models and applications in proof theory: Albert Dragalin
Constructivisation of non-standard analysis: Erik Palmgren
• Model theory
Finite models and finitely many variables: Anuj Dawar
Invariant definability in infinite and finite model theory: Janos Makowsky
Constructive logic and stable model reasoning: David Pearce
Large finite structures with few $L^k$-types: Martin Grohe
Feasibility in higher type: Daniel Leivant
Generalized quantifiers on finite structures: Lauri Hella
• Knowledge and belief
Reasoning and programming with knowledge and belief: T. Przymusinski
Multi-sorted preferences and belief change: Anna Gomolinska
Representation of knowledge by means of concurrent systems: Z. Suraj
• Concurrency
Synchronization and interpretation of concurrent systems: Antoni Mazurkiewicz
Algorithmic logic of concurrent processes with common memory: G. Mirkowska
Matrix representation of concurrent processes: Jozef Winkowski
• Computation theory, Complexity
Time complexity of decision trees: Mikhail Moshkov
A continuum of discrete systems: Howard Blair
Synchronized products of automata and model-checking: Andre Arnold
Survey of automorphisms of models of arithmetic: H. Kotlarski
• Logic programming, logics of programs
Herbrand's theorem for non-standard inference operations: Juergen Dix
Uncertain knowledge discovery and multi-valued logic programming: Peter Vojtas
Application of grammatical techniques in logic programming: Jan Maluszy\'nski
Automated reasoning in equational theories: L. Vigneron
Algebraic specifications and semantical properties of programs: A. Salwicki (a doctoral student of Rasiowa)
Correctness of transformations of general logic programs: Alberto Pettorossi
Partial deduction in the framework of structural synthesis of programs: Jan Komorowski
• Reasoning about knowledge in intelligent systems
Machine learning from imperfect data: Jerzy Grzymala-Busse
Information logics: Ewa Orlowska
Knowledge discovery for intelligent query answering: Zbigniew Ra\'s (son of Rasiowa)
Approximation logics: J. Stepaniuk
Quantization of real-valued attributes: Nguyen Hung Son