HELENA RASIOWA, 1917 - 1994

by

W. Bartol, E. Orłowska, A. Skowron

Mathematical Foundations of Computer Science

Helena Rasiowa has greatly contributed to the development of research in Poland on applications of logical methods in the foundations of computer science. She was one of the first to realize the great importance of mathematical logic for computer science - and at the same time she clearly saw the significance of computer science for the development of logic itself. In the last 20 years of her scientific activity she focused her efforts on the realization of this main idea through papers, seminars and research projects. Many of her students and collaborators who attended her lectures or seminars, those who wrote their PhD theses under her supervision, are now continuing the work she initiated. There remains no doubt today that she was right in the appreciation of the significance of the field. Among the authors of important research results on logical and algebraic methods in computer science the names of her students can be found quite often. Moreover, some of these important results have appeared in a journal which would not have existed without her dedication and to which she had been Editor-in-Chief for many years, i.e. Fundamenta Informaticae.

The form of this short article makes difficult a complete presentation of her achievements in the field of applications of logical and algebraic methods in computer science. She is the author of more then 30 papers, two lecture notes ([63], [72]) and an unfinished monograph in which she relates algebraic methods of non-classical logics with applications in the foundations of computer science. She was able to write eight chapters before she was taken to hospital.

Her contribution to theoretical computer science stems from her conviction that there are deep relations between methods of algebra and logic on one side and essential problems of foundations of computer science on the other. Among these problems she clearly distinguished inference methods characteristic of computer science and its applications. This conviction of hers had been supported by her results on many-valued and nonclassical logics, especially on applications of various generalizations of Post algebras to logics of programs and approximation logics.

Her investigations on logic and algebraic methods in computer science can be divided into two main streams. The first includes many-valued algorithmic logics and their applications to investigation of programs ([42-44], [51], [53-64], [69-72]), while the second is concerned with approximation logics in their relation with generalizations of Post algebras ([73-97]).

In a series of papers on algorithmic logic Rasiowa presents the results of her research on generalizations of classical algorithmic logic introduced by A.Salwicki to complex algorithms, which include programs with stacks or coroutines, programs with recursive coroutines, as well as procedures and recursive procedures. In these papers she makes intensive use of Post algebras of order which she introduced and studied in several publications, some of them written jointly with George Epstein. Rasiowa was particularly interested in axiomatizations of algorithmic logics corresponding to different classes of programs and this problem is represented in her papers belonging to this stream of research. The lecture notes [72], based on her lectures at the Istituto per le Aplicazioni del Calcolo, reflect her search for a homogeneous approach to a wide class of logics of complex programs, an approach which would be general enough to yield known logics as particular cases. The first lecture notes ([63]), formed by lectures delivered at Simon Fraser University, correspond to the same point of view.

In 1984 Helena Rasiowa initiated intensive investigations on methods of inference under incomplete information, which she called approximate reasoning. At present approximation logics have become one of the central topics of research in artificial intelligence and among the algebraic tools used in this research an important role is assigned to those created and developped by Rasiowa. They include generalizations of Post algebras, among them semi-Post algebras ([84]) and the so-called plain semi-Post algebras ([89]), which served as a basis for the construction of logics of approximate reasoning. During this period Rasiowa has worked with several mathematicians like George Epstein (University of Charlotte, North Carolina), Wiktor Marek (State University of Kentucky), Nguyen Cat-Ho (Vietnam) or Andrzej Skowron (Warsaw University).

The papers [73-97] correspond to the period between 1984 and 1994 . In [74] first order approximation logics are constructed. They are based on approximation operators in the sense of Z.Pawlak, which are applied to sets and relations defined by first order formulas. In [75] these logics have been extended to the case of a chain of equivalnce relations which determine lower and upper approximations.

The paper [84] introduces a generalization of Post algebras, called semi-Post lattices (algebras). The primitive Post constants are elements of a poset rather than of a chain, complete lattice or connected semilattice as it had been usual in generalized Post algebras (e.g. in papers by Dwinger, Traczyk, Speed, Rasiowa, Cat-Ho). Several characterizations of sublattices of a reduct of a semi-Post algebra which are semi-Post subalgebras are given, as well as different characterizations of semi-Post homomorphisms. These make use of a theorem stating that every semi-Post algebra is a semi-Post product of generalized Post algebras in the sense of Cat-Ho.

In [82] Rasiowa presents an algebraic approach to approximate reasoning, based on modified information systems of Dana Scott. Semi-Post algebras built over Scott's information systems are used as tools for an analysis of the properties of approximate reasonings.

Approximate reasonings are also treated in [76], [77], where they are based on a decreasing sequence of equivalence relations, which define a sequence of closure operators. The main result consists in a characterization of those sets , which are intersections of the family of all closures.

In [83] methods of approximate reasoning related to a selection strategy are studied. Here again semi-Post algerbas are used as a tool for investigations. The properties of approximate deductions are expressed in a first order logic introduced in the paper. Its semantics is defined via semi-Post algebras and a representation theorem.

The paper [86] deals with approximation logics of different types , where is a well-founded poset. Such logics have been introduced by Rasiowa in [83] and they stem from the idea that a set of objects to be recognized in a process of approximate reasoning is approximated by a family of covering sets and by their intersection and it relies on the notion of rough sets in the sense of Z. Pawlak. The approach is axiomatic; a completeness theorem is proved algebraically, using plain semi-Post algebras. Such algebras have first appeared in literature in [89]. Their importance within the class of all semi-Post algebras is due to their simplicity and strong analogies with Post algebras, but also due to their importance in the investigation of approximation logics. The main result of the paper refers to the representability of these algebras. Every element is uniquely represented in a normal form.

In [88] an epistemic logic is designed, which formalizes approximating reasonings performed by groups of agents who perceive reality via perception operators, which are their individual attributes, and knowledge operators, which are attributes of subsets of agents when arriving at a consensus. It is assumed that the set of agents is a poset ordered with respect to the sharpness of perception and the ability to distinguish objects. An axiomatization of the introduced logic is given and a completeness theorem is proved together with several other metalogical theorems. This logic is free of the paradoxes which appear in other epistemic logics. The research intiated in [88] has been continued in [92] and [93].

The problem of axiomatizing fuzzy sets is one of the most interesting and topical problems in the theory of these sets. In [94] Rasiowa introduces the notion of an -fuzzy set, which is a modification of -fuzzy sets in the sense of Goguen (1967). This new approach has been based on the theory of semi-Post algebras, which made possible the development of an axiomatic theory of algebras of -sets ([94]) and a representation theorem. -fuzzy sets are endowed with a rich structure and the classical fuzzy sets of L.Zadeh (1965) appear here as a particular case. The results show numerous advantages of this approach; in particular, it leads to a solution of the axiomatization problem for -fuzzy sets. The papers [94-97] introduce and develop the new approach to fuzzy and rough sets, based on semi-Post algebras. -fuzzy logics formalize approximate reasonings applied to notions which are not totally determined.

In [90] a theory of algebras of order is developed and applied to a construction of an approximation logic. Post algebras of order are particularly interesting because of the fact that in spite of their infinite order they preserve more analogies with Post algebras of finite orders than any other known generalization of the latter algebras. Besides, they have proved very useful in applications to approximation logics of infinite type, allowing both lower and upper approximations of sets being recognized. The theory of Post algebras of order contains a set representation theorem and is used to formulate a complete axiomatization of a first order approximation logic.

These brief examples of Rasiowa's research results on approximation logics illustrate the variety and wealth of her investigations, on the other - they exhibit the relation between the important topics of today's computer science and the algebraic methods which she constantly developed for the sake of investigations in logic.

Till the very last moments of Professor Rasiowa's life we admired her youth-ful enthusiasm towards research, her valuable and original results and her ability to justly appreciate the perspectives of newly arising research directions. It is not easy to accept that we shall have to proceed with our work without her.