# Question
Title: Finding a set of edges $E$ such that every $s$-$t$-path contains at least 2 edges from $E$
Given an undirected graph $G$ and two vertices $s$ and $t$, i want to find a minimum set of edges $E$ in $G$ such that every (simple) $s$-$t$-path contains at least 2 edges from $E$.
Is this problem solvable in polynomial time? What if the paths should not contain 2, but $r$ edges in $E$?

I know that for $r=1$, this is equivalent to simply finding a minimum $s$-$t$-cut, so maybe the problem can be solved by using MaxFlowMinCut-techniques?

# Answer
*\[EDIT: updated to apply to undirected graphs\]*

**Lemma 1.** *The general problem (with $r$ given as input) is solvable in polynomial time.*

*Proof.* 1. Fix a problem instance $(G=(V, E), s, t)$. For brevity, define an *$r$-cut* to be any edge subset $C\subseteq E$ such that every $s$-$t$ path contains at least $r$ edges in $C$. The goal is to find a minimum-size $r$-cut. (Note that we use $E$ for the given edge set, and $C$ for the solution, whereas the post uses $E$ for the solution.)

2. Consider the following linear-program (LP) relaxation of the problem:

$$\begin{aligned} \textsf{minimize } &\textstyle ~\sum\_{e\in E} \ell\_e~ \textsf{ s.t.}\\ \pi\_s &{} = 0 \\ \pi\_t &{} \ge r \\ |\pi\_w - \pi\_u| & {} \le \ell\_e \le 1 && (e=\\{u,w\\} \in E) \end{aligned} $$

3. Note that the LP is indeed a relaxation of the original problem. Indeed, each solution $C$ to the given instance corresponds to the integer-valued LP solution $(\ell, \pi)$ of cost $|C|$ obtained by setting $\ell\_e = 1$ for $e\in C$, and setting each $\pi\_v$ to the distance from $s$ to $v$ in the graph where each edge $e$ is assigned length $\ell\_e$. Conversely, given any integer-valued feasible LP solution $(\ell, \pi)$, taking $C=\\{e \in E : \ell\_e = 1\\}$ gives a solution $C$ to the given instance, of size $|C|=\sum\_{e\in E} \ell\_e$.
4. Now, using any polynomial-time LP algorithm, compute a min-cost (possibly fractional) solution $(\ell, \pi)$ to the LP. Since the LP is a relaxation of the original problem, the cost $\sum\_{e\in E} \ell\_e$ of $(\ell, \pi)$ is a lower bound on the minimum size of any $r$-cut.
5. Compute a random integer LP solution $(\ell', \pi')$ and corresponding $r$-cut $C$ from $(\ell, \pi)$ using the following randomized-rounding scheme:

> 1. choose $\lambda \in \[0, 1)$ uniformly at random
> 2. let $\pi'\_v = \lfloor \pi\_v + \lambda \rfloor$ for each vertex $v\in V$
> 3. let $\ell'\_e = |\pi'\_w - \pi'\_u|$ for each edge $e=\\{u,w\\}\in E$
> 4. let $C=\\{e\in E: \ell'\_e = 1\\}$ be the $r$-cut corresponding to $(\ell', \pi')$

6. First observe that *$(\ell', \pi')$ is feasible.* In particular, for any edge $\\{u, w\\}\in E$, we have $$\ell'\_e = |\pi'\_w - \pi'\_u| = |\lfloor \pi\_w + \lambda \rfloor - \lfloor \pi\_u + \lambda \rfloor| \le 1$$ because $|(\pi\_w + \lambda) - (\pi\_u + \lambda)| \le \ell\_e \le 1$.
7. Next we bound the expected size of $C$.
8. Consider any edge $e=\\{u,w\\}\in E$. We will show $\Pr\[e\in C\] \le \ell\_e$.
9. Note $|\pi\_w - \pi\_u| \le \ell\_e \le 1$, so $$\Pr\[e\in C\] = \Pr\_\lambda\[|\lfloor \pi\_w + \lambda \rfloor \- \lfloor \pi\_u + \lambda \rfloor| = 1\] = |\pi\_w - \pi\_u| \le \ell\_e. $$ (The second equality above follows by calculation.)
10. So $\Pr\[e\in C\] \le \ell\_e$ for all $e\in E$.
11. Now, using also linearity of expectation, we have $E\[|C|\] = \sum\_{e\in E} \Pr\[e\in C\] \le \sum\_{e\in E} \ell\_e$.
12. That is, the expected size of the $r$-cut $C$ is at most the cost of $(\ell, \pi)$. Since the latter cost is at most OPT (the minimum size of any $r$-cut), it follows that the expected size of $C$ is at most OPT. $~~~~\Box$

BTW, since $|C|$ can't be less than OPT in any outcome, it follows that $C$ must be optimal, for any choice of $\lambda\in \[0, 1)$. Essentially, every optimal solution to the LP is a convex combination of optimal integer solutions.
> 2 votes

# Answer
Here's an idea, find the min-cut edge set $C$ with respect to the required $s$-$t$. Thus, all $s$-$t$ paths will have exactly one edge from this set $C$. Now collapse all end points of the edges present in $C$ into a single vertex (but do not include the edges as they would create self-loops). It is safe to assume that both $s$ and $t$ have not merged, otherwise, your required set does not exist. Now again, find a min-cut edge set $C'$ on this modified graph. Thus, all $s$-$t$ paths will have one edge from $C$ and another from $C'$. By construction, the set $C \cup C'$ would be minimal (but may not be minimum).
> 1 votes

# Answer
**Lemma 1**: If all $s$-$t$ simple paths go through some edge $(u, v)$ then all of them also go through the nodes $u$ and $v$. Conversely if all if all $s$-$t$ simple paths go through $u$ and $v$ and there is only one path between $u$ and $v$ then all the paths go through the edge $(u, v)$.

Start BFS at $s$ and construct the BFS tree. Let $t \in L\_{k}$.
**Lemma 2**: If there is a layer $L\_{i}$ for $i$ \< $k$ such that $L\_{i} = \\{ w \\}$ (only have one node) then all $s$-$t$ paths go through $w$.

Outline of the Proof: If we remove the node from the BFS tree, then there are no paths between $s$ and $t$. This is since all non-tree edges in a BFS tree are between nodes of the same or successive layers.

Using Lemma 1 and 2, we can find all pairs of layers $L\_{i}$, $L\_{i+1}$ such that $|L\_{i}| = |L\_{i+1}| = 1$ and $i+1 \leq k$ and the set of edges between the pairs of layers, is the set of edges you're looking for.
> 0 votes

---
Tags: algorithms, graphs, network-flow, path
---


# Question
Title: Invariance Textbook Problem: Clarification Needed
I am currently reading Michael Soltys' *Analysis of Algorithms (2nd Edition)*, and Problem 1.13 of the subsection titled *Invariance* reads:

> Let $n$ be an odd number, and suppose that we have the set $\\{1,2,\dots,2n\\}$. We pick any two numbers $a$, $b$ in the set, delete them from the set, and replace them with $|{a-b}|$. Continue repeating this until just one number remains in the set; show that this remaining number must be odd.

However, I picked $n=3$ and performed the following.

* I start with $\\{1,2,3,4,5,6\\}$.
* I pick $1$ and $2$; I end up with $(\\{1,2,3,4,5,6\\}-\\{1,2\\})\cup\\{|{1-2}|\\}=\\{1,3,4,5,6\\}$.
* I pick $1$ and $6$; I end up with $\\{3,4,5\\}$.
* I pick $3$ and $5$; I end up with $\\{2,4\\}$.
* And finally, I pick $2$ and $4$; I end up with $\\{2\\}$.

Clearly, $2$ is not an odd number.

Is there something I misunderstood in my attempt?

# Answer
> 2 votes
I think they don't mean to consider a "set" of numbers (where $\\{3, 4, 5, 5\\} = \\{3, 4, 5\\}$) but rather a list or multiset of numbers.

In that case the result is true: initially the sum of the entries of the list is $n(2n+1)$ which is odd, and at each step the parity of the sum of the entries is preserved. When you choose $a, b$, the sum changes from its old value $s$ to $s-a-b+ |b-a|$. If $a, b$ are even then $-a-b+|b-a|$ is clearly even, if they are both odd then $-a-b$ is even as is $|b-a|$, and if one is even and one odd then $-a-b$ is odd and $|b-a|$ is odd so $-a-b+|b-a|$ is odd+odd=even.

---
Tags: algorithms, proof-techniques, induction, loop-invariants
---


# Question
Title: Number of ways in which a '?' in a given string can be replaced with numbers from [0-9]
I came across this interesting problem in a test and I couldn't complete it.

There is a string given s which can consists of numbers between 0-9 and '?'. In place of '?' we can insert any of the numbers between 0 to 9. We need to find the number of ways in which it can be done so that no two adjacent numbers are same.

For e.g: ?2 should return 9 as there are 9 ways to do this. 02 12 32 42 52 62 72 82 92

???should give 810

I tried naive brute force approach like creating conditions based on the position of? but that took me nowhere.

So thought maybe it could be solved recursively. But unable to form a logic.

I'd appreciate to know the intuition behind solving this problem. I can do the implementation.

# Answer
If you try to use recursion naively, you'll attempt to solve the problem for $w a$, where $w$ is a string and $a$ is a character (the possible characters being $\\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ?\\}$). This will fail, since the number of possibilities for $w a$ depends not only on the number of possibilities for $w$, but also on the last letter of $w$, because that influences the possibilities for filling $a$ if it happens to be a "?".

Slightly less naively, you can do a bit of dynamic programming. Assume you have a table of the number of possibilities for filling $w$ *assuming that if the last letter of $w$ is a "?" then it must be filled with $i$*, for $i = 0, …, 9$. Try to build the same table for $w a$. Try to bootstrap the process for the empty string, and at the end, when you're done for the whole string, you should be able to sum the values in the table to get the result.

And slightly less naively than that, you can

* Identify runs of consecutive "?",
* Remark that the total number of possibilities is the product of the numbers of possibilities for each run, since they are "independent" (assuming that there not already two adjacent identical digits in the input string),
* Compute the number of possibilities for a run $d\_1 ???…??? d\_2$, where $d\_1, d\_2$ are digits and there are $n$ times "?" in the middle (don't forget to special case runs of "?" at the beginning or at the end; another hint: distinguish the cases $d\_1 = d\_2$ and $d\_1 ≠ d\_2$),
* Conclude.
> 1 votes

---
Tags: algorithms, dynamic-programming, recursion
---


# Question
Title: How, if possible, can we efficiently compute with lazy data structures in -calculus?
In Haskell, we can use the following code to define fibonacci numbers,

```
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

```

And its time complexity is linear.

I cannot find a way to do it in lambda calculus or combinatory logic.

With Y combinator, it leads to exponential steps to evaluate.

Is it possible in lambda calculus? Is there any formal system that can evaluate it in linear steps?

# Answer
Although Haskell of course has native recursion, we can ignore it and implement the Y combinator $λf. (λx. f (x x)) (λx. f (x x))$ literally, using a `newtype` to get it through the type system, and a `NOINLINE` pragma to work around a GHC bug.

A `fibs` implementation based on the Y combinator runs in a *quadratic* number of steps, not exponential. This effectively builds the list a linear number of times, with each list depending only on the single list at the next level (try it online):

```
newtype Mu t = Mu (Mu t -> t)
{-# NOINLINE yStep #-}
yStep f (Mu x) = f (x (Mu x))
y f = yStep f (Mu (yStep f))
fibs = y (\f -> 1 : 1 : zipWith (+) f (tail f))
main = mapM_ print fibs

```

Just to see that nothing funny is going on, we can ignore Haskell’s builtin lists too and encode everything with functions (try it online):

```
{-# LANGUAGE RankNTypes #-}
newtype Mu t = Mu (Mu t -> t)
newtype List t = List (forall r. (t -> List t -> r) -> r)
{-# NOINLINE yStep #-}
yStep f (Mu x) = f (x (Mu x))
y f = yStep f (Mu (yStep f))
cons x xs = List (\f -> f x xs)
car (List xs) = xs (\x _ -> x)
cdr (List xs) = xs (\_ xs' -> xs')
zipWith' f = y (\go xs ys -> cons (f (car xs) (car ys)) (go (cdr xs) (cdr ys)))
fibs = y (\f -> cons 1 (cons 1 (zipWith' (+) f (cdr f))))
main = y (\go xs -> print (car xs) >> go (cdr xs)) fibs

```

We’re still relying on Haskell’s lazy evaluation. That’s not a problem—we can use a call-by-need lambda calculus interpreter. But alternatively, we can add an explicit laziness primitive to a call-by-value language, like in this JavaScript translation that still runs in quadratic steps (try it online):

```
const dummy = x => x;
const lazy = f => {
  let value;
  let evaluated = false;
  return () => {
    if (!evaluated) {
      value = f(dummy);
      evaluated = true;
    }
    return value;
  };
};
const force = l => l(dummy);

const add = x => y => x + y;

const fix = f => (x => x(x))(x => f(y => x(x)(y)));
const lazyFix = f => (x => lazy(() => x(x)))(x => f(lazy(() => x(x))));
const cons = x => xs => f => f(x)(xs);
const car = xs => xs(x => xs1 => x);
const cdr = xs => xs(x => xs1 => xs1);
const zipWith = f =>
  fix(
    go => xs => ys =>
      lazy(() =>
        cons(f(car(force(xs)))(car(force(ys))))(
          go(cdr(force(xs)))(cdr(force(ys)))
        )
      )
  );
const fibs = lazyFix(p =>
  cons(1n)(lazy(() => cons(1n)(zipWith(add)(p)(cdr(force(p))))))
);

for (let p = force(fibs); ; p = force(cdr(p))) console.log(car(p));

```

Of course, if we’re going to add laziness primitives, we might as well directly add an efficient primitive lazy fixed-point combinator, so we can write the solution that runs in a linear number of steps (try it online).

```
const dummy = x => x;
const lazyFix = f => {
  let value;
  let evaluated = false;
  const lazyValue = () => {
    if (!evaluated) {
      value = f(lazyValue);
      evaluated = true;
    }
    return value;
  };
  return lazyValue;
};
const lazy = lazyFix;
const force = l => l(dummy);

const add = x => y => x + y;

const fix = f => (x => x(x))(x => f(y => x(x)(y)));
const cons = x => xs => f => f(x)(xs);
const car = xs => xs(x => xs1 => x);
const cdr = xs => xs(x => xs1 => xs1);
const zipWith = f =>
  fix(
    go => xs => ys =>
      lazy(() =>
        cons(f(car(force(xs)))(car(force(ys))))(
          go(cdr(force(xs)))(cdr(force(ys)))
        )
      )
  );
const fibs = lazyFix(p =>
  cons(1n)(lazy(() => cons(1n)(zipWith(add)(p)(cdr(force(p))))))
);

for (let p = force(fibs); ; p = force(cdr(p))) console.log(car(p));

```

So I guess the formal system you’re looking for is lambda calculus with a primitive lazy fixed-point combinator.
> 3 votes

# Answer
In terms of the combinators $S = λxλyλz·xz(yz)$, $K = λxλy·x$, $I = λx·x$ and $B = λxλyλz·x(yz)$ and letting $C\_n$ denote the Church numerals, with $C\_0 = K I$, $C\_1 = I$, $C\_{n+1} = S B C\_n$, for $n = 1, 2, 3, ...$ (noting also that $S B (K I) = I$ under η-equivalence), something that is closer to what you're looking for is also a typical example showing how to deal with primitive recursion. The Fibonacci sequence is $$1, 1, 2 = 1 + 1, 3 = 1 + 2, 5 = 2 + 3, 8 = 3 + 5, ⋯.$$

The Church numerals have the property that $C\_n f x = f^n x$, where $f^n$ denotes the $n$-fold composition of $f$ with itself, e.g. $C\_2 f x = f (f x)$ and $C\_3 f x = f (f (f x))$. Since the Fibonacci sequence's recursive definition also involves the addition operator, we'll also need the operator for adding Church numerals, $C\_{m+n} f x = C\_m f (C\_n f x)$. Up to η-equivalence $C\_{m+n} = B S (B B) C\_m C\_n$. Let $A = B S (B B)$

Then $$ K C\_1 C\_1 = C\_1,\\ J K C\_1 C\_1 = K C\_1 (A C\_1 C\_1) = K C\_1 C\_2 = C\_1,\\ J^2 K C\_1 C\_1 = J K C\_1 C\_2 = K C\_2 (A C\_1 C\_2) = K C\_2 C\_3 = C\_2,\\ J^3 K C\_1 C\_1 = J^2 K C\_1 C\_2 = J K C\_2 C\_3 = K C\_3 (A C\_2 C\_3) = K C\_3 C\_5 = C\_3, $$ and so on ... where $$J k u v = k v (A u v) = S k (A u) v = B (S k) A u v = C B A (S k) u v = B (C B A) S k u v,$$ which also uses the combinator $C = λxλyλz·xzy$. Therefore, the $n$-th Fibonacci number, presented as a Church numeral, is $C\_n J K C\_1 C\_1$, where $J = B (C B A) S$ and $A = B S (B B)$.

Running this in Combo (which I put up on GitHub), with the η-rule turned on, e.g. $$ A = B\ S\ (B\ B),\ J = B\ (C\ B\ A)\ S,\ SB = S\ B,\\ C1 = I,\ C2 = SB\ I,\ C3 = SB\ C2,\ C4 = SB\ C3,\\ C4\ J\ K\ C1\ C1 $$ for the $4$-th Fibonacci number, I get $4, 7, 18, 26, 37, 49, 63, 80, 102, 132, ...$ steps for the cases $n = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ...$. So, it's probably quadratic, but not exponential. It can't be linear with Church numerals, since the numerals, themselves, are already linear (instead of logarithmic); i.e. they're essentially numerals in base $1$. You need positional numerals in base $2$ or higher. Then, it might become $n \log n$.

Further, you can probably roll up the first $n$ factor into a $\log n$ factor, too, if you exponentiate the iteration. The $1$-step iteration of $u v$ is into $v (u + v)$, which can be presented in vector-matrix form as $A w$, where $w$ is the vector for $u v$ and $A$ is a suitably-defined matrix. So, then, the $2$-step iteration is $A^2 w$, $4$-steps is $(A^2)^2 w$, $8$-steps is $((A^2)^2)^2 w$, and - in general - the $2^k$-step iteration is $A^{2^k} w$.
> 0 votes

---
Tags: lambda-calculus, functional-programming, combinatory-logic
---


# Question
Title: How does the half-integer spanning-tree problem contain the TSP?
I am trying the understand the following statement from the book of Grotschel, Lovasz and Schrijver:

Here, $\delta(W)$ is the set of edges incident to a set of vertices $W$.

They define an optimization problem whose solution is a nonnegative real vector. If we add a constraint that all elements of the vector must be integers, then the problem is equivalent to the minimum spanning tree problem, and therefore is solvable in polynomial time. However, if the constraint says that all elements of the vector must be half-integers (that is, either an integer or an integer plus $1/2$), the problem becomes NP-complete, as it includes the symmetric travelling salesman problem.

I do not see the connection: why does the problem with half-integer constraints contain the TSP?

# Answer
> 2 votes
Reduction from Hamiltonian Cycle (which is just a special case of TSP anyway):

Take an unweighted graph $G$ and make into a complete weighted graph $G'$ by adding a heavy edge (say, $\ell(e) = 2n$) for every $e\not\in E(G)$, and keeping $\ell(e)=1$ for $e\in E(G)$.

For any vector $\mathbf{x}$ that is a solution to the half-integer spanning tree problem, the subset of edges $F$ with $\mathbf{x}(e) \> 0$ for $e\in F$ must obviously make a connected subgraph of $G$. This implies that $|F| \geq n-1$. If $|F| = n-1$, then $(V(G), F)$ is a tree and contains at least two leaves $u,v$. The edges $e\_u,e\_v$ incident on these leaves must have a weight of 1 in $\mathbf{x}$. Therefore the combined weight $\sum\_{e\in F} \mathbf{x}(e)$ is at least $\frac{n+1}{2}$. Also, if $|F| \geq n+1$, then of course the combined weight is at least $\frac{n+1}{2}$.

On the other hand, if $|F| = n$ and every edge has a weight of $\frac{1}{2}$ in $\mathbf{x}$, then the combined weight is only $\frac{n}{2}$. This is only possible if $(V(G), F)$ is a cycle.

Therefore, $\sum\_{e\in F} \mathbf{x}(e)\ell(e)$ can achieve a minimum value of $\frac{n}{2}$ if and only if $G$ contains a Hamiltonian cycle.

# Answer
> 0 votes
Let $P=u\_1,u\_2,\ldots$ a solution to the STSP with cost $l$, we associate to it the vector $x\_P$ such that $(x\_P)\_e = \frac{1}{2}\\#\\{i; \\{u\_i,u\_{i+1}\\}=e\\}$ (each time the tour takes an edge, we add $\frac{1}{2}$ to $x\_P$). It is a solution to $\frac{1}{2}$-Spanning Tree: let $W$ be a cut, the tour has to leave it and enter it at least once, so $x\_P\cdot\delta(W)\geq 1$. Here $x\cdot l = \frac{1}{2}c(P)$ where $c(P)$ is the usual cost associated with the tour $P$. Hence the miminum $\frac{1}{2}$-ST solution is at least half the minimum STSP solution.

EDIT: the following is wrong, see comments

The other way around, given $x$ a solution, we construct a multigraph on $V(G)$ by putting $2x\_{\\{u,v\\}}$ edges between each pair of vertices $u,v$. Now each vertex has degree at least $2$ (since $x\cdot \delta(\\{u\\})\ge 1$), so we find a tour the same way we find Eulerian tours in even degree graphs: find a cycle starting from the source, if some vertices aren't visited by the current tour $P$, we have at least two edges in $\delta(V(P))$, so we can leave, follow a path in $V(G)\setminus V(P)$ until we can go back to $P$, an obtain a bigger tour. A tour visiting all vertices uses a subset of the edges we built, and as such has weight at most $2x\cdot l$. Hence the minimum STSP solution is at most twice the miminum $\frac{1}{2}$-ST solution.

It follows the problems are equivalent.

---
Tags: reductions, minimum-spanning-tree, traveling-salesman
---


# Question
Title: How is `y λx.x y` parsed using the standard pure untyped lambda calculus conventions?
How would the following term in the pure untyped lambda calculus be parsed:

`y λx.x y`

The relevant conventions listed on https://en.wikipedia.org/wiki/Lambda\_calculus\_definition#Notation (as well as many texts on this subject) state:

1. Applications are assumed to be left associative: `M N P` is parenthesised as `((M N) P)`
2. The body of an abstraction extends as far right as possible: λx.M N is parenthesised as `(λx.(M N))` and not `((λx.M) N)`

There is no priority specified between these two conventions. In the case of `y λx.x y`, if the "applications are left associative" rule is first applied, we get `(y (λx.x)) y`, and if the "abstraction extends as far right as possible" rule is first applied, we get `y (λx.x y)`. Which one is considered correct, and on what basis?

Observations and thoughts:

I have tried this on some online tools, and this is what I observed:

I initially thought that the rule "abstraction extends as far right as possible" was equivalent to specifying that application binds tighter than abstraction. But this assumption may be wrong. Under this assumption, `y λx.x y` would be parsed as `(y (λx.x)) y`, since the "applications are left associative" rule would kick in first.

# Answer
> 4 votes
The left associativity of applications is only relevant when you have a sequence of applications. If it were correct to interpret `y λx.x y` as `y (λx.x) y`, then the left associativity rule would disambiguate it to `(y (λx.x)) y`. But that interpretation violates the rule that abstractions extend as far right as possible.

Normally one never writes `y λx.x y` unparenthesized, so I think it's best for parsers to reject it, but if I saw it I would guess that it means `y (λx.x y)`.

# Answer
> 0 votes
The λ-abstraction takes everything to the right, as far as it can, no matter what the surrounding context. So, it takes priority.

I tried $y\ λx·x\ y$ in Combo, which I put up on GitHub. I just added a "compile-only" option in it a few days ago. The expressions $(y\ λx·x)\ y$ and $y\ (λx·x)\ y$ (which get entered into "Combo", respectively as "(y \x.x) y" and "y (\x.x) y", respectively) both compile as $y\ I\ y$. The expressions $y\ λx·x\ y$ and $y\ (λx·x\ y)$ (i.e. "y \x.x y" and "y (\x.x y)", respectively) both get compiled as $y\ (T\ y)$. Parentheses aren't needed in "Combo". You could also go "a = \x.x, y a y" for the first cases or "b = \x.x y, y b" for the second cases.

---
Tags: lambda-calculus, parsers, ambiguity, syntax
---


title: Shortest regular expression possible

text:
# Question
Title: Shortest regular expression possible
The question asks to write the shortest regular expression possible to the following automaton:

I see only one way to tackle the problem:

Use one of the methods mentioned here How to convert finite automata to regular expressions? and then get a regular expression.

If for example I use the Transitive closure method, it will be hard to say that the regular expression at the end is "the shortest as possible".

My question is there any better way to tackle the problem than to use one of the conversion method of automata to regular expression.

I saw in this post Are there any specific mechanical ways to reduce a regular expression 'equation' to a more simple one? that minimizing regular expressions is very hard, so according to it, starting with a long regular expression and trying to "shrink" it is not a good approach.

# Answer
To solve this question, you should not blindly apply some algorithm. Instead, start by understanding what the given automaton does. When you do this, you will see that the automaton is needlessly complicated for the language it describes - so any direct translation from automata to regular expressions will probably be horrible.

Also, once you've figured out which language the automaton describes, it shouldn't be too difficult to come up with a regular expression and some sense of why this is the shortest you can hope for.
> 2 votes

# Answer
Frame it as the least fixed point solution to the following system in Kleene algebra: $$ A ≥ 1 + a B + b C,\quad B ≥ 1 + a D + b E,\quad C ≥ 1 + a D + b D,\\ D ≥ a B + b C,\quad E ≥ a C + b B,\quad A. $$ where the final term ($A$) indicates the "starting expression".

The worst case, generally, is cubic in the size of the system. One of the sample/test files in RegEx, which I put up on GitHub in the 2010's, shows the layout for a degree 4 system. The program "dfa" in it will be of particular use. If you run "dfa" on the demo file, you get a full matrix system with 4 variables.

As one optimization, here, substitute in for all the single-reference items (here: $A$ and $E$) and as another optimization, factor out (here: the $D$ in the inequation for $C$): $$ B ≥ 1 + a D + b a C + b b B,\quad C ≥ 1 + (a + b) D,\quad D ≥ a B + b C,\quad 1 + a B + b C. $$

The next best optimization is to in-line substitute $D$. It has the fewest references and no "$1 + ⋯$" in it: $$ B ≥ 1 + a (a B + b C) + b a C + b b B,\quad C ≥ 1 + (a + b) (a B + b C),\quad 1 + a B + b C. $$ Factor out the "B" and "C": $$ B ≥ 1 + (a a + b b) B + (a b + b a) C,\quad C ≥ 1 + (a + b) a B + (a + b) b C,\quad 1 + a B + b C. $$

You have a full system of degree 2 and you're making use of both variables in the starting expression, so I don't think you'll get any better than that. In general, the least fixed point solution to $$ B ≥ m + w B + x C,\quad C ≥ n + y B + z C $$ is $$ B = (w^\* x z^\* y)^\* (w^\* m + w^\* x z^\* n),\quad C = (z^\* y w^\* x)^\* (z^\* n + z^\* y w^\* m). $$

This can be more succinctly written as $$d = w^\* m,\quad e = z^\* n,\quad f = w^\* x,\quad g = z^\* y,\quad B = (f g)^\* (d + f e),\quad C = (g f)^\* (e + g d).$$

Applying this to the system on hand: $$m = 1,\quad n = 1,\quad w = a a + b b,\quad x = a b + b a,\quad y = (a + b) a,\quad z = (a + b) b,$$ and substituting in for $B$ and $C$, we get $$ w = a a + b b,\quad x = a b + b a,\quad y = (a + b) a,\quad z = (a + b) b,\\ d = w^\*,\quad e = z^\*,\quad f = w^\* x,\quad g = z^\* y,\\ 1 + a (f g)^\* (d + f e) + b (g f)^\* (e + g d). $$ Setting $v = a + b$, this can be written $$ v = a + b,\quad w = a a + b b,\quad x = a b + b a,\quad y = v a,\quad z = v b,\\ d = w^\*,\quad e = z^\*,\quad f = d x,\quad g = e y,\\ 1 + a (f g)^\* (d + f e) + b (g f)^\* (e + g d). $$

Just to check, this can be fed into "dfa" (which uses "|" instead of "+"). Strangely, I tried this two separate ways and it kept insisting that it's a much smaller system - namely this one (up to a change of notation): $$ A ≥ 1 + a B + b B,\quad B ≥ 1 + a D + b D,\quad D ≥ a B + b B,\quad A. $$ In other words, your $B = C$ and $D = E$. Oops. They are equivalent states. I didn't see that.

Apply the same methods to this system, instead. Factor $$ A ≥ 1 + (a + b) B,\quad B ≥ 1 + (a + b) D,\quad D ≥ (a + b) B,\quad A. $$ Remove the single references ($D$ and $A$): $$ B ≥ 1 + (a + b) (a + b) B,\quad 1 + (a + b) B. $$ Solve for $B$: $$B = ((a + b)(a + b))^\*,$$ and the result is $$1 + (a + b)((a + b)(a + b))^\*,$$ or more succinctly, $$v = a + b,\quad 1 + v (v v)^\*.$$

There's a lot of heuristics. The one we should have used at the outset is: equivalent state reduction (which "dfa" uses and used).

In general, though, I don't think there is a clean-cut one-size-fits-all series of optimizations, though the ones used easily crunched your example. In general, cubic is the worst case - provided you maximally share sub-expressions (as I did in the cases all throughout, above).
> 2 votes

---
Tags: regular-languages, automata, finite-automata, regular-expressions
---


# Question
Title: File conversion to binary format to save storage space
Our test log files are stored in .asc format. Each file contains around 5000 rows of these Logging Strings as shown in the image. I would like to reduce the size of these files.They are around 4-5 MBs each bringing the total folder size for one test run around 700-900 MBs. The files are output from the system in only .asc format so i might have to opt for post-processing in this case. **What would be the best way to reduce the size of the file, if i need reduction by a factor of 5 to 10?**

* Will a conversion to binary file format be suitable? If yes, is it going to be in .bin format or something else ?
* If i opt for lossless compression technique for size reduction what would be a better option? Is there a ready tool that would run the technique for me like 7zip or should i be writing a program by myself? \[*I couldn't find much information leading to this point hence had to ask here*\]

*Zip doesn't yield satisfactory result*

One more question i had is why is it called .asc file ? It looks to me more like a .csv file or a .txt file. Is it that i see it in this format because of the file viewers i use ( notepad/notepad++/excel). Based on the formatting seeing in the image, isn't this more appropriate to be called a .csv file? *This is just to enhance my knowledge about the difference between a csv, txt and .asc file.*

# Answer
> 0 votes
Unfortunately, conversion to a binary format will barely yield compression by a factor 2. Because your decimal numbers currently occupy 7 bytes, while a float takes 4 bytes. You can discard all repeating strings, which are useless, and pack the 17 final 0/1 values to 3 bytes. The date/times can be encoded as integers on 4 bytes (number of tenths of a second since a starting date).

# Answer
> 0 votes
The first column (1591231.911710) seems to be the number of seconds since some specific time (about 18 days earlier).

If you can preserve that time, " LoggingString := … 2021,02:38:57.0," becomes unnecessary, as it can be recalculated.

The times in the first column could be reduced by subtracting the previous line's value from each one.

So, the second line would be reduced to:

> 2.004776 70.66,13.4,…

Does the time need to have microsecond precision? If milliseconds are sufficient, some trailing digits could be removed:

> 2.005 70.66,13.4,…

Depending upon what they actually are, some further savings could be made by changing the values at the right the same way the time stamps were shortened, by recording them as the difference from the previous value. The "70.67"s would all become "0", and "13"s would become "0" or ".01" or "-.01".

And if those values all have at most 2 digits after the decimal point, that "." character could be removed.

And instances of "…,0,…" could even be reduced to "…,,…".

And since the whole thing now uses fewer than 17 distinct characters, each one could be packed into half a byte.

---

That should give an overall reduction in the lower end of the 5–10 range, and zipping the file might provide a little more saving.

Is it really worth the effort though, compared with the cost of additional storage?

# Answer
> 0 votes
The data consists of fixed text, and numbers that are multiples of 0.000001 or 0.1, converted to numbers or dates as text. So step 1 is that you multiply these numbers by 1,000,000 or 10 with an integer result.

Step 2 is recording not the numbers, but differences between consecutive number which are much smaller. And for the time information, you record the second differences. Then look up how h.264 store sequences of small integers with self-adjusting arithmetic coding with a different encoder for each number.

---
Tags: data-compression, binary, encoding-scheme, filesystems, storage
---


# Question
Title: How to convert finite automata to regular expressions?
Converting regular expressions into (minimal) NFA that accept the same language is easy with standard algorithms, e.g. Thompson's algorithm. The other direction seems to be more tedious, though, and sometimes the resulting expressions are messy.

What algorithms are there for converting NFA into equivalent regular expressions? Are there advantages regarding time complexity or result size?

This is supposed to be a reference question. Please include a general decription of your method as well as a non-trivial example.

# Answer
> 109 votes
There are several methods to do the conversion from finite automata to regular expressions. Here I will describe the one usually taught in school which is very visual. I believe it is the most used in practice. However, writing the algorithm is not such a good idea.

# State removal method

This algorithm is about handling the graph of the automaton and is thus not very suitable for algorithms since it needs graph primitives such as ... state removal. I will describe it using higher-level primitives.

### The key idea

The idea is to consider regular expressions on edges and then removing intermediate states while keeping the edges labels consistent.

The main pattern can be seen in the following to figures. The first has labels between $p,q,r$ that are regular expressions $e,f,g,h,i$ and we want to remove $q$.

Once removed, we compose $e,f,g,h,i$ together (while preserving the other edges between $p$ and $r$ but this is not displayed on this):

### Example

Using the same example as in Raphael's answer:

we successively remove $q\_2$:

and then $q\_3$:

then we still have to apply a star on the expression from $q\_1$ to $q\_1$. In this case, the final state is also initial so we really just need to add a star:

$$ (ab+(b+aa)(ba)^\*(a+bb))^\* $$

### Algorithm

`L[i,j]` is the regexp of the language from $q\_i$ to $q\_j$. First, we remove all multi-edges:

```
for i = 1 to n:
  for j = 1 to n:
    if i == j then:
      L[i,j] := ε
    else:
      L[i,j] := ∅
    for a in Σ:
      if trans(i, a, j):
        L[i,j] := L[i,j] + a

```

Now, the state removal. Suppose we want to remove the state $q\_k$:

```
remove(k):
  for i = 1 to n:
    for j = 1 to n:
      L[i,i] += L[i,k] . star(L[k,k]) . L[k,i]
      L[j,j] += L[j,k] . star(L[k,k]) . L[k,j]
      L[i,j] += L[i,k] . star(L[k,k]) . L[k,j]
      L[j,i] += L[j,k] . star(L[k,k]) . L[k,i]

```

Note that both with a pencil of paper and with an algorithm you should simplify expressions like `star(ε)=ε`, `e.ε=e`, `∅+e=e`, `∅.e=∅` (By hand you just don't write the edge when it's not $∅$, or even $ε$ for a self-loop and you ignore when there is no transition between $q\_i$ and $q\_k$ or $q\_j$ and $q\_k$)

Now, how to use `remove(k)`? You should not remove final or initial states lightly, otherwise you will miss parts of the language.

```
for i = 1 to n:
  if not(final(i)) and not(initial(i)):
    remove(i)

```

If you have only one final state $q\_f$ and one initial state $q\_s$ then the final expression is:

```
e := star(L[s,s]) . L[s,f] . star(L[f,s] . star(L[s,s]) . L[s,f] + L[f,f])

```

If you have several final states (or even initial states) then there is no simple way of merging these ones, other than applying the transitive closure method. Usually this is not a problem by hand but this is awkward when writing the algorithm. A much simpler workaround is to enumerate all pairs $(s,f)$ and run the algorithm on the (already state-removed) graph to get all expressions $e\_{s,f}$ supposing $s$ is the only initial state and $f$ is the only final state, then doing the union of all $e\_{s,f}$.

This, and the fact that this is modifying languages more dynamically than the first method make it more error-prone when programming. I suggest using any other method.

### Cons

There are a lot of cases in this algorithm, for example for choosing which node we should remove, the number of final states at the end, the fact that a final state can be initial, too etc.

Note that now that the algorithm is written, this is a lot like the transitive closure method. Only the context of the usage is different. I do not recommend implementing the algorithm, but using the method to do that by hand is a good idea.

# Answer
> 56 votes
### Method

The nicest method I have seen is one that expresses the automaton as equation system of (regular) languages which can be solved. It is in particular nice as it seems to yield more concise expressions than other methods.

Let $A= (Q,\Sigma,\delta,q\_0,F)$ an NFA without $\varepsilon$-transitions. For every state $q\_i$, create the equation

$\qquad \displaystyle Q\_i = \bigcup\limits\_{q\_i \overset{a}{\to} q\_j} aQ\_j \cup \begin{cases} \\{\varepsilon\\} &,\ q\_i \in F \\ \emptyset &, \text{ else}\end{cases}$

where $F$ is the set of final states and $q\_i \overset{a}{\to} q\_j$ means there is a transition from $q\_i$ to $q\_j$ labelled with $a$. If you read $\cup$ as $+$ or $\mid$ (depending on your regular expression definition), you see that this is an equation of regular expressions.

For solving the system you need associativity and distributivity of $\cup$ and $\cdot$ (string concatenation), commutativity of $\cup$ and Arden's Lemma¹:

> Let $L,U,V \subseteq \Sigma^\*$ regular languages with $\varepsilon \notin U$. Then,
>
> $\qquad \displaystyle L = UL \cup V \quad \Longleftrightarrow \quad L = U^\*V$

The solution is a set of regular expressions $Q\_i$, one for every state $q\_i$. $Q\_i$ describes exactly those words that can be accepted by $A$ when started in $q\_i$; therefore $Q\_0$ (if $q\_0$ is the initial state) is the desired expression.

---

### Example

For the sake of clarity, we denotate singleton sets by their element, i.e. $a = \\{a\\}$. The example is due to Georg Zetzsche.

Consider this NFA:

\[source\]

The corresponding equation system is:

$\qquad \begin{align} Q\_0 &= aQ\_1 \cup bQ\_2 \cup \varepsilon \\ Q\_1 &= bQ\_0 \cup aQ\_2 \\ Q\_2 &= aQ\_0 \cup bQ\_1 \end{align}$

Now plug the third equation into the second:

$\qquad \begin{align} Q\_1 &= bQ\_0 \cup a(aQ\_0 \cup bQ\_1) \\ &= abQ\_1 \cup (b \cup aa)Q\_0 \\ &= (ab)^\*(b \cup aa)Q\_0 \end{align}$

For the last step, we apply Arden's Lemma with $L = Q\_1$, $U = ab$ and $V = (b \cup aa) \cdot Q\_0$. Note that all three languages are regular and $\varepsilon \notin U = \\{ab\\}$, enabling us to apply the lemma. Now we plug this result into the first equation:

$\qquad \begin{align} Q\_0 &= a(ab)^\*(b \cup aa)Q\_0 \cup baQ\_0 \cup bb(ab)^\*(b \cup aa)Q\_0 \cup \varepsilon \\ &= ((a \cup bb)(ab)^\*(b \cup aa) \cup ba)Q\_0 \cup \varepsilon \\ &= ((a \cup bb)(ab)^\*(b \cup aa) \cup ba)^\* \qquad \text{(by Arden's Lemma)} \end{align}$

Thus, we have found a regular expression for the language accepted by above automaton, namely

$\qquad \displaystyle ((a + bb)(ab)^\*(b + aa) + ba)^\*.$

Note that it is quite succinct (compare with the result of other methods) but not uniquely determined; solving the equation system with a different sequence of manipulations leads to other -- equivalent! -- expressions.

---

1. For a proof of Arden's Lemma, see here.

# Answer
> 33 votes
# Brzozowski algebraic method

This is the same method as the one described in Raphael's answer, but from a point of view of a systematic algorithm, and then, indeed, the algorithm. It turns out to be easy and natural to implement once you know where to begin. Also it may be easier by hand if drawing all the automata is impractical for some reason.

When writing an algorithm you have to remember that the equations must be always linear so that you have a good abstract representation of the equations, thing that you can forget when you are solving by hand.

### The idea of the algorithm

I won't describe how it works since it is well done in Raphael's answer which I suggest to read before. Instead, I focus on in which order you should solve the equations without doing too many extra computations or extra cases.

Starting from Arden's rule's ingenious solution $X=A^\*B$ to the language equation $X=AX∪B$ we can consider the automaton as a set of equations of the form:

$$X\_i = B\_i + A\_{i,1}X\_1 + … + A\_{i,n}X\_n$$

we can solve this by induction on $n$ by updating the arrays $A\_{i,j}$ and $B\_{i,j}$ accordingly. At the step $n$, we have:

$$X\_n = B\_n + A\_{n,1}X\_1 + … + A\_{n,n}X\_n$$

and Arden's rule gives us:

$$X\_n = A\_{n,n}^\* (B\_n + A\_{n,1}X\_1 + … + A\_{n,n-1}X\_{n-1})$$

and by setting $B'\_n = A\_{n,n}^\* B\_n$ and $A'\_{n,i}=A\_{n,n}^\*A\_{n,i}$ we get:

$$X\_n = B'\_n + A'\_{n,1}X\_1 + … + A'\_{n,n-1}X\_{n-1}$$

and we can then remove all needs of $X\_n$ in the system by setting, for $i,j\<n$:

$$B'\_i = B\_i + A\_{i,n}B'\_n$$ $$A'\_{i,j} = A\_{i,j} + A\_{i,n}A'\_{n,j}$$

When we have solved $X\_n$ when $n=1$, we obtain a equation like this:

$$X\_1 = B'\_1$$

with no $A'\_{1,i}$. Thus we got our regular expression.

### The algorithm

Thanks to this, we can build the algorithm. To have the same convention than in the induction above, we will say that the initial state is $q\_1$ and that the number of state is $m$. First, the initialization to fill $B$:

```
for i = 1 to m:
  if final(i):
    B[i] := ε
  else:
    B[i] := ∅

```

and $A$:

```
for i = 1 to m:
  for j = 1 to m:
    for a in Σ:
      if trans(i, a, j):
        A[i,j] := a
      else:
        A[i,j] := ∅

```

and then the solving:

```
for n = m decreasing to 1:
  B[n] := star(A[n,n]) . B[n]
  for j = 1 to n:
    A[n,j] := star(A[n,n]) . A[n,j];
  for i = 1 to n:
    B[i] += A[i,n] . B[n]
    for j = 1 to n:
      A[i,j] += A[i,n] . A[n,j]

```

the final expression is then:

```
e := B[1]

```

### Implementation

Even if it may seems a system of equations that seems too symbolic for an algorithm, this one is well-suited for an implementation. ~~Here is an implementation of this algorithm in Ocaml~~ (broken link). Note that apart from the function `brzozowski`, everything is to print or to use for Raphael's example. Note that there is a surprisingly efficient function of simplification of regular expressions `simple_re`.

# Answer
> 28 votes
# Transitive closure method

This method is easy to write in a form of an algorithm, but generates absurdly large regular expressions and is impractical if you do it by hand, mostly because this is too systematic. It is a good and simple solution for an algorithm though.

### The key idea

Let $R^k\_{i,j}$ represent the regular expression for the strings going from $q\_i$ to $q\_j$ using the states $\\{q\_1, …, q\_k\\}$. Let $n$ be the number of states of the automaton.

Suppose that you know already the regular expression $R\_{i,j}$ from $q\_i$ to $q\_j$ without the intermediate state $q\_k$ (except for extremities), for all $i,j$. Then you can guess how adding another state will affect the new regular expression $R'\_{i,j}$: it changes only if you have direct transitions to $q\_k$, and it can be expressed like that:

$$R'\_{i,j} = R\_{i,j} + R\_{i,k} . R\_{k,k}^\* . R\_{k,j}$$

($R$ is $R^{k-1}$ and $R'$ is $R^k$.)

### Example

We will use the same example as in Raphael's answer. At first, you can only use the direct transitions.

Here is the first step (note that a self loop with a label $a$ would have transformed the first $ε$ into $(ε+a)$.

$$R^0 = \begin{bmatrix} ε & a & b \\ b & ε & a \\ a & b & ε \end{bmatrix} $$

At the second step we can use $q\_0$ (which is renamed into $q\_1$ for us, because $R^0$ is already used for the purpose above). We will see how $R^1$ works.

From $q\_2$ to $q\_2$: $R^1\_{2,2} = R^0\_{2,2} + R^0\_{2,1} {R^0\_{1,1}}^\* R^0\_{1,2} = ε + b ε^\* a = ε + ba$.

Why is that? It is because going from $q\_2$ to $q\_2$ using only $q\_1$ as an intermediate state can be done by staying here ($ε$) or going to $q\_1$ ($a$), looping there ($ε^\*$) and coming back ($b$).

$$R^1 = \begin{bmatrix} ε & a & b \\ b & ε+ba & a+bb \\ a & b+aa & ε+ab \end{bmatrix} $$

You can compute like that $R^2$ and $R^3$, too, and $R^3\_{1,1}$ will give you the final expression because $1$ is both initial and final. Note that a lot of simplification of expressions have been done here. Otherwise the first $a$ of $R^0$ would be $(∅+a)$ and the first $a$ of $R^1$ would be $((∅+a)+ε(ε)^\*a)$.

### Algorithm

Initialization:

```
for i = 1 to n:
  for j = 1 to n:
    if i == j:
      R[i,j,0] := ε
    else:
      R[i,j,0] := ∅
    for a in Σ:
      if trans(i, a, j):
        R[i,j,0] := R[i,j,0] + a

```

Transitive closure:

```
for k = 1 to n:
  for i = 1 to n:
    for j = 1 to n:
      R[i,j,k] := R[i,j,k-1] + R[i,k,k-1] . star(R[k,k,k-1]) . R(k,j,k-1)

```

Then the final expression is (supposing $q\_s$ is the initial state):

```
e := ∅
for i = 1 to n:
  if final(i):
    e := e + R[s,i,n]

```

But you can imagine it generates ugly regular expressions. You can indeed expect things like $(∅)^\*+(a+(∅)^\*)(ε)^\*(a + ∅)$ that represents the same language as $aa$. Note that simplifying a regular expression is useful in practice.

# Answer
> 0 votes
Without going through the details of how, it might be instructive to see what the worst case looks like. That also contains the essence of the closed-form (or more accurately: "fail-safe") solution, but I digress...

A 4-state automaton with states $\\{A,B,C,D\\}$ and $A$ as the start state, with transitions can be written as a fixed point system in Kleene Algebra as follows: $$ A ≥ a + aa\ A + ab\ B + ac\ C + ad\ D,\\ B ≥ b + ba\ A + bb\ B + bc\ C + bd\ D,\\ C ≥ c + ca\ A + cb\ B + cc\ C + cd\ D,\\ D ≥ d + da\ A + db\ B + dc\ C + dd\ D, A, $$ where the final $A$ indicates the "start expression" and with linear coefficients $aa, ab, ⋯, dc, dd$ and affine coefficients $a, b, c, d$. The solution being sought is the least fixed point solution of this (a fixed-point) system, for $\\{A,B,C,D\\}$, applied to and substituted in the start expression $A$. And ... that solution (with sharing of subexpressions) is: $$ DD = dd^\*,\\ DC = dc,\quad CD = cd\ DD,\\ DB = db,\quad BD = bd\ DD,\\ DA = da,\quad AD = ad\ DD,\\ CC = (cc + CD\ DC)^\*,\\ CB = cb + CD\ DB,\quad BC = (bc + BD\ DC)\ CC,\\ CA = ca + CD\ DA,\quad AC = (ac + AD\ DC)\ CC,\\ BB = (bb + BC\ CB + BD\ DB)^\*,\\ BA = ba + BC\ CA + BD\ DA,\quad AB = (ab + AC\ CB + AD\ DB)\ BB,\\ AA = (aa + AB\ BA + AC\ CA + AD\ DA)^\*,\\ Yd = d,\\ Yc = c + CD\ Yd,\\ Yb = b + BC\ Yc + BD\ Yd,\\ Ya = a + AB\ Yb + AC\ Yc + AD\ Yd,\\ AA\ Ya $$

The sub-expressions are $AA, AB, ⋯, DC, DD$, as well as $Ya, Yb, Yc, Yd$. If you want to see what the whole thing looks like, without the factoring out of the shared sub-expressions, in-line substitute everything, from top on down.

With sharing, it's cubic in the worst case, in the number of states (and variables).

This is one of the demo files in RegEx, over on GitHub, up to change in notation. The program of interest in there is "dfa". If you run the program on it, you'll get the original 4×4 system, with the 16 linear coefficients and 4 affine coefficients.

Given the complexity of the file - even with the expression sharing - you can begin to see why I never (yet) got around to writing a reverse convertor. You need heuristics to optimize the algebraic systems and expressions ... which is actually a problem well-suited for AI. So, I've been sorta sitting on this (RegEx is from the mid 1990's, originally posted in the comp.compilers archives), waiting for AI to come around.

If you want to try your hand at AI, this is a good case to work on it with. One application (of many) is control-flow-structure synthesis, because that's what this really is, in disguise. The states are goto-labels, the embedded state-labels are "goto's", the stars are loops, the "+"'s are branches, either deterministic, if "guarded" or non-deterministic.

---
Tags: algorithms, formal-languages, finite-automata, regular-expressions, reference-question
---


# Question
Title: Are there languages L1 ⊆ L2 ⊆ L3 when L1 and L3 are NP-Complete languages and L2 ∈ P?
Are there languages L1 ⊆ L2 ⊆ L3 where L1 and L3 are NP-Complete languages and L2 ∈ P? Would this imply P=NP? Thanks

# Answer
Consider the following problems:

* $L\_1$:
    + Input: two graphs $G\_1$ and $G\_2$
    + Question: does $G\_1$ contain an hamiltonian path and is $G\_2$ complete?
* $L\_2$:
    + Input: two graphs $G\_1$ and $G\_2$
    + Question: is $G\_2$ complete?
* $L\_3$:
    + Input: two graphs $G\_1$ and $G\_2$
    + Question: does $G\_2$ contain an hamiltonian path?

Then $L\_1 \subseteq L\_2 \subseteq L\_3$. $L\_1$ and $L\_3$ are $\mathsf{NP}$-complete, but $L\_2$ is in $\mathsf{P}$.
> 24 votes

# Answer
That’s trivial. Take an NP-complete language $L$ with three symbols $a, b$, and $c$. Let $L’$ be the same language with $a, b, c$ replaced with $d, e, f$.

Now pick $L\_1 = L, L\_2 = (a \cup b \cup c)^\*$, and $L\_3 = L\_2 (\epsilon \cup L’)$.
> 20 votes

# Answer
The existing answers provide good examples of the requested condition, but I think there's some intuition missing.

What makes a language hard to decide is not what it contains, but the combination of what it contains and *does not* contain. That is, it is the "shape" of the language *boundary* that makes it hard.

With that in mind, a procedure for obtaining the condition $L1 \subseteq L2 \subseteq L3$ is:

* Pick any NP-complete $L1$, e.g., the set of all satisfiable boolean formulae.
* Form $L2$ by expanding $L1$ to a simple superset, e.g., the set of all boolean formulae (regardless of satisfiability).
* Form $L3$ by expanding $L2$, adding another difficult boundary. For example, elements of $L3$ can consist of an element of $L2$ optionally followed by an element of any NP-complete language (including $L1$ again).

Graphically, this looks like:

In this diagram, the smooth boundary of $L2$ is meant to suggest it is easy to recognize, while the more jagged boundaries of $L1$ and $L3$ suggest they are hard to recognize.
> 18 votes

# Answer
The constructions in the other answers are nice, but end up with somewhat artificial languages created by disjunction. There are more natural languages that also do the trick:

Let $L\_1$ be the set of trees that can be embedded in the 2D integer grid, such that the vertices are placed on distinct grid points and the edges are placed on grid edges. (This is an NP-complete problem, see this answer ).

Let $L\_2$ be the set of all trees (clearly in P), and let $L\_3$ be the set of $3$-colorable graphs (well-known to be NP-complete).

$L\_1\subseteq L\_2$ should be clear, and $L\_2\subseteq L\_3$ follows from the fact that all trees are $2$-colorable.
> 9 votes

---
Tags: complexity-theory, np-complete, p-vs-np
---


# Question
Title: Does Either...Or means Exclusive Or or Inclusive Or?
Let's take a compound propositions

Either it is below freezing or it is snowing.

Now if,
$p$: it is below freezing
$q$: it is snowing

Question Link: https://gateoverflow.in/42720/kenneth-rosen-edition-6th-exercise-1-1-question-7-page-no-17

Will it be $p \vee q$ or $p \oplus q$? There are some instances where semantics are required. For example

Either you are ill or appearing for exam. In this both cases can't be true, because if you are ill you can't appear for example and you must be in one state.

References

# Answer
> 10 votes
Don't try to force formal definitions over common english language.

"Either… or" means whatever you want it to mean. There is no convention. Just be precise when you want a formal definition.

Also what is the problem with the answers given in the post you linked?

# Answer
> 4 votes
Natural language is indeed ambiguous and depends a lot on semantics and specific context \[ref\].

In English, Either/Or usually means Exclusive Or because we tend to use in the situation where two options are presented and exactly one should be True (let's say selected) for entire statement to be True.

But in mathematics, however, Either/Or includes intersection case as well i.e inclusive or. This is because most of the statements in maths work out even when both of the statements are individually True.

But again, when you are dealing with natural languages in the logic, make sure to consider the context and how two statements would interact each other.

For example, if you are ill then you won't appear for example and if you are appearing for exam, then you aren't ill. Here, in this case, exclusive or ($\oplus$) would work better.

Here is the question related to ambiguity between inclusive and exclusive or, which is solved by thinking rationally and in context with how we will deal the situation in real world. https://gateoverflow.in/42729/kenneth-rosen-edition-6th-exercise-1-1-question-15-page-no-18

Also Wikipedia Article says,

> Some **informal ways** of describing XOR are "one or the other but not both", "**either one or the other**", and "A or B, but not A and B".

References

# Answer
> 0 votes
In English, no distinction is made between inclusive and exclusive OR.

That is, there is no word or specific idiom that makes these distinctions.

The purpose of the word "or" in English is not as a logical operator, but to connect a series of alternatives together in a sentence.

When the system of logical operators was invented in the 19th century by George Boole, he simply used existing English words to describe the operators in his system. But these terms take on a much more specific definition in his system, than the definition they have in ordinary English.

In ordinary English, it is often possible to resolve by context or common sense, whether it is possible for multiple alternatives to occur jointly and (if so) how the statement should apply in such a case. For example, "wanted dead or alive" (exclusive), or "come hell or high water" (inclusive).

But it's a mistake to think English speakers are constantly performing this resolution - often the distinction is simply not an important element of what is being said.

When using somewhat technical language, as in law, you might find devices like "either A, or B, or both" and "either A or B, but not both".

So it's possible to use English to express exactly the same meaning as the logical operators. But it takes more words and more complicated sentences to do so, and it is done by explicitly addressing the joint cases and stating whether or not they are included.

---
Tags: discrete-mathematics, propositional-logic
---


# Question
Title: What is the regular language for L = {w | w has even length, and starts and ends with the same symbol}?
I **originally** thought it was 0(01)\*(01)*0 U 1(01)*(01)1 where:

* two versions: one that starts and ends with 0, the other that starts and ends with 1
* connected by plus, which does not mean union of both but either or
* repeat of (01)\* to make the string even. For example, for 0010 you would

1. start with 0
2. pick 0 from the first 01s
3. pick 0 from the second 01s
4. end with 0

**UPDATE: I think this is a more clear and accurate answer: L=(00+11+01+10)∗(00+11)**

* 00 + 11 +01 + 10: All possible options for an even length
* 00+ 11: 00 will match either 00 or 01 and 11 will match 11 or 10

# Answer
Your regex is incorrect since $0011 \in (00+11+01+10)^∗(00+11)$ but $0011 \notin L$. Assuming we only consider words over $\\{0, 1\\}$, the language is recognised by

$$1\big((0 + 1)(0 + 1)\big)^\*1 + 0\big((0 + 1)(0 + 1)\big)^\*0$$

and more generally for alphabet $\Sigma$

$$\bigcup\_{c \in \Sigma} c(\Sigma\Sigma)^\*c.$$
> 1 votes

---
Tags: computability, regular-languages, finite-automata, context-free, regular-expressions
---


# Question
Title: Draw a finite automation for {w ∈ Σ ∗ | w does not contain the substring 10}
So I am trying to draw a finite automation that has no limits on the length, but cannot have the substring of `10`

I created a DFA that could satisfy this requirement, but am uncertain about the accept states having `01` because you can use the loop to create something like (i.e. 10**10**10).

But I can't add additional transitions from stage a like the picture below because you add too many zeros with the loop to get 00**10**000

What would you suggest?

# Answer
> 2 votes
Is it required that your finite automaton accepts empty strings? The only requirement appears to be the non-occurrence of $10$. If so, $a$ must be an accepting state.

The idea is that whenever your finite automaton accepts a $1$, it cannot accept any more $0$s. The following DFA is my suggestion.

*Edit: I forgot to specify the initial state.*

---
Tags: computability, regular-languages, finite-automata, regular-expressions, computation-models
---


# Question
Title: Subset Relations Between CFGs and Their Languages
Is it possible for there to exist two context-free grammars where the set of rules of the first is a proper subset of the set of rules of the second, yet the language generated by the second grammar is a proper subset of the language generated by the first?

# Answer
> 4 votes
Let $G$ and $H$ be your two context-free grammars, respectively. If the set of all rules in $G$ is a subset of the set of all rules in $H$, then all derivations possible in $G$ are also possible in $H$. In other words, the language accepted by $G$ is also accepted by $H$.

Therefore, it is impossible for the language generated by $H$ to be a proper subset of the language generated by $G$.

# Answer
> 1 votes
No. Adding rules can only add options for generating strings; all preexisting derivations are still possible.

# Answer
> 1 votes
This might be considered cheating, but I think it's possible to define such grammars if the set of terminals/non-terminals isn't required to be the same for both of them.

Using wikipedias formulation, define the CFGs $G\_1 = (V\_1, \Sigma\_1, R\_1, S)$ and $G\_2 = (V\_2, \Sigma\_2, R\_2, S)$ such that

* $V\_1 = \\{S\\}$, $V\_2 = \\{S, A\\}$
* $\Sigma\_1 = \\{A\\}$, $\Sigma\_2 = \emptyset$
* $R\_1 = \\{S \to A\\} \subset R\_2 = \\{S \to A, A \to A\\}$

then $L(G\_1) = \\{A\\} \supset \emptyset = L(G\_2)$.

---
Tags: formal-languages, automata, finite-automata, context-free
---


# Question
Title: Are float pseudo-random number generators always implemented using integer generators underneath
In C it's well known to use simple routine for turning integer rng into float rng. Something like that

```
float frand( float min, float max ) {
    float scale = rand()/(float)RAND_MAX; // [0, 1.0]
    return min + scale * (max - min); // [min, max]
}

```

So the core random number generation is happening inside integer rand() function which uses some sort of linear congruential generator. Is it always like that for floats?

Is there a better, more performant way if you specifically interested in float pseudo-random number generation in a given range (range is known on compile time)? This relying on integer arithmetic and float conversions seem wasteful to me, but on the other hand I have no idea how to implement it without it.

# Answer
I am not aware of any direct-to-float PRNGs. The primary issue is that it is very difficult to get high quality random numbers using floating point operations. PRNGs typically leverage well understood integer behaviors to generate random-esque sequences with good properties.

Practically speaking, the subtractions and divisions are not all that wasteful. Any PRNG you build using floats will be substantially more expensive.

The one case I can think of where you'd really want to use floats is if you had an extremely skewed distribution which is often very close to 0. In this case, the extra precision of the float for small numbers would help. Otherwise, the exponent part of the float doesn't really help you. All you end up with is an integer PRNG in the mantissa part of the float, but with fewer bits than the higher quality and faster integer PRNGs would generate.
> 2 votes

# Answer
Yes. When IBM created its POWER processors which may have been the first ones with a fused multiply-add operation, they managed to implement the linear-congruential method using floating point, generating large numbers of random numbers in parallel at a rate of one per cycle.
> 1 votes

# Answer
As other answers have pointed out, most PRNGs using floating-point computation and floating-point storage for the PRNG state simply use the floating-point unit to perform integer arithmetic, using the significand part of IEEE-754 floating-point types to store the integers. One (historical) motivation for this is that hardware may support wider floating-point types than integer types.

One PRNG of this kind that has good quality and is still in wide-spread use today is MRG32k3a, which uses a sextuple of `double` variables for state. It first appeared in the literature in the late 1990s:

P. L'Ecuyer, "Good parameters and implementations for combined multiple recursive random number generators." *Operations Research*, Vol. 47, No. 1, Jan.-Feb. 1999, pp. 159-164

```
#define norm 2.328306549295728e-10
#define m1   4294967087.0
#define m2   4294944443.0
#define a12     1403580.0
#define a13n     810728.0
#define a21      527612.0
#define a23n    1370589.0

double  s10, s11, s12, s20, s21, s22;

double MRG32k3a ()
   {
   long k;
   double p1, p2;

   /* Component 1 */
   p1 = a12 * s11 - a13n * s10;
   k = p1 / m1;   p1 -= k * m1;   if (p1 < 0.0) p1 += m1;
   s10 = s11;   s11 = s12;   s12 = p1;
   /* Component 2 */
   p2 = a21 * s22 - a23n * s20;
   k = p2 / m2;   p2 -= k * m2;   if (p2 < 0.0) p2 += m2;
   s20 = s21;   s21 = s22;   s22 = p2;
   /* Combination */
   if (p1 <= p2) return ((p1 - p2 + m1) * norm);
   else return ((p1 - p2) * norm);
   }

```

The use of `long k` was motivated by the absence of a way to round a floating-point-number to an integer using round-towards-0, i.e. truncation. However, since ISO-C99 there is the `trunc()` function which can be used for this purpose and maps to a single instruction on many modern processor architectures. This results in a pure floating-point computation, and modern compilers like Clang are able to use 2-way SIMD vectorization to parallelize the computation of `p1` and `p2`.

```
double MRG32k3a (void)
{
    double k, p1, p2;

    /* Component 1 */
    p1 = a12 * s11 - a13n * s10;
    k = trunc (p1 / m1);  p1 -= k * m1;  if (p1 < 0.0) p1 += m1;
    s10 = s11;   s11 = s12;   s12 = p1;
    /* Component 2 */
    p2 = a21 * s22 - a23n * s20;
    k = trunc (p2 / m2);  p2 -= k * m2;  if (p2 < 0.0) p2 += m2;
    s20 = s21;   s21 = s22;   s22 = p2;
    /* Combination */
    if (p1 <= p2) return ((p1 - p2 + m1) * norm);
    else return ((p1 - p2) * norm);
}

```

Floating-point division is often fast on the latest (post 2020) processor implementations. Given that the divisors here are constant, it may nonetheless be worthwhile to try and replace the division by constant with FMA-based computation utilizing a pre-computed reciprocal. FMA is a fused multiply-add operation that computes $a b +c$ that uses the *full* product $ab$ during the addition and applies a single rounding at the end. It was first introduced by IBM in the early 1990s:

Erdem Hokenek, Robert K. Montoye, and Peter W. Cook. "Second-generation RISC floating point with multiply-add fused." *IEEE Journal of Solid-State Circuits,* Vol. 25, No. 5, October 1990, pp. 1207-1213

At this point in time the major processor architectures all support FMA in hardware, and it is conveniently accessible via a standard function `fma()` in C, C++, and various other programming languages. Using FMA, we can create a bit-accurate replacement for division by constant for many integer constants:

```
/* compute quotient q=x/y for finite x, y; rcp_y = correctly rounded 1.0/y */
double qdiv (double x, double y, double rcp_y)
{
    double q;
    q = x * rcp_y;
    if (x != 0) q = fma (fma (-y, q, x), rcp_y, q);
    return q;
}

```

This results in the following implementation, which can likewise be SIMD vectorized by compilers like Clang:

```
#define rcp_m1   (1.0/m1)
#define rcp_m2   (1.0/m2)

double MRG32k3a (void)
{
    double k, p1, p2;

    /* Component 1 */
    p1 = a12 * s11 - a13n * s10;
    k = trunc (qdiv (p1, m1, rcp_m1));  p1 -= k * m1;  if (p1 < 0.0) p1 += m1;
    s10 = s11;   s11 = s12;   s12 = p1;
    /* Component 2 */
    p2 = a21 * s22 - a23n * s20;
    k = trunc (qdiv (p2, m2, rcp_m2));  p2 -= k * m2;  if (p2 < 0.0) p2 += m2;
    s20 = s21;   s21 = s22;   s22 = p2;
    /* Combination */
    if (p1 <= p2) return ((p1 - p2 + m1) * norm);
    else return ((p1 - p2) * norm);
}

```

It should be noted that MRG32k3a can be efficiently implemented via pure integer computation on modern 64-bit processors. Even on 32-bit processors that provide an integer multiplier that can deliver the most significant 32 bits of the full product of two 32-bit integers an integer-based implementation can be reasonably efficient.

---

Part of programmer folklore in the world of 3D graphics is the following PRNG that uses only `float` computation and a two-vector of `float` variables for state storage.

```
float rand(vec2 n) {
    return fract(sin(dot(n.xy ,vec2(12.9898,78.233))) * 43758.5453);
}

```

This generates random numbers in $(-1,1)$ via `fract()`, which extracts the fractional part of a `float`. With the simple application of the absolute value, this could be used to generate random numbers in $\[0, 1)$. For performance, this PRNG relies heavily on the availability of a blazingly fast `sin()` approximation, which is a standard feature of GPUs.

I have not used this PRNG and know nothing about its origin, design criteria, and properties. The small state and the non-linearity of the sine function *suggests* that it has a short period and provides a distribution that is not entirely uniform. Also, granularity of the generated numbers is limited as the significand of a `float` mapped to IEEE-754 `binary32` format comprises only 23 stored bits. There is a Q&A for this PRNG on Stackoverflow which may be useful for followup.
> 1 votes

# Answer
My very very first computer that came with BASIC built-in, had a random number generator that replaced the previous value x with the fractional part of (x + pi)^5.

It wasn’t very random. It had the interesting property that of two consecutive random numbers the second was larger with a probability of about 60% (or it was smaller. Can’t remember). The
> 1 votes

---
Tags: floating-point, performance, pseudo-random-generators, c, random-number-generator
---


title: Minimize Cost to Split Integer Arrays

text:
# Question
Title: Minimize Cost to Split Integer Arrays
There is a sorted integer array $a\_1 \dots a\_n$ and an integer $1 \leq k \leq n$, we need to figure out the minimized total cost to group this integer array into $k$ groups. The cost per group is mean($a\_i \dots a\_j$) for a group from $i$ to $j$. Give an algorithm in $O(nk)$. Group here means partitioning and there's no requirement for what element constraints inside each group.

I am currently trying to do dynamic programming for this but I am rather very lost on how to achieve $O(nk)$ time complexity. I have tried sorting the array and then pre-compute the segment sum but I still can't get the complexity down.

# Answer
> 0 votes
If the group elements do not need to be consecutive, then here is a simple approach: Take the first element and place it in group 1; the second in group 2; and so on for the first $k$ elements. Then $(k+1)$-th element is placed in group 1, so on and so forth. In general $i$-th element in placed into group $((i-1) ~\text{mod}~ k + 1)$-th group. Each group would roughly cost about the overall mean of all elements.

---
Tags: dynamic-programming
---


# Question
Title: Does the Subset Product Problem remain NP-complete if repetition in S is not allowed?
Just curioius, I wanted to know when $S$ ={set of divisors of N} and we're given $N$ a target product. Our goal is to decide if a combination in $S$ has product equal to N.

Does the problem remain NP-complete in this restriction? Assuming only positive integers?

# Answer
> 1 votes
Let $S = \\{s\_1,\dots,s\_m\\}$ (this is a multiset!), without loss of generality not containing any $1$s (if it does, remove them), and let $p\_1,\dots,p\_m$ be distinct primes which don't divide $N$ or any number in $S$. Let $$ S' = \\{ p\_i, s\_i p\_i : i = 1, \dots, m \\}, \quad N' = p\_1 \cdots p\_m N. $$

Suppose that there is a subset $T \subseteq S$ whose product equals $N$. Then the product of the following subset equals $N'$: $$ \\{ s\_i p\_i : s\_i \in T \\} \cup \\{ p\_i : s\_i \notin T \\}. $$

Conversely, suppose that there is a subset $T' \subseteq S'$ whose product equals $N'$. By construction, $T'$ must contain exactly one of $\\{p\_i, s\_ip\_i\\}$ for every $i$. If we let $T = \\{ s\_i : s\_i p\_i \in T' \\}$, then the product of $T$ is $N$.

---

If we take the first $m$ primes larger than $\max(s\_1,\dots,s\_m,N)$ then the new instance has size polynomial in the size of the original instance. But it is not clear that we can find these primes efficiently. Therefore we need to slightly modify the construction.

Let $q\_1,\dots,q\_m$ be the first $m$ primes. We can find these in time $\mathit{poly}(m)$, which is polynomial in the size of the input. Now let $p\_i = q\_i^{e\_i}$, where $e\_i$ is larger than the total exponent of $q\_i$ in all numbers in $S$ (we can find $e\_i$ efficiently using GCD). The size of each $p\_i$ is at most roughly the sum of sizes of the $s\_j$, so this reduction can be implemented in polynomial time. Details left to you.

---
Tags: np-complete, decision-problem, subset-product
---


# Question
Title: A more concise Finite Automata for 10 substring?
I am learning about finite automata and trying to create a machine that matches

**`{w ∈ Σ∗| w does not contain the substring 10}`**

I created a DFA where it either starts with `1` or `0`. I know it's not the most concise FA, but is it accurate?

# Answer
> 4 votes
Your automat**on** (automata is the plural word) is wrong:

* as @Knogger stated, there is no initial state
* finite automata (unless generalized) can only have one-letter transitions, so transitions $01$ are not allowed
* even if $01$ transitions are allowed, this would create $10$ as substring, since $0101$ contains $10$.

You should try again, noting the fact that a word $w\in \\{0,1\\}^\*$ does not contain $10$ as a substring if and only if $w = 0^p1^q$, for some $p, q\geqslant 0$.

# Answer
> 0 votes
This one is a classic textbook problem. You can build your required DFA as follows:

step 1: build a complete DFA $M$ that accepts all strings containing `10` as a substring

step 2: just swap the status of final/non-final states in this DFA to get another DFA $M'$

step 3: argue that $M'$ has to be your required one

Read more about DFA complementation here.

---
Tags: regular-languages, finite-automata, regular-expressions, computation-models, substrings
---


# Question
Title: NP hardness of adaption of the graph bandwidth problem
Is the following adaptation of the graph bandwidth problem NP hard? If so, which problem could a reduction use?

Given: Graph $G = (V , E ), L:E\to \mathbb N$.

Question: Is there a $f : V \to \mathbb Z$ where for each $e = \\{u, v \\} \in E$, $|f (u) - f (v )| = L(e)$?

# Answer
This problem can be trivially solved for a forest. However it is $\mathrm{NP}$-complete even for a single cycle. Let's reduce the partition problem to this one.

Given a multiset $S$ of positive integers we build a cycle graph $G \cong C\_{|S|}$ on $|S|$ vertices and place elements of $S$ one per edge as the function $L$. Now the function $f$ exists if and only if there is a partition of the multiset $S$ into two subsets $S\_1$ and $S\_2$ such that sum of elements in both subsets is the same.

* If such partition exists, then starting with an arbitrary vertex $v$ of the graph $G$ we firstly let $f(v) = 0$ and then moving around the cycle along edge $e = \\{\\,u, w\\,\\}$ from the vertex $u$ to the vertex $w$ we let $f(w) = f(u) + L(e)$ if $L(e)$ came to $S\_1$ or $f(w) = f(u) - L(e)$ otherwise. (Note that for equal elements distributed between $S\_1$ and $S\_2$ corresponding number of edges should take $+$ and $-$ signs.) Going along the last edge to the vertex $v$ we don't have any contradiction, because each element of $S\_1$ was added and each element of $S\_2$ was subtracted exactly once.
* If such a function $f$ exists, then starting from an arbitrary vertex $v$ and moving around the cycle along the edge $e = \\{\\,u, w\\,\\}$ from the vertex $u$ to the vertex $w$ we place element $L(e)$ into $S\_1$ if $f(w) = f(u) + L(e)$ or into $S\_2$ otherwise. Since after passing each edge once we added or subtracted $L(e)$ for each $e$ exactly once and starting from $f(v)$ we finally get $f(v)$ again, we conclude that the sum of elements in subsets $S\_1$ and $S\_2$ is the same.

Since the reduction is polynomial in space and time, and partition problem is $\mathrm{NP}$-complete, then the given problem is $\mathrm{NP}$-hard. And since it belongs to the class $\mathrm{NP}$ we conclude that it is $\mathrm{NP}$-complete.
> 3 votes

---
Tags: graphs, np-hard
---


title: DFA to regular expression conversion

text:
# Question
Title: DFA to regular expression conversion
I was looking at the question How to convert finite automata to regular expressions? to convert DFA to regex.

The question, I was trying to solve is:

I have got the following equations:

$Q\_0=aQ\_0 \cup bQ\_1 \cup \epsilon$

$Q\_1=aQ\_1 \cup bQ\_1 \cup \epsilon$

When solved, we will get $Q\_0=a^\*b(a \cup b)^\* \cup\ \epsilon$

But my doubt is that, in the DFA starting state is also the final state so, even if we dont give any $b$, it will be accepted, if we give some $a$. But in the regex we have $b$, instead of $b^\*$. Why is it so? Is it because,we have that regex $\cup$ $\epsilon$ ?

# Answer
I'll be using the solution to $Q = \alpha Q \cup \beta$ given by $Q = \alpha^\* \beta$, essentially as you would go solving a system of linear equations by hand:

$$ \begin{align\*} Q\_0 &= a Q\_0 \cup b Q\_1 \cup \epsilon \\ Q\_1 &= (a \cup b) Q\_1 \cup \epsilon \end{align\*} $$ From the first equation you have $Q\_0 = a^\* (b Q\_1 \cup \epsilon)$, the second one reduces to $Q\_1 = (a \cup b)^\* \epsilon = (a \cup b)^\*$. Replacing $Q\_1$ in $Q\_0$ gives: $$ Q\_0 = a^\* (b (a \cup b)^\* \cup \epsilon) = a^\* b (a \cup b)^\* \cup a^\* $$
> 2 votes

# Answer
Every state and every item from the set $\\{a,b\\}$ has a transition to another state, and every state is an accepting state. Therefore, all states are equivalent and the regular expression (in your notation) is just $(a ∪ b)^\*$.

The automaton in question is equivalent to the following Kleene Algebraic fixed-point system of inequations: $$A ≥ a A + b B + 1,\quad B ≥ a B + b B + 1,\quad A,$$ with the last item, $A$, indicating the starting expression. The least fixed point solution for $(A,B)$, substituted into the starting expression $A$ yields the regular expression in question.

As you noted, you can factor $B$: $$A ≥ a A + b B + 1,\quad B ≥ (a + b) B + 1,\quad A.$$ You can solve for $B$. In general, the least fixed point solution to $x ≥ u x + v$, in $x$, which is denoted $μx·(ux + v)$, in Kleene algebra, is just $x = u^\* v$. Thus, the reduction: $$A ≥ a A + b B + 1,\quad B ≥ (a + b)^\*,\quad A.$$ Upon substitution for $B$ and elimination, this reduces to: $$A ≥ a A + b (a + b)^\* + 1,\quad A.$$ In a similar way, we find the solution for $A$: $$A ≥ a^\* (b (a + b)^\* + 1),\quad A,$$ and, upon substitution and elimination of $A$: $$a^\* (b (a + b)^\* + 1).$$

(Your mistake, as already noted in another reply, is that you had the equivalent of $a^\* b (a + b)^\* + 1$, instead of $a^\* (b (a + b)^\* + 1)$.)

Kleene-algebraic identities can be used, particularly $(u + v)^\* = u^\* (v u^\*)^\*$ and $u^\* = u u^\* + 1$, reducing this to $$\begin{align} a^\* (b (a + b)^\* + 1) &= a^\* (b a^\* (b a^\*)^\* + 1)\\ &= a^\* (b a^\*)^\*\\ &= (a + b)^\*, \end{align}$$ or, in your notation $(a ∪ b)^\*$.

The axioms cited in the linked article are sufficient to prove any and all Kleene-algebraic identities. They are equivalent to the following set of properties: $$ (x + y) + z = x + (y + z),\quad x + 0 = x = 0 + x,\quad x + y = y + x,\quad x + x = x,\\ (xy)z = x(yz),\quad x 1 = x = 1 x,\quad p 0 q = 0,\quad p (x + y) q = p x q + p y q,\\ 0^\* = 1,\quad μx·(a + bx + xc) = b^\* a c^\*. $$ (*Edit*: I put in $0^\* = 1$, too, otherwise you have to split the least-fixed-point equation into $μx·(a + bx) = b^\* a$ and $μx·(a + xc) = a c^\*$.)

These axiomatizations come from 1994. Many texts - even now - are obsolete, still using frameworks from the 1960's and not including these more recent developments, which themselves are now over a generation past.

If you strengthen it by replacing the last axiom with $$p (μx·f(x)) q = \sup\_{n≥0} p f^n(0) q,$$ where $$f^0(x) = x,\quad f^1(x) = f(x),\quad f^2(x) = f(f(x)),\quad f^3(x) = f(f(f(x))),\quad ⋯,$$ where $f(x)$ denotes an arbitrary Kleene-polynomial in $x$, then you get an axiomatization for fixed-point-closed Kleene algebras that is complete with respect to the algebra of context-free subsets; i.e. an algebra for "context-free" expressions: μ-continuous Chomsky Algebras.

This comes from the mid-2010's (2014, I believe) and was in 2018 proven equivalent to another axiomatization that arose in 2008 (the algebra of C-dioids), which used in place of the last property that (a) every context-free subset $U$ has a least upper bound $\sup U$, and (b) $\sup \\{p\\}U\\{q\\} = p (\sup U) q$, for context-free subsets $U$.
> 0 votes

---
Tags: regular-languages, automata, finite-automata, regular-expressions
---


# Question
Title: Is this language in R, RE or coRE? or neither $ L=\{\langle M\rangle\mid M$ is a TM that accepts all even length words$\}$
in my quest to understand computability theory, I came across this question, and it made me think that I don't fully understand the theory

is this language in R RE or coRE? or neither $$ L=\\{ \<M\>|M \ Is \ a \ TM \ that \ accepts \ all \ even \ length \ words \\} $$

my attempt:

in terms of where intuition this language is in coRE because we can only reject input that is not in the language, which is a TM that accepts an odd lengh word. but i am not sure how to make the reduction from $$ \overline{HP} $$

# Answer
> 2 votes
First, your intuition about this language being co-semi-decidable is incorrect, since whether some word of odd length is accepted makes no difference on whether the Turing machine belongs to the language. To prove that a Turing machine is not in $L$, you need to show that it does *not* accept some *even* length word. There isn't an obvious semi-algorithm to do that: you can always run it and if it rejects, you will see it, but it might not terminate, and you will never be sure.

In fact, this language is neither semi-decidable, nor co-semi-decidable (and in particular not decidable).

Perhaps the easiest to show is that $L$ is not decidable. This follows immediately from a famous result, Rice's theorem. (If you want an explicit reduction from the halting problem, I encourage you to look at the proof of Rice's theorem.)

To show that $L$ is not semi-decidable, you can apply a less famous but also very useful sibling of Rice's theorem, namely the Rice-Shapiro theorem. See the Wikipedia page for a precise statement. A machine that accepts all words is in $L$, and by the Rice-Shapiro theorem, this entails that some machine which only terminates on a finite number of words is in $L$, a contradiction since there are infinitely many words of even length.

The proof that $L$ is not co-semi-decidable can also be done with the same theorem. A machine that always loops is not in $L$, and terminates on a finite number of words (namely zero), therefore *any* machine must not be in $L$, because all machines "extend" this looping machine in terms of behavior. This is absurd, because some machines are in $L$.

---
Tags: formal-languages, computability
---


# Question
Title: DFS to assign guards to nodes in a tree structure
Consider a uniquely designed museum where rooms are arranged in a tree structure. Each room can have up to two child rooms connected by a path. The task is to develop an algorithm to place a minimum number of security guards so that the entire museum is guarded. A guard placed in a room can guard that room, its parent room, and its direct child rooms. It is a standard binary tree, and using DFS for bottom-up traversal is expected. Worst case time and space complexity is to be expressed.

I thought traversing as post order and looking whether a node has a parent and having at least one child to assign a guard to it, but it also adds extra guards. Should we also check if a node is guarded etc or is there a better way without it since we traverse bottom to up?

# Answer
This looks like the dominating set problem, but in a tree.

If the tree has two nodes or more, note that it is never interesting to put a guard in a leaf, because putting the guard in its parent will cover more rooms. Conversely, since you need a guard to check the leaf room, you need to put a guard either in the leaf or in its parent.

This gives the idea of an algorithm: using a DFS traversal in post-order, for each node, if it is uncovered, put a guard in its parent. The idea is that after putting a guard in the parent of a leaf (as stated above) and deleting covered nodes, this creates new leaves and you can apply it recursively (note that this can disconnect the tree, but it is not a problem).
> 1 votes

---
Tags: algorithms, graphs, graph-traversal, depth-first-search
---


title: Measuring Cache Access Time

text:
# Question
Title: Measuring Cache Access Time
I want to make a simple C program in order to measure L1, L2 and L3 latencies of my CPU. I know some info about them:

```
Caches (sum of all):
  L1d:                   128 KiB (4 instances)
  L1i:                   256 KiB (4 instances)
  L2:                    2 MiB (4 instances)
  L3:                    4 MiB (1 instance)

```

I tried with the following code, but the output has no sense for me.

```
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

#define L1_BLOCKS 512
#define L2_BLOCKS 8196
#define L3_BLOCKS 65536
#define BLOCK_SIZE 64

/*
  Calculate AVG time to access from arr[from_block]
  to arr[from_block + test_size].
*/
double mem_test(uint64_t *arr, int from_block, int test_size) {
    unsigned char tmp;

    double elapsed = 0;
    clock_t start_time, end_time;

    start_time = clock();

    for (int block_idx = from_block; block_idx < from_block + test_size; block_idx++) {
        tmp += arr[block_idx];
    }

    end_time = clock();
    elapsed = (double) (end_time - start_time) / test_size;

    return elapsed;
}

int main() {
    uint64_t *arr = malloc(BLOCK_SIZE * L3_BLOCKS);
    unsigned char tmp;

    // Test main memory
    // At this moment cache L1, L2, L3 should not contain
    // any of the arr blocks.
    double main_latency = mem_test(arr, 0, L1_BLOCKS);
    printf("MAIN MEMORY: %.20f\n", main_latency);

    // Load memory in cache.
    for (int idx = L3_BLOCKS; idx > 0; --idx) {
        arr[idx] = 1;
        tmp = arr[idx];
    }
    // At this moment, L1 should contiain all blocks from
    // arr[0] to arr[L1_BLOCKS], L2 all blocks from arr[0]
    // to arr[L2_BLOCKS], and L3 all blocks from arr[0] to
    // arr[L3_BLOCKS].

    double l1_latency = mem_test(arr, 0, L1_BLOCKS);
    printf("L1: %.20f\n", l1_latency);

    double l2_latency = mem_test(arr, L1_BLOCKS, L1_BLOCKS);
    printf("L2: %.20f\n", l2_latency);

    double l3_latency = mem_test(arr, L2_BLOCKS, L1_BLOCKS);
    printf("L3: %.20f\n", l3_latency);

    free(arr);

    return 0;
}

```

```
MAIN MEMORY: 0.00585937500000000000
L1: 0.00585937500000000000
L2: 0.00390625000000000000
L3: 0.00390625000000000000

```

# Answer
Since tmp is never used, an optimising compiler may not calculate it at all - you would get a result of 0. That needs fixing. Making tmp static and printing it at the very end is enough.

Clock() returns time not in seconds, but units of CLOCKS\_PER\_SEC. Divide the elapsed time by CLOCKS\_PER\_SEC.

When you try to get the main memory latency, you have no idea whether the memory is in some cache or not. That number is meaningless.

To measure it properly: read the data once. Ignore the time. Then read the data repeatedly for one second and use that for your result.

Don’t just check the cache sizes. You want to know the curve when your use approaches or slightly exceeds the cache size. I’d start with 100 bytes then increase by 1% repeatedly up to a very large size. You want to know if your caches have any positive effect for large sizes.

Your test doesn’t test latency, it tests bandwidth. Very different. And you have so many instructions per byte that even with main memory, the instructions may be the limit, not the memory bandwidth.

Read bytes n bytes apart, for n = 1, 2, 4, 8, 16, 32, 64, 128 and 256. Check the results.
> 0 votes

---
Tags: computer-architecture, cpu-cache, memory-access
---


# Question
Title: What is the value range for absolute value formulation of binary variable
According to this link binary variables - absolute values the formula of some binary variables like absolute value is :

y = | x1 - x2| for two variables x1, x2 with 0 ≤ xi ≤ U

Introduce binary variables d1, d2 to mean

d1 : 1 if x1 - x2 is the positive value d2 : 1 if x2 - x1 is the positive value

MIP formulation

0 ≤ xi ≤ U \[1.i\]

**0 ≤ y - (x1-x2) ≤ 2 · U · d2 \[2\]**

**0 ≤ y - (x2-x1) ≤ 2 · U · d1 \[3\]**

d1 + d2 = 1 \[4\]

Notice the bolded numbers, what do these 2s represent? Do they represent the value range? Aren't the value range is only from 0 to 1?

Sorry, I'm totally new to this.

# Answer
> 0 votes
That's just basic inequalities, there is no trick.

* if $d\_1 = 1$, then $d\_2 = 0$, and $y = x\_1 - x\_2$. That means that: $$y - (x\_1 - x\_2) = 0 \leqslant 2 \times U \times d\_2 = 0$$
* if $d\_1 = 0$, then $d\_2 = 0$, and $y = x\_2 - x\_1$. That means that: $$y - (x\_1 - x\_2) = 2x\_2 - 2x\_1 \leqslant 2\times U - 2\times 0 = 2\times U \times d\_2$$

Same thing for the other inequality.

---
Tags: binary
---


# Question
Title: What is the name of the theory that says that Turing equivalence is universal, and Turing machines are maximally computationally powerful?
In the Chomsky hierarchy, level 0 grammars include all languages that can be recognized by a Turing machine. There is no level -1 (which would represent the class of languages that cannot be recognized by a Turing machine, but can be recognized by something more computationally powerful than a Turing machine). Turing machines are universal, in the sense that all Turing-equivalent machines have the same fundamental computational capability (ignoring time and space limits), and as far as we know, it is not possible to build something that is fundamentally more computationally powerful than a Turing machine.

What is the name for this theory? How is it proved that there cannot exist a computer more computationally powerful than a Turing machine?

# Answer
The term I was looking for, that collects research on my original question as to whether there was a proof that Turing completeness is the most powerful model of computing, is hypercomputation:

https://en.wikipedia.org/wiki/Hypercomputation

It seems that it is controversial as to whether hypercomputation models can practically be built (there is no proof yet as to whether hypercomputation is possible or not).

(Thanks to mhum for pointing me in the right direction so that I could find this answer...)
> 1 votes

# Answer
I believe that the questioner is inquiring about the Church-Turing thesis.
> 4 votes

# Answer
In my recent question, I asked why do we consider Turing Machines as a limit of computation, you can check it here, good answer was provided for it: Is the Turing machine the only framework to analyse limits of computation?
> 1 votes

---
Tags: turing-machines, computability, formal-grammars, turing-completeness, chomsky-hierarchy
---


# Question
Title: How to write a turing machine program for any given problem?
I'm learning about Turing machine program,i want to know how we write a Turing machine program about any given problem, like a string is accepted by Turing machine, program (for a Single Tape Turing Machine) that checks if a binary number on the tape is an even number etc

# Answer
> 2 votes
Think about an algorithm to solve the problem.

Then write a Turing-machine that implements this algorithm.

For instance, checking if a binary number is even can be done by examining its rightmost bit.

That gives you an algorithm: First you look for the rightmost bit, then when you have found it, you check whether it is 0 or 1.

So you can make a Turing-machine with four states: "have not found the right-most bit yet", "have found the right-most bit", "the right-most bit is 0", "the right-most bit is 1". Then write the transitions between these states.

# Answer
> 0 votes
Let me narrow down your question: is it always possible to write a Turing Machine that solves any **mathematical** problem? We can make this more precise by reviewing some terms:

* Let $\Sigma = \\{0, 1\\}.$ Denote $\Sigma^\*$ as the set of binary strings (including the empty string). A **language** $L$ is a subset of $\Sigma^\*.$ (You can use any finite set for $\Sigma$. The choice is arbitrary, but many texts I’ve read frequently use it).
* Let $M$ be a Turing Machine, and let $L(M)$ be the set of all strings accepted by $M.$
    + $M$ **recognizes** a language $L$ if $L = L(M).$
    + $M$ **decides** $L$ if it recognizes $L$ and halts on all inputs.
* A language is **Turing-recognizable** if it is recognized by a Turing Machine, and **Turing-decidable** if it is decided by a Turing Machine. For readability, I will drop the prefix.

Now we can rephrase your question: is every language decidable?

The answer is **no.** One famous example is Alan Turing’s Halting Problem: determine whether a Turing Machine halts or not on a given input. You can find more details in his paper, where he first introduced Turing Machines. (If you are interested in why he wrote this paper, I would suggest looking into the Entscheidungsproblem, a major mathematical issue from the 20th century).

Note that you can recognize the Halting Problem. Roughly speaking, you can write a Turing Machine $M’$ that monitors $M$: if $M$ accepts or rejects an input, so will $M’.$ But if $M$ never halts on some input (goes into an infinite loop), so will $M’.$ However, there are languages that can’t be recognized by a Turing Machine. For example, you can make an unrecognizable language through diagonalization (see these slides from Clemson University).

We can strengthen this result as \[Rice’s Theorem\]\[4\]: every non-trivial property of a Turing machine is undecidable. A property is trivial if it is true of all Turing machines or none of them. In particular, not all Turing machines are recognizers for some fixed language $L,$ so we cannot decide this, in general.

With all of that said, there are many instances where we *can* write down a Turing Machine. These include some important computational classes:

* Any regular language/regex. This includes Stef’s example.
* Any context free grammar. This includes parsing *most* programming languages.
* Any polynomial time running algorithm.
* And so on.

In your original question, I suspect you wanted to know whether *humans* can write down a Turing Machine for some problem. This is really a question about what humans can compute, which is an issue for philosophy. For that, I would suggest looking into the \[Church Turing thesis.\]\[5\]

\[4\]: https://en.wikipedia.org/wiki/Rice%27s\_theorem#:~:text=Rice's%20theorem%20asserts%20that%20it,or%20false%20of%20all%20programs). \[5\]: https://en.wikipedia.org/wiki/Church%E2%80%93Turing\_thesis

---
Tags: turing-machines, turing-recognizable
---


# Question
Title: Proof for boosting success probability of a random algorithm with binary output
There is a theorem stating that, given a random algorithm with a binary output that has a success probability $\geq 2/3$, you can always create the another algorithm that solves the same problem but with a success probability $\geq 1-\delta$ by just repeating the original algorithm $\mathcal{O}(1/\log\delta)$ times and taking a majority vote (stated in this YouTube video at 29:14).

Is there a (preferably simple) proof for this?

Edit: As remarked by Nathaniel there is a typo in my question and it should read $\mathcal{O}(\log(1/\delta))$ (I left the typo above so that the last part of his answer would still make sense in context)

# Answer
The proof I know of uses a weak version of Chernoff bound:

> If $X\_1, X\_2, …, X\_n$ are independent Bernoulli random variables of same parameter $p$, and $X = \sum\limits\_{i=1}^nX\_i$, then: $$\mathbb{P}(X \geqslant n/2)\leqslant \left(\frac{1+p}{\sqrt{2}}\right)^n$$

The idea is the following:

* repeat the algorithm $n$ times;
* denote $X\_i = \left\\{\begin{array}{ll}0 & \text{if the result is correct}\\1&\text{otherwise} \end{array}\right.$ for the $i$-th call of the algorithm.

Those $(X\_i)$ form a sequence of independent Bernoulli random variables of same parameter $p\leqslant \frac13$ (because the probability of failure is lesser than one third).

There is a failure if the majority vote fails, meaning that $\sum\limits\_{i=1}^nX\_i \geqslant \frac{n}2$. Using Chernoff bound, the probability of faillure is lesser than:

$$\left(\frac{1+1/3}{\sqrt{2}}\right)^n = \left(\frac{4}{3\sqrt2}\right)^n$$

Now for the probability of failure to be less than $\delta$, it suffices that:

$$\begin{align\*}\left(\frac{4}{3\sqrt2}\right)^n\leqslant \delta &\Leftrightarrow n\log\_2\left(\frac{4}{3\sqrt2}\right) \leqslant \log\_2 \delta\\ &\Leftrightarrow n\geqslant \frac{\log\_2\delta}{\log\_2\left(\frac{4}{3\sqrt2}\right)}\end{align\*}$$

Note that the last inequality is reversed, because $\log\_2\left(\frac{4}{3\sqrt2}\right)$ is negative.

In conclusion, one need to repeat the algorithm $\mathcal{O}\left(\log \frac1{\delta}\right)$ to get the probability of failure to less than $\delta$. Note that this is different of the $\frac{1}{\log \delta}$ you asked, but since this quantity is negative if $\delta \< 1$, I think it was a mistake.
> 10 votes

---
Tags: complexity-theory, randomized-algorithms
---


# Question
Title: How can I reduce the complexity of an inverse DFT where I have a uniform frequency series being evaluated at non-uniform target points?
I have implemented an N-dimensional Non-Uniform Discrete Fourier Transform (in this case it's specifically an *inverse* NUDFT) using PyTorch. My goal with this implementation is to have a function which is given an N-dimensional array of values and a list of non-grid-aligned, non-uniform points to interpolate its value at. For example, if I had the following pseudocode:

```
image = load_image("some_image.jpg")
frequency_space = fft_n(image)
target_points = random(32, 2)

output = nuidft(frequency_space, target_points)

```

I would expect `output` to contain plausible interpolated values for 32 randomly sampled, non-grid-aligned points in the input `image`.

Currently, I am doing this interpolation by evaluating the Fourier series of the input at the points, but my current implementation is egregiously time- and space-hungry, as it evaluates the IDFT equation for every target point on every one of the points in the frequency space representation of the signal, i.e.:

```
frequency_space = dft_n(x)

target_points = rand(batch_size, n_points, n_dims)

results = empty_like(*x.shape, *target_points.shape)
for coordinates, frequency in frequency_space, :
    for target_point in target_points:
        # evaluate IDFT complex sinusoids at target_point
        # store value in results array.

# take the n-dim mean (double sum for 2D input, triple sum for 3D input, etc)
output = results.mean(dims=range(n_dims))

```

This approach is also given as the first method for *uniform to uniform* IDFT in this person's blog post I found. (specifically the "Direct Evaluation of IDFT" section). Unfortunately, the later methods discussed in the same post are both specific to uniform synthesis (like scaling an image up or down uniformly by a constant factor), which is *not* what I'm trying to do here.

Now, I know that in the *uniform* IDFT, you can drastically reduce the time complexity by leveraging the transform's *separability*, i.e.:

```
idft_1d(idft_1d(x, dim=0), dim=1) == idft_2d(x)

```

So instead of doing $N^2$ operations for a square input of size $N$, you do $2N$ 1D DFTs, which can be cheaply computed using the FFT algorithm.

In my research, I've stumbled across the concept of an N-dimensional Non-Uniform Discrete Fourier Transform, which comes in three variants:

> * The nonuniform discrete Fourier transform of type I (NUDFT-I) uses uniform sample points ${\displaystyle p\_{n}=n/N}$ but nonuniform (i.e. non-integer) frequencies ${\displaystyle f\_{k}}$. This corresponds to evaluating a generalized Fourier series at equispaced points. It is also known as NDFT or forward NDFT
> * The nonuniform discrete Fourier transform of type II (NUDFT-II) uses uniform (i.e. integer) frequencies ${\displaystyle f\_{k}=k}$ but nonuniform sample points ${\displaystyle p\_{n}}$. This corresponds to evaluating a Fourier series at nonequispaced points. It is also known as adjoint NDFT.
> * The nonuniform discrete Fourier transform of type III (NUDFT-III) uses both nonuniform sample points ${\displaystyle p\_{n}}$ and nonuniform frequencies ${\displaystyle f\_{k}}$. This corresponds to evaluating a generalized Fourier series at nonequispaced points. It is also known as NNDFT.

But I am having trouble wrapping my head around which, if any, of these variants might be helpful to me. Thus, my question is: am I missing any obvious shortcuts? Am I doomed to evaluate every sinusoid once for every sample point? Or is there some separability magic I'm missing here than can reduce my complexity to something nicer, something with a $log$ in it instead of just a bunch of exponents?

Apologies if the question is vague, but if I've managed to communicate what I'm searching for adequately, I would massively appreciate being pointed in the right direction.

# Answer
> 0 votes
There are python modules available for the NUFFT, the NUFFT function can be used for this sort-of inverse operation by exchanging the frequencies and times, and multiplying the times by negative 1. Note that this requires the NUFFT moduThis can be shown from the definition of the NUDFT:
$X\_k = \sum\_{n=0}^{N-1} x\_n e^{-2\pi i p\_n f\_k}, \quad 0 \leq k \leq N-1,$
you can see that exchanging p (the sample points) with f (the frequencies) and inverting one of them, we get
$X\_k = \sum\_{n=0}^{N-1} x\_n e^{2\pi i f\_n p\_k}, \quad 0 \leq k \leq N-1,$
which is equivalent to the definition of the Uniform IDFT given below after swapping $X\_k$ and $x\_n$ in the uniform case.
$x\_n = \frac{1}{N} \sum\_{k=0}^{N-1} X\_k \cdot e^{i2\pi \tfrac{k}{N} n}$
I am not familiar enough with image processing or any of these particular libraries to say how to extend this to the two-dimensional case, but I don't believe it should be terribly complicated.

Several NUFFT modules exist and I am not sure which one would be the best for your application.

References: https://en.wikipedia.org/wiki/Discrete\_Fourier\_transform
https://en.wikipedia.org/wiki/Non-uniform\_discrete\_Fourier\_transform
https://www.mathworks.com/help/matlab/ref/double.nufft.html
https://www.mathworks.com/help/matlab/ref/double.nufftn.html
https://www.mathworks.com/matlabcentral/answers/2032659-adjoint-inverse-nufft
https://www.mathworks.com/matlabcentral/answers/829233-how-do-i-invert-a-non-uniform-fft-using-the-nufft-function?s\_tid=sug\_su

---
Tags: time-complexity, optimization, space-complexity, fourier-transform, fast-fourier-transform
---