Coding distributive lattices with Edge Firing Games

In this note, we show that any distributive lattice is isomorphic to the set of reachable configurations of an Edge Firing Game. Together with the result of James Propp, saying that the set of reachable configurations of any Edge Firing Game is always a distributive lattice, this shows that the two concepts are equivalent.     

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.     

Weakly distributive domains (II)

In our previous work (Inform. and Comput., 2005, 202: 87–103), we have shown that for any ω-algebraic meet-cpo D, if all higher-order stable function spaces built from D are ω-algebraic, then D is finitary. This accomplishes the first of a possible, two-step process in solving the problem raised (LNCS, 1991, 530: 16–33; Domains and lambda-calculi, Cambridge Univ. Press, 1998) whether the category of stable bifinite domains of Amadio-Droste-Göbel (LNCS, 1991, 530: 16–33; Theor. Comput. Sci., 1993, 111: 89–101) is the largest cartesian closed full subcategory within the category of ω-algebraic meet-cpos with stable functions. This paper presents the results of the second step, which is to show that for any ω-algebraic meet-cpo D satisfying axioms M and I to be contained in a cartesian closed full sub-category using ω-algebraic meet-cpos with stable functions, it must not violate MI^∞. We introduce a new class of domains called weakly distributive domains and show that for these domains to be in a cartesian closed category using ω-algebraic meet-cpos, property MI^∞ must not be violated. Further, we demonstrate that principally distributive domains (those for which each principle ideal is distributive) form a proper subclass of weakly distributive domains, and Birkhoff’s M ₃ and N ₅ (Introduction to Lattices and order, Cambridge Univ. Press, 2002) are weakly distributive (but non-distributive). Then, we establish characterization results for weakly distributive domains. We also introduce the notion of meet-generators in constructing stable functions and show that if an ω-algebraic meet-cpo D contains an infinite number of meet-generators, then [D → D] fails I. However, the original problem of Amadio and Curien remains open.     

Weakly distributive domains(Ⅱ)

In our previous work (Inform. and Comput., 2005, 202: 87–103), we have shown that for any ω-algebraic meet-cpo D, if all higher-order stable function spaces built from D are ω-algebraic, then D is finitary. This accomplishes the first of a possible, two-step process in solving the problem raised (LNCS, 1991, 530: 16–33; Domains and lambda-calculi, Cambridge Univ. Press, 1998) whether the category of stable bifinite domains of Amadio-Droste-G?bel (LNCS, 1991, 530: 16–33; Theor. Comput. Sci., 1993, 111: 89–101) is the largest cartesian closed full subcategory within the category of ω-algebraic meet-cpos with stable functions. This paper presents the results of the second step, which is to show that for any ω-algebraic meet-cpo D satisfying axioms M and I to be contained in a cartesian closed full sub-category using ω-algebraic meet-cpos with stable functions, it must not violate MI^∞. We introduce a new class of domains called weakly distributive domains and show that for these domains to be in a cartesian closed category using ω-algebraic meet-cpos, property MI^∞ must not be violated. Further, we demonstrate that principally distributive domains (those for which each principle ideal is distributive) form a proper subclass of weakly distributive domains, and Birkhoff’s M ₃ and N ₅ (Introduction to Lattices and order, Cambridge Univ. Press, 2002) are weakly distributive (but non-distributive). Then, we establish characterization results for weakly distributive domains. We also introduce the notion of meet-generators in constructing stable functions and show that if an ω-algebraic meet-cpo D contains an infinite number of meet-generators, then [D → D] fails I. However, the original problem of Amadio and Curien remains open.     

Resolution-based decision procedures for the universal theory of some classes of distributive lattices with operators

We establish a link between the satisfiability of universal sentences with respect to classes of distributive lattices with operators and their satisfiability with respect to certain classes of relational structures. This justifies a method for structure-preserving translation to clause form of universal sentences in such classes of algebras. We show that refinements of resolution yield decision procedures for the universal theory of some such classes. In particular, we obtain exponential space and time decision procedures for the universal clause theory of (i) the class of all bounded distributive lattices with operators satisfying a set of (generalized) residuation conditions, and (ii) the class of all bounded distributive lattices with operators, and a doubly-exponential time decision procedure for the universal clause theory of the class of all Heyting algebras.     

Lattices of processes in graphs and congruences on ideals in distributive lattices

We consider the class of lattices of processes in graphs and its relationship to the class of all distributive lattices.Translated from Kibernetika i Sistemnyi Analiz, No. 1, pp. 162–165, January–February, 1992.     

Polynomial permutations on bounded commutative directoids with an antitone involution

Main results of Dorninger and L?nger (J Pure Appl Math 40:441–449, 2007) concerning polynomial permutations on bounded lattices with an antitone involution are generalized to the case of bounded commutative directoids.     

On derivations of lattices

In this paper, we introduce the notion of derivation for a lattice and discuss some related properties. We give some equivalent conditions under which a derivation is isotone for lattices with a greatest element, modular lattices, and distributive lattices. We characterize modular lattices and distributive lattices by isotone derivation. Moreover, we prove that if d is an isotone derivation of a lattice L, the fixed set Fix_d(L) is an ideal of L. Finally, we prove that D(L) is isomorphic to L in a distributive lattice L.     

Remarks on minimal solutions of a system of fuzzy relation equations over complete infinitely distributive lattices

In Section 3.6 of Fuzzy relation equations and their applications to knowledge engineering. Kluwer Academic Publishers, Boston (1989), Di Nola et al. presented a procedure to find a minimal solution from a fixed solution of a system of fuzzy relation equations over complete infinitely distributive lattices, and put the question: is the minimal solution found by the procedure unique or not? In this paper, we give a negative answer to the question and make some further remarks. We not only give a necessary and sufficient condition for the uniqueness of such minimal solutions, but also characterize the existence of the least solution and a unique solution of a system of fuzzy relation equations over complete infinitely distributive lattices.     

A generalized finite difference method using Coatmèlec lattices

Generalized finite difference methods require that a properly posed set of nodes exists around each node in the mesh, so that the solution for the corresponding multivariate interpolation problem be unique. In this paper we first show that the construction of these meshes can be computerized using a relatively simple algorithm based on the concept of a Coatmèlec lattice. Then, we present a generalized finite difference method which provides a numerical solution of a partial differential equation over an arbitrary domain, using the generated meshes. The accuracy and mesh adaptivity of the method is evaluated using elliptical equations in several domains.     

On congruences of weak lattices

We characterize when an equivalence relation on the base set of a weak lattice \(\mathbf{L}=(L,\sqcup ,\sqcap )\) becomes a congruence on \(\mathbf{L}\) provided it has convex classes. We show that an equivalence relation on L is a congruence on \(\mathbf{L}\) if it satisfies the substitution property for comparable elements. Conditions under which congruence classes are convex are studied. If one fundamental operation of \(\mathbf{L}\) is commutative then \(\mathbf{L}\) is congruence distributive and all congruences of \(\mathbf{L}\) have convex classes.     

On the Structure of (Weak) Inverses of an (Weakly) Invertible Finite Automaton

In this paper, we first give a method by which, for any weakly invertible finite automatonM with delay τ, the set of all weak inverse finite automata of M with delay τ can beconstructed. We then give a method by which, for any invertible one, all its inverses with delayτ can also be constructed.     

On finite automata with limited nondeterminism

We develop a new algorithm for determining if a given nondeterministic finite automaton is limited in nondeterminism. From this, we show that the number of nondeterministic moves of a finite automaton, if limited, is bounded by where is the number of states. If the finite automaton is over a one-letter alphabet, using Gohon's result the number of nondeterministic moves, if limited, is less than . In both cases, we present families of finite automata demonstrating that the upper bounds obtained are almost tight. We also show that the limitedness problem of the number of nondeterministic moves of finite automata is PSPACE-hard. Since the problem is already known to be in PSPACE, it is therefore PSPACE-complete. Received: 14 June 1994 / 3 December 1997     

On filter theory of residuated lattices

The aim of this paper is to develop the filter theory of general residuated lattices. First, we extend some particular types of filters and fuzzy filters in BL-algebras and MTL-algebras naturally to general residuated lattices, and further enumerate some relative results obtained in BL-algebras or MTL-algebras, which still hold in general residuated lattices. Next, we introduce the concepts of regular filters and fuzzy regular filters to general residuated lattices, which are two new types of filters and fuzzy filters, and derive some of their characterizations. Finally, we discuss the relations between (fuzzy) regular filters and several other special (fuzzy) filters, and also characterize some special classes of residuated lattices by filters or fuzzy filters.     

(Full) Leakage resilience of Fiat-Shamir signatures over lattices

Fiat-Shamir is a mainstream construction paradigm of lattice-based signature schemes. While its theoretical security is well-studied, its implementation security in the presence of leakage is a relatively under-explored topic. Specifically, even some side-channel attacks on lattice-based Fiat-Shamir signature (FS-Sig) schemes have been proposed since 2016, little work on the leakage resilience of these schemes appears. Worse still, the proof idea of the leakage resilience of FS-Sig schemes based on traditional number-theoretic assumptions does not apply to most lattice-based FS-Sig schemes. For this, we propose a framework to construct fully leakage resilient lattice-based FS-Sig schemes in the bounded memory leakage (BML) model. The framework consists of two parts. The first part shows how to construct leakage resilient FS-Sig schemes in BML model from leakage resilient versions of non-lossy or lossy identification schemes, which can be instantiated based on lattice assumptions. The second part shows how to construct fully leakage resilient FS-Sig schemes based on leakage resilient ones together with a new property called state reconstruction. We show almost all lattice-based FS-Sig schemes have this property. As a concrete application of our fundamental framework, we apply it to existing lattice-based FS-Sig schemes and provide analysis results of their security in the leakage setting.     

On the uniform finite generation of SO(n, )

A Lie group G, generated by two one-parameter subgroups is said to be uniformly finitely generated by them if there exists a positive integer N such that every element of G can be expressed as a product of at most N elements chosen alternately from the two one-parameter subgroups. In this paper we construct pairs of generators of so(n) whose one-parameter subgroups uniformly finitely generate SO(n) and as a consequence, we put an upper bound on the number of switches required to join any two points on a manifold M trajectories of two particular vector fields on M.