Search Results

The two notions are equivalent if you take continuity with respect to the Scott topology (and not the one you define with the closure operators). Let $(X,\leq_X)$ and $(Y,\leq_Y)$ be dcpos. We say th …

This question is motivated by Linear Feedback Shift Registers, which cycle through $\{0,1\}^n \setminus \{(0,\ldots,0)\}$ by shifting and applying a small set of XOR operations. Let $n>1$ be an intege …

First, we note that $\mathbb{IR}$ is ordered by $[a,b] \sqsubseteq [c,d]$ iff $[c,d] \subseteq [a,b]$, which makes $\mathbb{IR}$ into a domain. Now suppose $f: [-a,a]\to \mathbb{IR}$ is Scott-continuo …

This answers @user3078439's question in his comment to my original answer. First, a short argument to show that if $P,Q$ are domains and $f:P\to Q$ is Scott-continuous, then $f$ is order preserving. …

(This question actually arose in real life when dealing with status bits with mutual influence.) Let $G=(V,E)$ be a connected, simple, undirected graph with $|V| \geq 2$. For $v\in V$, let $N_G(v) = …

We have a group of $n$ people who must make a journey of length $d$. They are to start together, and their goal is to arrive at the destination at same time. They have a single bicycle, which they rid …

Let $n>1$ be an integer. For $a,b\in \{0,1\}^n$ let $d_h(a, b)$ denote the Hamming distance of $a$ and $b$. For $k\in \{1,\ldots,n-1\}$ let $H(n,k)$ be the graph on $\{0,1\}^n$ given by the edge set $ …

We consider any non-negative integer as an ordinal, that is $0=\emptyset$ and $n=\{0,\ldots,n-1\}$ for every positive integer. Let $\{0,1\}^n$ denote the set of $\{0,1\}$-vectors of length $n$. Define …

Motivation. In computer science, addition of integers $a+b$ can be approximated by a very fast operation: $(a,b)\mapsto (a\oplus b) \oplus ((a\land b) \ll 1)$, where $\oplus$ denotes bitwise XOR, $\la …

Let $n\in\mathbb{N}$ be a positive integer. Let $\{0,1\}^{(2^n)}$ be the set of $0,1$-sequences of length $2^n$. For $a,b\in \{0,1\}^{(2^n)}$ let $d_h(a,b)$ be the Hamming distance between $a$ and $b$ …

This is a strengthening of an older question. Is there a positive integer $c_0$ with the following property? For every integer $n\geq c_0$ there is a function $f:\{0,1\}^{c_0}\to\{0,1\}$ such that th …

Is $\;\big\{(a,b,c)\in\mathbb{N}^3: \big(\exists m,n,\ell \in (\mathbb{N}\setminus\{0,1,2\})\big): a^m + b^n= c^\ell\big\}\;$ computable?

Donald Knuth introduced a fast, bit-wise approximation to integer addition by $$(a,b) \mapsto a \, ^{\land} \, b \, ^{\land} \, ((a \text{ & } b) \ll 1)$$ where $a,b$ are given in binary and $\,^{\lan …

Let $\text{Mat}(n\times n,\mathbb{Z})$ denote the collection of integer $n\times n$ matrices. We say $M\in \text{Mat}(n\times n,\mathbb{Z})$ is a power matrix if there is an integer $k>1$ and a matrix …

Let $\mathbb{N}$ denote the set of positive integers, and let $G=(V,E)$ be a finite simple, undirected graph. Given $f:V\to \mathbb{Z}$ we define the neighborhood sum function $\mathrm{nsum}_f:V\to\ma …