Other Computer Engineering Commons^™

Completeness For The Coalgebraic Cover Modality, Clemens Kupke, Alexander Kurz, Yde Venema

Engineering Faculty Articles and Research

We study the finitary version of the coalgebraic logic introduced by L. Moss. The syntax of this logic, which is introduced uniformly with respect to a coalgebraic type functor, required to preserve weak pullbacks, extends that of classical propositional logic with a so-called coalgebraic cover modality depending on the type functor. Its semantics is defined in terms of a categorically defined relation lifting operation.

As the main contributions of our paper we introduce a derivation system, and prove that it provides a sound and complete axiomatization for the collection of coalgebraically valid inequalities. Our soundness and completeness proof is algebraic, …

Coalgebraic Logics (Dagstuhl Seminar 12411), Ernst-Erich Doberkat, Alexander Kurz

Engineering Faculty Articles and Research

This report documents the program and the outcomes of Dagstuhl Seminar 12411 “Coalgebraic Logics”. The seminar deals with recent developments in the area of coalgebraic logic, a branch of logics which combines modal logics with coalgebraic semantics. Modal logic finds its uses when reasoning about behavioural and temporal properties of computation and communication, coalgebras have evolved into a general theory of systems. Consequently, it is natural to combine both areas for a mathematical description of system specification. Coalgebraic logics are closely related to the broader categories semantics/formal methods and verification/logic.

Relation Liftings On Preorders And Posets, Marta Bílková, Alexander Kurz, Daniela Petrişan, Jiří Velebil

Engineering Faculty Articles and Research

The category Rel(Set) of sets and relations can be described as a category of spans and as the Kleisli category for the powerset monad. A set-functor can be lifted to a functor on Rel(Set) iff it preserves weak pullbacks. We show that these results extend to the enriched setting, if we replace sets by posets or preorders. Preservation of weak pullbacks becomes preservation of exact lax squares. As an application we present Moss’s coalgebraic over posets.

Generic Trace Logics, Christian Kissig, Alexander Kurz

Engineering Faculty Articles and Research

We combine previous work on coalgebraic logic with the coalgebraic traces semantics of Hasuo, Jacobs, and Sokolova.

Towards Nominal Formal Languages, Alexander Kurz, Tomoyuki Suzuki, Emilio Tuosto

Engineering Faculty Articles and Research

We introduce formal languages over infinite alphabets where words may contain binders.We define the notions of nominal language, nominal monoid, and nominal regular expressions. Moreover, we extend history-dependent automata (HD-automata) by adding stack, and study the recognisability of nominal languages.

Evidence Supporting Measure Of Similarity For Reducing The Complexity In Information Fusion, Xinde Li, Jean Dezert, Florentin Smarandache, Xinhan Huang

Branch Mathematics and Statistics Faculty and Staff Publications

This paper proposes a new solution for reducing the number of sources of evidence to be combined in order to diminish the complexity of the fusion process required in some applications where the real-time constraint and strong computing resource limitation are of prime importance. The basic idea consists in selecting, among the whole set of sources of evidence, only the biggest subset of sources which are not too contradicting based on a criterion of Evidence Supporting Measure of Similarity (ESMS) in order to process solely the coherent information received. The ESMS criterion serves actually as a generic tool for outlier …

A New Approach To Algebraic Coding Theory Through The Applications Of Soft Sets, Florentin Smarandache, Mumtaz Ali

Branch Mathematics and Statistics Faculty and Staff Publications

Algebraic codes play a signifcant role in the minimisation of data corruption which caused by defects such as inference, noise channel, crosstalk, and packet loss. In this paper, we introduce soft codes (soft linear codes) through the application of soft sets which is an approximated collection of codes. We also discuss several types of soft codes such as type-1 soft codes, complete soft codes etc. Further, we construct the soft generator matrix and soft parity check matrix for the soft linear codes. Moreover, we develop two techniques for the decoding of soft codes.

Non Bayesian Conditioning And Deconditioning, Jean Dezert, Florentin Smarandache

Branch Mathematics and Statistics Faculty and Staff Publications

In this paper, we present a Non-Bayesian conditioning rule for belief revision. This rule is truly Non-Bayesian in the sense that it doesn’t satisfy the common adopted principle that when a prior belief is Bayesian, after conditioning by X, Bel(X|X) must be equal to one. Our new conditioning rule for belief revision is based on the proportional conflict redistribution rule of combination developed in DSmT (Dezert-Smarandache Theory) which abandons Bayes’ conditioning principle. Such Non-Bayesian conditioning allows to take into account judiciously the level of conflict between the prior belief available and the conditional evidence. We also introduce the deconditioning problem …

Bitopological Duality For Distributive Lattices And Heyting Algebras, Guram Bezhanishvili, Nick Bezhanishvili, David Gabelaia, Alexander Kurz

Engineering Faculty Articles and Research

We introduce pairwise Stone spaces as a natural bitopological generalization of Stone spaces—the duals of Boolean algebras—and show that they are exactly the bitopological duals of bounded distributive lattices. The category PStone of pairwise Stone spaces is isomorphic to the category Spec of spectral spaces and to the category Pries of Priestley spaces. In fact, the isomorphism of Spec and Pries is most naturally seen through PStone by first establishing that Pries is isomorphic to PStone, and then showing that PStone is isomorphic to Spec. We provide the bitopological and spectral descriptions of many algebraic concepts important for the study …

On Coalgebras Over Algebras, Adriana Balan, Alexander Kurz

Engineering Faculty Articles and Research

We extend Barr’s well-known characterization of the final coalgebra of a Set-endofunctor as the completion of its initial algebra to the Eilenberg-Moore category of algebras for a Set-monad M for functors arising as liftings. As an application we introduce the notion of commuting pair of endofunctors with respect to the monad M and show that under reasonable assumptions, the final coalgebra of one of the endofunctors involved can be obtained as the free algebra generated by the initial algebra of the other endofunctor.

On Universal Algebra Over Nominal Sets, Alexander Kurz, Daniela Petrişan

Engineering Faculty Articles and Research

We investigate universal algebra over the category Nom of nominal sets. Using the fact that Nom is a full re ective subcategory of a monadic category, we obtain an HSP-like theorem for algebras over nominal sets. We isolate a `uniform' fragment of our equational logic, which corresponds to the nominal logics present in the literature. We give semantically invariant translations of theories for nominal algebra and NEL into `uniform' theories and systematically prove HSP theorems for models of these theories.

Families Of Symmetries As Efficient Models Of Resource Binding, Vincenzo Ciancia, Alexander Kurz, Ugo Montanari

Engineering Faculty Articles and Research

Calculi that feature resource-allocating constructs (e.g. the pi-calculus or the fusion calculus) require special kinds of models. The best-known ones are presheaves and nominal sets. But named sets have the advantage of being finite in a wide range of cases where the other two are infinite. The three models are equivalent. Finiteness of named sets is strictly related to the notion of finite support in nominal sets and the corresponding presheaves. We show that named sets are generalisd by the categorical model of families, that is, free coproduct completions, indexed by symmetries, and explain how locality of interfaces gives good …

Algebraic Theories Over Nominal Sets, Alexander Kurz, Daniela Petrişan, Jiří Velebil

Engineering Faculty Articles and Research

We investigate the foundations of a theory of algebraic data types with variable binding inside classical universal algebra. In the first part, a category-theoretic study of monads over the nominal sets of Gabbay and Pitts leads us to introduce new notions of finitary based monads and uniform monads. In a second part we spell out these notions in the language of universal algebra, show how to recover the logics of Gabbay-Mathijssen and Clouston-Pitts, and apply classical results from universal algebra.

Super Special Codes Using Super Matrices, Florentin Smarandache, W.B. Vasantha Kandasamy, K. Ilanthenral

Branch Mathematics and Statistics Faculty and Staff Publications

The new classes of super special codes are constructed in this book using the specially constructed super special vector spaces. These codes mainly use the super matrices. These codes can be realized as a special type of concatenated codes. This book has four chapters. In chapter one basic properties of codes and super matrices are given. A new type of super special vector space is constructed in chapter two of this book. Three new classes of super special codes namely, super special row code, super special column code and super special codes are introduced in chapter three. Applications of these …

Equational Coalgebraic Logic, Alexander Kurz, Raul Leal

Engineering Faculty Articles and Research

Coalgebra develops a general theory of transition systems, parametric in a functor T; the functor T specifies the possible one-step behaviours of the system. A fundamental question in this area is how to obtain, for an arbitrary functor T, a logic for T-coalgebras. We compare two existing proposals, Moss’s coalgebraic logic and the logic of all predicate liftings, by providing one-step translations between them, extending the results in [21] by making systematic use of Stone duality. Our main contribution then is a novel coalgebraic logic, which can be seen as an equational axiomatization of Moss’s logic. The three logics are …

Functorial Coalgebraic Logic: The Case Of Many-Sorted Varieties, Alexander Kurz, Daniela Petrişan

Engineering Faculty Articles and Research

Following earlier work, a modal logic for T-coalgebras is a functor L on a suitable variety. Syntax and proof system of the logic are given by presentations of the functor. This paper makes two contributions. First, a previous result characterizing those functors that have presentations is generalized from endofunctors on one-sorted varieties to functors between many-sorted varieties. This yields an equational logic for the presheaf semantics of higher-order abstract syntax. As another application, we show how the move to functors between many-sorted varieties allows to modularly combine syntax and proof systems of different logics. Second, we show how to associate …

Pi-Calculus In Logical Form, Marcello M. Bonsangue, Alexander Kurz

Engineering Faculty Articles and Research

Abramsky’s logical formulation of domain theory is extended to encompass the domain theoretic model for picalculus processes of Stark and of Fiore, Moggi and Sangiorgi. This is done by defining a logical counterpart of categorical constructions including dynamic name allocation and name exponentiation, and showing that they are dual to standard constructs in functor categories. We show that initial algebras of functors defined in terms of these constructs give rise to a logic that is sound, complete, and characterises bisimilarity. The approach is modular, and we apply it to derive a logical formulation of pi-calculus. The resulting logic is a …

Coalgebras And Their Logics, Alexander Kurz

Engineering Faculty Articles and Research

"Transition systems pervade much of computer science. This article outlines the beginnings of a general theory of specification languages for transition systems. More specifically, transition systems are generalised to coalgebras. Specification languages together with their proof systems, in the following called (logical or modal) calculi, are presented by the associated classes of algebras (e.g., classical propositional logic by Boolean algebras). Stone duality will be used to relate the logics and their coalgebraic semantics."

Weak Factorizations, Fractions And Homotopies, Alexander Kurz, Jiří Rosický

Engineering Faculty Articles and Research

We show that the homotopy category can be assigned to any category equipped with a weak factorization system. A classical example of this construction is the stable category of modules. We discuss a connection with the open map approach to bisimulations proposed by Joyal, Nielsen and Winskel.

Preface, Thomas Hildebrandt, Alexander Kurz

Engineering Faculty Articles and Research

No abstract provided.

Algebraic Semantics For Coalgebraic Logics, Clemens Kupke, Alexander Kurz, Dirk Pattinson

Engineering Faculty Articles and Research

With coalgebras usually being defined in terms of an endofunctor T on sets, this paper shows that modal logics for T-coalgebras can be naturally described as functors L on boolean algebras. Building on this idea, we study soundness, completeness and expressiveness of coalgebraic logics from the perspective of duality theory. That is, given a logic L for coalgebras of an endofunctor T, we construct an endofunctor L such that L-algebras provide a sound and complete (algebraic) semantics of the logic. We show that if L is dual to T, then soundness and completeness of the algebraic semantics immediately yield the …

Coalgebras And Modal Expansions Of Logics, Alexander Kurz, Alessandra Palmigiano

Engineering Faculty Articles and Research

In this paper we construct a setting in which the question of when a logic supports a classical modal expansion can be made precise. Given a fully selfextensional logic S, we find sufficient conditions under which the Vietoris endofunctor V on S-referential algebras can be defined and we propose to define the modal expansions of S as the logic that arises from the V-coalgebras. As an example, we also show how the Vietoris endofunctor on referential algebras extends the Vietoris endofunctor on Stone spaces. From another point of view, we examine when a category of ‘spaces’ (X,A), ie sets X …

Stone Coalgebras, Clemens Kupke, Alexander Kurz, Yde Venema

Engineering Faculty Articles and Research

In this paper we argue that the category of Stone spaces forms an interesting base category for coalgebras, in particular, if one considers the Vietoris functor as an analogue to the power set functor. We prove that the so-called descriptive general frames, which play a fundamental role in the semantics of modal logics, can be seen as Stone coalgebras in a natural way. This yields a duality between the category of modal algebras and that of coalgebras over the Vietoris functor. Building on this idea, we introduce the notion of a Vietoris polynomial functor over the category of Stone spaces. …

Definability, Canonical Models, And Compactness For Finitary Coalgebraic Modal Logic, Alexander Kurz, Dirk Pattinson

Engineering Faculty Articles and Research

This paper studies coalgebras from the perspective of the finitary observations that can be made of their behaviours. Based on the terminal sequence, notions of finitary behaviours and finitary predicates are introduced. A category Behω(T) of coalgebras with morphisms preserving finitary behaviours is defined. We then investigate definability and compactness for finitary coalgebraic modal logic, show that the final object in Behω(T) generalises the notion of a canonical model in modal logic, and study the topology induced on a coalgebra by the finitary part of the terminal sequence.

Modal Predicates And Coequations, Alexander Kurz, Jiří Rosický

Engineering Faculty Articles and Research

We show how coalgebras can be presented by operations and equations. This is a special case of Linton’s approach to algebras over a general base category X, namely where X is taken as the dual of sets. Since the resulting equations generalise coalgebraic coequations to situations without cofree coalgebras, we call them coequations. We prove a general co-Birkhoff theorem describing covarieties of coalgebras by means of coequations. We argue that the resulting coequational logic generalises modal logic.

Preface, Alexander Kurz

Engineering Faculty Articles and Research

No abstract provided.

Modal Rules Are Co-Implications, Alexander Kurz

Engineering Faculty Articles and Research

In [13], it was shown that modal logic for coalgebras dualises—concerning definability— equational logic for algebras. This paper establishes that, similarly, modal rules dualise implications:It is shown that a class of coalgebras is definable by modal rules iff it is closed under H (images) and Σ (disjoint unions). As a corollary the expressive power of rules of infinitary modal logic on Kripke frames is characterised.

Notes On Coalgebras, Cofibrations And Concurrency, Alexander Kurz, Dirk Pattinson

Engineering Faculty Articles and Research

We consider categories of coalgebras as (co)-fibred over a base category of parameters and analyse categorical constructions in the total category of deterministic and non-deterministic coalgebras.

(Ω, Ξ)-Logic: On The Algebraic Extension Of Coalgebraic Specifications, Rolf Hennicker, Alexander Kurz

Engineering Faculty Articles and Research

We present an extension of standard coalgebraic specification techniques for statebased systems which allows us to integrate constants and n-ary operations in a smooth way and, moreover, leads to a simplification of the coalgebraic structure of the models of a specification. The framework of (Ω,Ξ)-logic can be considered as the result of a translation of concepts of observational logic (cf. [9]) into the coalgebraic world. As a particular outcome we obtain the notion of an (Ω, Ξ)- structure and a sound and complete proof system for (first-order) observational properties of specifications.