Search

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: Coalgebras can be seen as a natural abstraction of Kripke frames. In the same sense, coalgebraic logics are generalised modal logics. In this paper, we give an overview of the basic tools, techniques and results that connect coalgebras and modal logic. We argue that coalgebras unify the semantics of a large range of different modal logics (such as probabilistic, graded, relational, conditional) and discuss unifying approaches to reasoning at this level of generality. We review languages defined in terms of the so-called cover modality, languages induced by predicate liftings as well as their common categorical abstraction, and present (abstract) results on completeness, expressiveness and complexity in these settings, both for basic languages as well as a number of extensions, such as hybrid languages and fixpoints. [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]

Abstract: The relational product construction is often consider as an abstract version of cartesian products. The existence of those products is strongly connected with the representability of that category. In this paper we investigate a canonical weakening of the notion of a relational product. Unlike the strong version, any (small) category of relations can be embedded into a suitable category providing all weak relational products. Furthermore, we provide several examples, and we study the categorical properties of the new construction. [Copyright &y& Elsevier]

Abstract: Given a finite set E, a relation with base is a mapping such that for all . The restriction of R to a subset X of E is R considered as a mapping from into . Given an integer and a relation R with base E, we call -reconstruction of R every relation with the same base, any restriction of which to a subset X of E with up to k elements is isomorphic to the restriction of R to X. The relation R is -reconstructible when each -reconstruction of R is isomorphic to R. In this work, the structure of the non--reconstructible relations is studied for all . This study leads to an introduction of the minimal non--reconstructible relations and to characterization of the class of such relations for all . This class includes in particular the class of the indecomposable non--reconstructible relations. [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]