The logic of Peirce algebras

Peirce algebras combine sets, relations and various operations linking the two in a unifying setting. This paper offers a modal perspective on Peirce algebras. Using modal logic a characterization of the full Peirce algebras is given, as well as a finite axiomatization of their equational theory that uses so-called unorthodox derivation rules. In addition, the expressive power of Peirce algebras is analyzed through their connection with first-order logic, and the fragment of first-order logic corresponding to Peirce algebras is described in terms of bisimulations.     

Completion of Boolean algebras in MSet

Two important algebraic structures in many branches of mathematics as well as in computer science are M-sets (sets with an action of a monoid M on them) and Boolean algebras. Of particular significance are complete Boolean algebras. And in the absence of the desired completeness one often considers extensions which remedy this lack, preferably in a “universal” way as a normal completion. Combining these two structures one gets M-Boolean algebras (Boolean algebras with an action of M on them, which are a special case of Boolean algebras with operators).The aim of this paper is to study the general notion of an internally complete poset in a topos, in the sense of Johnstone, and use it to give a minimal normal completion for an M-Boolean algebra.     

Distributive mereotopology: extended distributive contact lattices

The notion of contact algebra is one of the main tools in the region based theory of space. It is an extension of Boolean algebra with an additional relation C called contact. The elements of the Boolean algebra are considered as formal representations of spatial regions as analogues of physical bodies and Boolean operations are considered as operations for constructing new regions from given ones and also to define some mereological relations between regions as part-of, overlap and underlap. The contact relation is one of the basic mereotopological relations between regions expressing some topological nature. It is used also to define some other important mereotopological relations like non-tangential inclusion, dual contact, external contact and others. Most of these definitions are given by means of the operation of Boolean complementation. There are, however, some problems related to the motivation of the operation of Boolean complementation. In order to avoid these problems we propose a generalization of the notion of contact algebra by dropping the operation of complement and replacing the Boolean part of the definition by that of a distributive lattice. First steps in this direction were made in (Düntsch et al. Lect. Notes Comput. Sci. 4136, 135–147, 2006, Düntsch et al. J. Log. Algebraic Program. 76, 18–34, 2008) presenting the notion of distributive contact lattice based on the contact relation as the only mereotopological relation. In this paper we consider as non-definable primitives the relations of contact, nontangential inclusion and dual contact, extending considerably the language of distributive contact lattices. Part I of the paper is devoted to a suitable axiomatization of the new language called extended distributive contact lattice (EDC-lattice) by means of universal first-order axioms true in all contact algebras. EDC-lattices may be considered also as an algebraic tool for a certain subarea of mereotopology, called in this paper distributive mereotopology. The main result of Part I of the paper is a representation theorem, stating that each EDC-lattice can be isomorphically embedded into a contact algebra, showing in this way that the presented axiomatization preserves the meaning of mereotopological relations without considering Boolean complementation. Part II of the paper is devoted to topological representation theory of EDC-lattices, transferring into the distributive case important results from the topological representation theory of contact algebras. It is shown that under minor additional assumptions on distributive lattices as extensionality of the definable relations of overlap or underlap one can preserve the good topological interpretations of regions as regular closed or regular open sets in topological space.     

Synchronous Kleene algebra

The work presented here investigates the combination of Kleene algebra with the synchrony model of concurrency from Milner’s SCCS calculus. The resulting algebraic structure is called synchronous Kleene algebra. Models are given in terms of sets of synchronous strings and finite automata accepting synchronous strings. The extension of synchronous Kleene algebra with Boolean tests is presented together with models on sets of guarded synchronous strings and the associated automata on guarded synchronous strings. Completeness w.r.t. the standard interpretations is given for each of the two new formalisms. Decidability follows from completeness. Kleene algebra with synchrony should be included in the class of true concurrency models. In this direction, a comparison with Mazurkiewicz traces is made which yields their incomparability with synchronous Kleene algebras (one cannot simulate the other). On the other hand, we isolate a class of pomsets which captures exactly synchronous Kleene algebras. We present an application to Hoare-like reasoning about parallel programs in the style of synchrony.     

Algebraic models of deviant modal operators based on de Morgan and Kleene lattices

An algebraic model of a kind of modal extension of de Morgan logic is described under the name MDS5 algebra. The main properties of this algebra can be summarized as follows: (1) it is based on a de Morgan lattice, rather than a Boolean algebra; (2) a modal necessity operator that satisfies the axioms N, K, T, and 5 (and as a consequence also B and 4) of modal logic is introduced; it allows one to introduce a modal possibility by the usual combination of necessity operation and de Morgan negation; (3) the necessity operator satisfies a distributivity principle over joins. The latter property cannot be meaningfully added to the standard Boolean algebraic models of S5 modal logic, since in this Boolean context both modalities collapse in the identity mapping. The consistency of this algebraic model is proved, showing that usual fuzzy set theory on a universe U can be equipped with a MDS5 structure that satisfies all the above points (1)-(3), without the trivialization of the modalities to the identity mapping. Further, the relationship between this new algebra and Heyting-Wajsberg algebras is investigated. Finally, the question of the role of these deviant modalities, as opposed to the usual non-distributive ones, in the scope of knowledge representation and approximation spaces is discussed.     

粗代数研究

在粗糙集的代数方法研究中,一个重要的方面是从粗糙集的偶序对((下近似集,上近似集()表示入手,通过定义偶序对的基本运算,从而构造出相应粗代数,并寻找能够抽象刻画偶序对性质的一般代数结构.其中最有影响的粗代数分别是粗双Stone代数、粗Nelson代数和近似空间代数,它们对应的一般代数结构分别是正则双Stone代数、半简单Nelson代数和预粗代数.通过建立这些粗代数中算子之间的联系,证明了:(a) 近似空间代数可转化为半简单Nelson代数和正则双Stone代数;(b) 粗Nelson代数可转化为预粗代数和正则双Stone代数;(c) 粗双Stone代数可化为预粗代数和半简单Nelson代数,从而将3个不同角度的研究统一了起来.     

On the algebraic structure of binary lattice-valued fuzzy relations

From a general algebraic point of view, this paper aims at providing an algebraic analysis for binary lattice-valued relations based on lattice implication algebras—a kind of lattice-valued propositional logical algebra. By abstracting away from the concrete lattice-valued relations and the operations on them, such as composition and converse, the notion of lattice-valued relation algebra is introduced, LRA for short. The reduct of an LRA is a lattice implication algebra. Such an algebra generalizes Boolean relation algebras by general distributive lattices and can provide a fundamental algebraic theory for establishing lattice-valued first-order logic. Some important results are generalized from the classical case. The notion of cylindric filter is introduced and the generated cylindric filters are characterized.     

Region–based theory of discrete spaces: A proximity approach

We introduce Boolean proximity algebras as a generalization of Efremovič proximities which are suitable in reasoning about discrete regions. Following Stone’s representation theorem for Boolean algebras, it is shown that each such algebra is isomorphic to a substructure of a complete and atomic Boolean proximity algebra. Co-operation was supported by EC COST Action 274 “Theory and Applications of Relational Structures as Knowledge Instruments” (TARSKI), , and NATO Collaborative Linkage Grant PST.CLG 977641.     

Refinement algebra with dual operator

Algebras of imperative programming languages have been successful in reasoning about programs. In general an algebra of programs is an algebraic structure with programs as elements and with program compositions (sequential composition, choice, skip) as algebra operations. Various versions of these algebras were introduced to model partial correctness, total correctness, refinement, demonic choice, and other aspects. We introduce here an algebra which can be used to model total correctness, refinement, demonic and angelic choice. The basic model of our algebra are monotonic Boolean transformers (monotonic functions from a Boolean algebra to itself).     

On the isomorphism problem of concept algebras

Weakly dicomplemented lattices are bounded lattices equipped with two unary operations to encode a negation on concepts. They have been introduced to capture the equational theory of concept algebras (Wille 2000; Kwuida 2004). They generalize Boolean algebras. Concept algebras are concept lattices, thus complete lattices, with a weak negation and a weak opposition. A special case of the representation problem for weakly dicomplemented lattices, posed in Kwuida (2004), is whether complete weakly dicomplemented lattices are isomorphic to concept algebras. In this contribution we give a negative answer to this question (Theorem 4). We also provide a new proof of a well known result due to M.H. Stone (Trans Am Math Soc 40:37–111, 1936), saying that each Boolean algebra is a field of sets (Corollary 4). Before these, we prove that the boundedness condition on the initial definition of weakly dicomplemented lattices (Definition 1) is superfluous (Theorem 1, see also Kwuida (2009)).     

Sub-effect algebras and Boolean sub-effect algebras

 We show that Boolean effect algebras may have proper sub-effect algebras and conversely. Properties of lattice effect algebras with two blocks are shown. One condition of the completness of effect algebras is given. We also show that a lattice effect algebra associated to an orthomodular lattice can be embedded into a complete effect algebra iff the orthomodular lattice can be embedded into a complete orthomodular lattice.     

Rough 3-valued algebras

Rough set theory is an important tool for dealing with granularity and vagueness in information systems. This paper studies a kind of rough set algebra. The collection of all the rough sets of an approximation space can be made into a 3-valued Lukasiewicz algebra. We call the algebra a rough 3-valued Lukasiewicz algebra. In this paper, we focus on the rough 3-valued Lukasiewicz algebras, which are a special kind of 3-valued Lukasiewicz algebras. Firstly, we examine whether the rough 3-valued Lukasiewicz algebra is an axled 3-valued Lukasiewicz algebra. Secondly, we present the condition under which the rough 3-valued Lukasiewicz algebra is also a 3-valued Post algebra. Then we investigate the 3-valued Post subalgebra problem of the rough 3-valued Lukasiewicz algebra. Finally, this paper studies the relationship between the rough 3-valued Lukasiewicz algebra and the Boolean algebra constructed by all the exact sets of the corresponding approximation space.     

On Discretized Generalizations of Krichever-Novikov Algebras

The structure of a generalization of the Virasoro-De-Witt algebra is investigated. Its commutator algebra structure is generated by the derivative operator, coupled to a difference operator by a pair of parameters (x, y). The generators of the commutator algebra A are constructed as products of monomials and integer powers of the shifted Weierstrass--function. The structure coefficients of the arising commutator algebra are derived. Lie substructures of the algebra are evaluated in detail, in particular with respect to Lie subalgebras. An efficient tool, introduced as Basis Pairs, is used to get information on the substructures under investigation. Degenerations of the algebra A are investigated and it turns out that several Lie algebras — studied in formerly in the context of bosonic string theory — can be reobtained as special cases from the substructures of A we develop.     

Maximal contractions in Boolean algebras

In the present paper,the concepts of deductive element and maximal contraction are introduced in Boolean algebras,and corresponding theories of consistency and maximal contractions are studied.An algorithm principle is proposed to compute all maximal contractions for a consistent set with respect to its refutation in Boolean algebras.It is pointed out that the quotient algebra of the first-order language with respect to its provable equivalence relation constitutes a Boolean algebra,and hence the computation of R-contractions for closed formulas in first-order languages can be converted into the one in Boolean algebras proposed in this paper.Furthermore,the concept of basic element is introduced in Boolean algebras,which contributes to the definitions of clause and Horn clause transplanted from logic to a special type of Boolean algebras generated by basic elements.It is also pointed out that the computation of R-contractions for clauses in the classical propositional logic can be converted into the one in Boolean algebras generated by basic elements proposed in this paper.     

Ideals in MV-pairs

An MV-pair is a BG-pair (B, G) (where B is a Boolean algebra and G is a subgroup of the automorphism group of B) satisfying certain conditions. Recently, it was proved by Jenča that, given an MV-pair (B, G), the quotient B/~ _G , where ~ _G is an equivalence relation naturally associated with G, is an MV-algebra, and conversely, to every MV-algebra there corresponds an MV-pair. In this paper, we study relations between congruences of B and congruences of B/~ _G induced by a G-invariant ideal I of B. In addition we bring some relations between ideals in MV-algebras and in the corresponding R-generated Boolean algebras.     

Kleene modules and linear languages

A Kleene algebra (K, +, ·, *, 0, 1) is an idempotent semiring with an iteration * as axiomatised by Kozen. We consider left semiring modules (A, +, 0, :) over Kleene algebras. We call such a left semiring module a Kleene module if each linear equation x = a + r : x has a least solution, where : is the product from K × A to A. The linear context-free languages can be viewed as a Kleene module A over a Kleene algebra R of binary regular word relations. Thus, the simultaneous linear fixed-point operator μ on languages can be reduced to iteration * on R and the scalar product :.     

Pseudocomplemented lattice effect algebras and existence of states

We prove that in every pseudocomplemented atomic lattice effect algebra the subset of all pseudocomplements is a Boolean algebra including the set of sharp elements as a subalgebra. As an application, we show families of effect algebras for which the existence of a pseudocomplementation implies the existence of states. These states can be obtained by smearing of states existing on the Boolean algebra of sharp elements.     

Bases for Boolean co-clones

The complexity of various problems in connection with Boolean constraints, like, for example, quantified Boolean constraint satisfaction, have been studied recently. Depending on what types of constraints may be used, the complexity of such problems varies. A very interesting observation of the recent past has been that the thus derived classification of constraints can be explained with the help of universal algebra. More precisely, the difficulty of such a constraint problem often depends on the co-clone the constraints are from. A co-clone is a set of Boolean relations that is closed under very natural closure operations. Nearly all these co-clones can be generated by said operators out of a finite set of relations, a so-called base. Knowing a, preferably simple, base for each co-clone can therefore be of great value when studying the complexity of Boolean constraint problems, since this knowledge reduces the infinitely many cases of equivalent problems to a single one—the constraint satisfaction problem for this base. In this paper we give a finite and simple base for every Boolean co-clone, where this is possible. We give evidence that the presented bases are as easy as possible.     

INTERACTIVE 0-ALGEBRAS AND FUZZY OBJECTS OF TYPE N

The aim of this paper is to raise some questions–and partly, also to answer them –in connection with two important problem groups of fuzzy mathematics: n-fuzzy objects and the sigma-properties of different interactive fuzzy structures. These questions are suggested by the analyzation of natural languages, the common sense thinking – which are typical fields where the most adequate mathematical model is a fuzzy one-especially by complex adjectival structures and subjective “verifying” processes, respectively. They have, however, a real practical significance also in the field of engineering, as, e.g., in learning machine problems.In the first part we try to point to the practical importance of the concept of fuzzy objects of type n (or n-fuzzy objects), from the aspect of modeling natural languages. A useful way to define n-fuzzy algebras, i.e., generalizing ordinary fuzzy algebras for n-fuzzy objects, is also given, with introducing an isomorphism mapping from the fuzzy to the n-fuzzy object space. As an example, R-n-fuzzy algebra is defined. Because of the isomorphic property of the above mapping the later studies can be restricted to ordinary fuzzy objects.

In the second part some very basic concepts in connection with the sigma-properties of fuzzy algebras are given and some simple theorems are proved. These are quite important from the aspect of fuzzy learning processes, as their probability theoretic interpretation leads to several convergence theorems – which are not dealt with here, however.

In this part we raise the concept of the quantified of a fuzzy algebra, and by means of this concept a close relation between interactive fuzzy and Boolean algebras is proved –a very different relation from that between Zadeh's original, noninteractive system and Boolean algebra.

Although any presentation of complete application examples is not at all intended in this paper, finally some aspects of the application of the above results, especially in learning control algorithms, are given, the statements backed up by the experience of a simulation experiment going on at present.