Search

Abstract A relation algebra is called measurable when its identity is the sum of measurable atoms, where an atom is called measurable if its square is the sum of functional elements. In this paper we show that atomic measurable relation algebras have rather strong structural properties: they are constructed from systems of groups, coordinated systems of isomorphisms between quotients of the groups, and systems of cosets that are used to “shift” the operation of relative multiplication. An atomic and complete measurable relation algebra is completely representable if and only if there is a stronger coordination between these isomorphisms induced by a scaffold (the shifting cosets are not needed in this case). We also prove that a measurable relation algebra in which the associated groups are all finite is atomic. [ABSTRACT FROM AUTHOR]

In this paper we consider, from a computational point of view, the problem of classifying logics within the Leibniz and Frege hierarchies typical of abstract algebraic logic. The main result states that, for logics presented syntactically, this problem is in general undecidable. More precisely, we show that there is no algorithm that classifies the logic of a finite consistent Hilbert calculus in the Leibniz and in the Frege hierarchies. [ABSTRACT FROM AUTHOR]

Abstract: We show that for Multiplicative Exponential Linear Logic (without weakenings) the syntactical equivalence relation on proofs induced by cut-elimination coincides with the semantic equivalence relation on proofs induced by the multiset based relational model: one says that the interpretation in the model (or the semantics) is injective. We actually prove a stronger result: two cut-free proofs of the full multiplicative and exponential fragment of linear logic whose interpretations coincide in the multiset based relational model are the same “up to the connections between the doors of exponential boxes”. [Copyright &y& Elsevier]

Abstract: We generalize stochastic Kripke models and Markov transition systems to stochastic right coalgebras. These are coalgebras for a functor with as an endofunctor on the category of analytic spaces, and is the subprobability functor. The modal operators are generalized through predicate liftings which are set-valued natural transformations involving the functor. Two states are equivalent iff they cannot be separated by a formula. This equivalence relation is used to construct a cospan for logical equivalent coalgebras under a separation condition for the set of predicate liftings. Consequently, behavioral and logical equivalence are really the same. From the cospan we construct a span. The central argument is a selection argument giving us the dynamics of a mediating coalgebra from the domains of the cospan. This construction is used to establish that behavioral equivalent coalgebras are bisimilar, yielding the equivalence of all three characterizations of a coalgebra’s behavior as in the case of Kripke models or Markov transition systems. [Copyright &y& Elsevier]

Relation algebras were invented by Tarski and his collaborators in the middle of the 20th century. The concept of integrality arose naturally early in the history of the subject, as did various constructions of finite integral relation algebras. Later the concept of finite-dimensionality was introduced for classifying nonrepresentable relation algebras. This concept is closely connected to the number of variables used in proofs in first-order logic. Some results on these topics are presented in chronological order. [Copyright &y& Elsevier]