## Number 1

M. F. FRIAS , G. A. BAUM and A. M.HAEBERER
Fork Algebras in Algebra, Logic and Computer Science
pages 1--25

Since the main themes at the Helena Rasiowa memorial were algebra, logic and computer science, we will present a survey of results on fork algebras from
these points of view. IIn this paper we study fork algebras from the points ofview of their algebraic and logical properties and applications. These results
will prove to be essential, in a future work, for the definition of a wide-spectrum calculus for program construction.
S. KASANGIAN and S. VIGNA
The Topos of Labelled Trees: A Categorical Semantics for SCCS
pages  27-45

In this paper a we give a semantics for SCCS using the constructions of the topos of labelled trees. The semantics accounts for all aspects of the original
formulation of  SCCS including unbounded non-determinism. Then, a partial solution to the problem of characterizing bisimulation in terms of a class of morphisms is proposed. We define a class of morphisms of the topos of trees, called  conflict preserving, such that two trees T and  U are bisimilar iff there is a pair of conflict preserving morphisms f from T  to  U and g from  U to T such that fgf=f and gfg=g. It is the first characterization which does not require the existence of a third quotient object. The results can be easily extended to more general transition systems.
D. PIGOZZI and A. SALIBRA
Lambda Abstraction Algebras: Coordinatizing Models of Lambda Calculus
pages 47-90

Lambda abstraction algebras are designed to algebraize the untyped lambda calculus in the same way cylindric and polyadic algebras algebraize the first-order logic; they are ntended as an alternative to combinatory algebras in this regard. Like combinatory algebras they can be defined by true identities and thus form a variety in the sense of universal algebra.
One feature of lambda abstraction algebras that sets them apart from combinatory algebras is the way variables in the lambda calculus are abtracted; this provides each lambda abstraction algebra with an implicit coordinate system.
Another peculiar feature is the algebraic reformulation of ($\beta$)-conversion as the definition of abstract substitution. Functional lambda abstraction algebras arise as the
coordinatizations'' of environment models or lambda models, the natural combinatory models of the lambda calculus. As in the case of cylindric and polyadic algebras, questions of the functional representation of various subclasses of lambda abstraction algebras  are an important part of the theory.
The main result of the paper is a stronger version of the functional representation theorem for locally finite lambda abstraction algebras, the algebraic analogue of the completeness theorem of lambda calculus. This result is used to study the connection between the combinatory models of the lambda calculus and lambda abstraction algebras. Two significant results of this kind are the existence of a strong categorical equivalence between lambda algebras and locally finite lambda abstraction algebras, and between lambda models and rich, locally finite lambda abstraction algebras.

J. TYSZKIEWICZ
Queries and Algorithms Computable by Polynomial Time Existential Reflective Machines
pages 91-105

We consider two kinds of reflective relational machines: the usual ones, which use first order queries, and existential reflective machines, which use only first order existential queries. We compare these two computation models. We build on already existing results for standard relational machines, obtained by Abiteboul, Papadimitriou and
Vianu~[2], so we prove only results for existential machines.
First we show that for both standard and existential reflective machines the set of polynomial time computable Boolean queries consists precisely of all  PSPACE omputable queries.
Then we go further and compare which classes of algorithms both kinds of machines represent. Unless  PSPACEPNP there are PSPACE queries which cannot be computed by polynomial time existential reflective machines which use only polynomial amount of relational memory, while it is possible for standard reflective machines. We conclude that existential reflective machines, being equivalent in computational power to unrestricted machines, implement substantially worse algorithms than the latter.
Concerning deciding P classes of structures, every fixpoint query can be evaluated by a polynomial time unrestricted reflective machine using constant number of variables, while existential reflective machines need $\lfloor n/2\rfloor$ variables to implement the graph connectivity query. So again the algorithms represented by existential reflective machines are worse.
Finally, for each $k$ we get a characterization of the $\Delta_{k+1}^p$ level in the polynomial time hierarchy in terms of reflective relational machines which use either $\Pi^0_k$ or $\Sigma^p_k$ queries.

## Number 2

M.K. CHAKRABORTY  and E. ORLOWSKA
Substitutivity Principles in Some Theories of Uncertainty
pages 107-120

A semantics of identity inspired by rough set modeling of uncertainty is proposed and the underlying substitutivity principles are presented. A survey of some theories of identity is given, in particular, an interpretation of identity in E-unification theory, some many-valued logics and some algebraic theories.

T. GAASTERLAND and J. LOBO
Qualifying Answers According to User Needs and Preferences
pages 121-137

This paper presents a rigorous methodology for using annotated logic programming techniques to handle user preferences and needs in answering database queries. Two alternative transformations turn a database program into a new program that returns answers to queries according to qualitative labels. The two transformations
have different semantics and are each appropriate in different situations.  We have modified the standard definitions of annotated logic programs to handle user needs and preferences in databases.
In the formalism, the user provides a lattice of domain-independent values that define preferences and needs and a set of domain specific user constraints qualified with lattice values. After the original database and the user constraints have been transformed into a new annotated deductive database, query-answering procedures for deductive databases are used, with minor modifications, to obtain annotated answers to queries. Because preference declaration is separated from data representation and management, preferences can be easily altered without touching the database.  The resulting query language allows users to ask for answers at different preference levels.

V. MAREK, A. NERODE and J. B. REMMEL
Complexity of Recursive Normal Default Logic
pages 139-147

Normal default logic, the fragment of default logic obtained by restricting defaults to rules of the form $\frac{\alpha: M\beta}{\beta}$, is the most important and widely studied part of default logic.  In [20], we proved  a basis theorem for extensions of recursive propositional logic normal default theories and hence for finite
predicate logic normal default theories.  That is, we proved that every recursive propositional normal default theory possesses an extension which is r.e. in $0'$. Here we
show that this bound is tight. Specifically, we show that for every r.e. set $A$ and every set $B$ r.e. in $A$ there is a recursive normal default theory $\langle D,W\rangle$ with a unique extension  which is Turing-equivalent to $A\bigoplus B$. A similar result holds for finite predicate logic normal default theories.

G. PAUN, L. POLKOWSKI and A. SKOWRON
Rough Set Approximations of Languages
pages 149-162
We investigate here the possibility of approximating a language starting from a partial knowledge of its strings. This is understood as the possibility to read only a bounded part of a string: a prefix or a subword. In this way, indiscernibility relations among strings (they are equivalence or tolerance relations) are introduced, which lead to lower and upper approximations of languages. By varying the length of the perceived substring, we get sequences of approximations converging to the language. In many cases, the pproximations of context-free languages are proved to be regular languages.
C. RUIZ and J. MINKER
Combining Closed World Assumptions with Stable Negation
pages 163-181

