Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [lattices]

The theory of lattices, partially ordered sets all subsets of which have suprema and infima inside the set.

0
votes
0answers
25 views

Sufficient conditions for an analysis using a monotone framework to converge

We define a monotone framework as follows: $\begin{align*} in(\ell) &=\begin{cases} \mathrm{Initial} & \text{when $\ell\in$ Entry Labels}\\\\ \bigoplus \{out(\ell') \mid (\ell',\ell) \in \...
0
votes
1answer
63 views

How to Compute the Fixed Point on a DataFlow Lattice

Wondering the general overview of how to compute the fixed point on a program's dataflow lattice. A fixed point of a function $f(x)$ is one where the output of the function equals the input, so: $$f(...
0
votes
1answer
92 views

How to Construct a Lattice from Program Statements

In order to optimize a program, I am trying to figure out how the idea of a lattice applies to data-flow graphs, as introduced by this presentation (first diagram below). The lattice seems to take a ...
1
vote
1answer
113 views

A way to convert a binary tree into a grid

Wondering if there is a way to convert a binary tree into a grid such as this: ...
1
vote
1answer
62 views

How do I find depth and height of all nodes in a bounded semilattice?

I'm writing a program where I have a bounded semilattice (it has a root element at the top, all edges point downwards, and a node may have multiple parents). I need to precompute each node's depth (...
1
vote
0answers
56 views

Can the standard knapsack problem be solved using LLL?

It is well-known that the Merkle–Hellman knapsack cryptosystem can be solved using the LLL algorithm. In the Merkle-Hellman knapsack cryptosystem, we're trying to find a solution $x_i \in \{0,1\}$ ...
4
votes
1answer
33 views

Closure operator and set of fixpoint

In chapter 2.2 of Giacobazzi, Roberto; Ranzato, Francesco, Uniform closures: Order-theoretically reconstructing logic program semantics and abstract domain refinements, Inf. Comput. 145, No.2, 153-...
7
votes
2answers
1k views

Algorithm to generate self-avoiding random walk on a lattice

Where can I find some code to generate random self-avoiding walks on 2 and 3-dimensional lattices whose side-lengths are powers of two? The walk should pass through every point on the lattice More ...
5
votes
2answers
601 views

Testing if a given DAG is a lattice

I am given a directed acyclic graph (DAG) with a unique source and sink. Is there an efficient way to test whether the partial order represented by this graph is a lattice? In other words, I need to ...
3
votes
1answer
64 views

Finding optimal set for a sum of a product function over a 2D lattice

Given a 2D lattice with coordinates $1 \leq x \leq c$ and $1 \leq y \leq d$, we define $f(x, y) = xy$. We wish to find a boolean function $I(x,y)$ that determines in $O(1)$ time whether or not $(x,y)...
2
votes
1answer
70 views

Data-flow analysis problem adjust to Ullman-Aho's framework?

I am reading the classical book "Compilers. Principles, techniques and tools" by Aho et alii. On chapter 9.3 they talk about a general framework to solve data-flow analysis problems that use a ...
3
votes
1answer
525 views

Relation between Lattice and Boolean Algebra

In discrete math, I have read that lattice is a generalized form of boolean lattice. But those places where boolean algebra is mentioned, they don't tell about lattices (digital logic, binary,...). ...
1
vote
1answer
51 views

Approximate Nearest Neighbour Problem in Spherical Setting

There has been significant literature in solving the (Approximate) Nearest Neighbour Problem in the spherical setting in the $\mathbb{R}^n$ using Angular and Spherical LSH and other lattice sieving ...
5
votes
0answers
49 views

Correctness of a zigzag algorithm to find the most similar vector in a bounded integer lattice

I am currently working on an integer lattice problem, called the "most similar vector problem," and wondering if can be solved correctly by a simple "zig-zagging" algorithm. Given a real vector $u \...
3
votes
1answer
49 views

“Most Similar Vector Problem” on an Integer Lattice

I am currently working on problem that I think could be expressed as an integer lattice problem, and hoping to find some guidance on this forum. Given $u \in \mathbb{R}^n$ and a bounded integer ...
3
votes
2answers
230 views

Halting Problem and Turing Degree and Reduction? [closed]

This is a Local Olympiad question on computation and computer science on 2013. How can explain it and says some hint for understanding such an example question. for $ A \subseteq \mathbb{N}$ we ...
1
vote
0answers
142 views

Algorithms to generate random orthogonal basis for given Lattice

Suppose I want to generate a $n$-dimentional (random) Lattice, and then output a list of all orthogonal vectors of length $d$. What are the possible algorithms to do this, in poly-time? one way ...
2
votes
1answer
106 views

Monotone Frameworks: Transfer functions for flow edges instead of labels

So, in generic program analysis, we have a lattice $L$ with a join operation $\sqcup$, program with statements labelled, and for each label $b$, a transfer function $F_b : L \rightarrow L$. The goal ...
5
votes
1answer
299 views

What does Tarski's Fixed-Point theorem give us that that Y-Combinator does't

I'm taking a graduate course on the theory of functional programming, based on Paul Taylor's "Practical Foundations of Mathematics." I understand the statement of Tarski's theorem about how for any $\...
1
vote
1answer
101 views

Help in understanding exactly how lattices used as one way functions for hashing

(This question is related to homework) I am doing a cryptography course via long distance and we have been given an assignment which is based on lattice-based cryptography. I have spent the majority ...
3
votes
1answer
109 views

Unranking paths in a graph/lattice

A ranking algorithm determines the position (or rank) of a combinatorial object among all the objects (with respect to a given order); an unranking algorithm finds the object having a specified rank. ...
15
votes
6answers
6k views

What are lattices used for?

Wikipedia says: Complete lattices appear in many applications in mathematics and computer science Is it just referring to the fact that the standard Boolean algebra used in computation is a ...
12
votes
1answer
2k views

Is there a data-structure for semilattices similar to a tree data-structure?

If we regard a tree as a partial ordered set, it becomes a special case of a join-semilattice. For a join-semilattice, we want to be able to compute the (unique) least upper bound of two elements (...
3
votes
1answer
830 views

Security Lattice Construction

I am having a problem trying to solve a question on a past paper asking to design a security lattice. Here is the question: The AB model (Almost Biba) is a model for expressing integrity policies ...