The Experts below are selected from a list of 7635 Experts worldwide ranked by ideXlab platform

Miguel Couceiro - One of the best experts on this subject based on the ideXlab platform.

  • Interpolation by polynomial functions of Distributive Lattices : a generalization of a theorem of R. L. Goodstein
    Algebra Universalis, 2013
    Co-Authors: Miguel Couceiro, Tamas Waldhauser
    Abstract:

    We consider the problem of interpolating functions partially defined over a Distributive Lattice by means of Lattice polynomial functions. Goodstein's theorem solves a particular instance of this interpolation problem on a Distributive Lattice L with least and greatest elements 0 and 1, respectively: given a function f : {0, 1} n → L , there exists a Lattice polynomial function p:Ln→L such that p| {0,1} n = f if and only if f is monotone; in this case, the interpolating polynomial p is unique. We extend Goodstein’s theorem to a wider class of partial functions f:D→L over a Distributive Lattice L, not necessarily bounded, and where D⊆Ln is allowed to range over n-dimensional rectangular boxes D={a1,b1}×...×{an,bn} with ai,bi∈L and ai

  • General Interpolation by Polynomial Functions of Distributive Lattices
    2012
    Co-Authors: Miguel Couceiro, Didier Dubois, Henri Prade, Agnès Rico, Tamas Waldhauser
    Abstract:

    For a Distributive Lattice $L$, we consider the problem of interpolating functions $f\colon D\to L$ defined on a finite set $D\subseteq L^n$, by means of Lattice polynomial functions of $L$. Two instances of this problem have already been solved. In the case when $L$ is a Distributive Lattice with least and greatest elements $0$ and $1$, Goodstein proved that a function $f\colon\{0,1\}^{n}\to L$ can be interpolated by a Lattice polynomial function $p\colon L^{n}\to L$ if and only if $f$ is monotone; in this case, the interpolating polynomial $p$ was shown to be unique.The interpolation problem was also considered in the more general setting where $L$ is a Distributive Lattice, not necessarily bounded, and where$D\subseteq L^{n}$ is allowed to range over cuboids $D=\left\{ a_{1},b_{1}\right\} \times\cdots\times\left\{ a_{n},b_{n}\right\} $ with $a_{i},b_{i}\in L$ and $a_{i}

  • Commuting polynomial operations of Distributive Lattices
    Order, 2012
    Co-Authors: Miguel Couceiro, Mike Behrisch, Erkko Lehtonen, Keith A. Kearnes, Ágnes Szendrei
    Abstract:

    We describe which pairs of Distributive Lattice polynomial operations commute.

C. J. Van Alten - One of the best experts on this subject based on the ideXlab platform.

  • complexity of the universal theory of bounded residuated Distributive Lattice ordered groupoids
    Algebra Universalis, 2019
    Co-Authors: Dmitry Shkatov, C. J. Van Alten
    Abstract:

    We prove that the universal theory and the quasi-equational theory of bounded residuated Distributive Lattice-ordered groupoids are both EXPTIME-complete. Similar results are proven for bounded Distributive Lattices with a unary or binary operator and for some special classes of bounded residuated Distributive Lattice-ordered groupoids.

  • Distributive and completely Distributive Lattice extensions of ordered sets
    International Journal of Algebra and Computation, 2018
    Co-Authors: W. Morton, C. J. Van Alten
    Abstract:

    It is known that a poset can be embedded into a Distributive Lattice if, and only if, it satisfies the prime filter separation property. We describe here a class of “prime filter completions” for posets with the prime filter separation property that are completely Distributive Lattices generated by the poset and preserve existing finite meets and joins. The free completely Distributive Lattice generated by a poset can be obtained through such a prime filter completion. We also show that every completely Distributive completion of a poset with the prime filter separation property is representable as a canonical extension of the poset with respect to some set of filters and ideals. The connections between the prime filter completions and canonical extensions are described and yield the following corollary: the canonical extension of any Distributive Lattice is the free completely Distributive Lattice generated by the Lattice. A construction that is a variant of the prime filter completion is given that can be used to obtain the free Distributive Lattice generated by a poset. In addition, it is shown that every Distributive Lattice extension of the poset can be represented by such a construction. Finally, we show that a poset with the prime filter separation property and the free Distributive Lattice generated by it generates the same free completely Distributive Lattice.

  • Distributive and completely Distributive Lattice extensions of ordered sets
    International Journal of Algebra and Computation, 2018
    Co-Authors: W. Morton, C. J. Van Alten
    Abstract:

    It is known that a poset can be embedded into a Distributive Lattice if, and only if, it satisfies the prime filter separation property. We describe here a class of “prime filter completions” for p...

  • Embedding Ordered Sets into Distributive Lattices
    Order, 2015
    Co-Authors: C. J. Van Alten
    Abstract:

    This paper investigates the class of ordered sets that are embeddable into a Distributive Lattice in such a way that all existing finite meets and joins are preserved. The main result is that the following decision problem is NP-complete: Given a finite ordered set, is it embeddable into a Distributive Lattice with preservation of existing meets and joins? The NP-hardness of the problem is proved by polynomial reduction of the classical 3SAT decision problem into it, and the NP-completeness by presenting a suitable NP-algorithm.

Heping Zhang - One of the best experts on this subject based on the ideXlab platform.

  • Decomposition theorem on matchable Distributive Lattices
    Discrete Applied Mathematics, 2014
    Co-Authors: Heping Zhang, Dewu Yang, Haiyuan Yao
    Abstract:

    A Distributive Lattice structure M(G) has been established on the set of perfect matchings of a plane bipartite graph G. We call a Lattice matchable Distributive Lattice (simply MDL) if it is isomorphic to such a Distributive Lattice. It is natural to ask which Lattices are MDLs. We show that if a plane bipartite graph G is elementary, then M(G) is irreducible. Based on this result, a decomposition theorem on MDLs is obtained: a finite Distributive Lattice L is an MDL if and only if each factor in any cartesian product decomposition of L is an MDL. Two types of MDLs are presented: J(mxn) and J(T), where mxn denotes the cartesian product between m-element chain and n-element chain, and T is a poset implied by any orientation of a tree.

  • a Distributive Lattice on the set of perfect matchings of a plane bipartite graph
    Order, 2003
    Co-Authors: Peter Che Bor Lam, Heping Zhang
    Abstract:

    Let G be a plane bipartite graph and M(G) the set of perfect matchings of G. The Z-transformation graph of G is defined as a graph on M(G): M,M′∈M(G) are joined by an edge if and only if they differ only in one cycle that is the boundary of an inner face of G. A property that a certain orientation of the Z-transformation graph of G is acyclic implies a partially ordered relation on M(G). An equivalent definition of the poset M(G) is discussed in detail. If G is elementary, the following main results are obtained in this article: the poset M(G) is a finite Distributive Lattice, and its Hasse diagram is isomorphic to the Z-transformation digraph of G. Further, a Distributive Lattice structure is established on the set of perfect matchings of any plane bipartite graph.

Ágnes Szendrei - One of the best experts on this subject based on the ideXlab platform.

Peter Schuster - One of the best experts on this subject based on the ideXlab platform.

  • The projective spectrum as a Distributive Lattice
    Cahiers de Topologie et Géométrie différentielles catégoriques, 2007
    Co-Authors: Henri Lombardi, Thierry Coquand, Peter Schuster
    Abstract:

    We construct a Distributive Lattice whose prime filters correspond to the homogeneous prime ideals of a graded commutative ring. This is the prime example of a non-affine scheme in a point-free context, and the model case of a fairly general glueing method for Distributive Lattices. We furthermore prove the projective form of the formal Hilbert Nullstellensatz.

  • the projective spectrum as a Distributive Lattice
    Cahiers de Topologie et Géométrie Différentielle Catégoriques, 2007
    Co-Authors: Thierry Coquand, Henri Lombardi, Peter Schuster
    Abstract:

    Nous construisons un treillis distributif dont les filtres premiers correspondent aux ideaux premiers homogenes d'un anneau commutatif gradue. Ceci donne un exemple caracteristique d'un schema non affine en topologie sans points, et d'une construction generale de recollements de treillis distributifs. Nous prouvons aussi une forme projective du "Theoreme des zeros" de Hilbert.