title: Big-O Notation Statement True?

text:
# Question
Title: Big-O Notation Statement True?
Considering functions f and g, is the following true?

$ (f \in O(g)) \implies (f \in \Theta(g)) \lor (f \in o(g))$

If not, can you please state an example? Despite thinking hard, i could not find one.

Thanks a lot!

# Answer
> 3 votes
No, this is not true. For example, let $f$ be the constant $1$ function, and define $g$ by $g(2n) = 1/n$ and $g(2n+1) = 1$.

---
Tags: asymptotics, landau-notation
---


title: Disco Zoo Complexity

text:
# Question
Title: Disco Zoo Complexity
A popular mobile game, DiscoZoo, is about "rescuing" animals from a 5x5 grid of cells. Each animal represents a unique pattern (some have 3 cells, some have 4). The object is that, given this 5x5 grid, find all (or as many as possible) of the given animals within 10 turns, where the pattern of animals can be at any place within the grid (but cannot be rotated, change size, etc. - only translated such that all the coordinates of each animal are valid, and there is only one animal per square). We can only "get" an animal if we can successfully find each of the squares of that animal within the number of turns left; otherwise, we do not.

Here is an example. The sheep has a pattern of 4 horizontal adjacent squares, so clearly the squares (5, 2) (indexing from 1 and as (row, col)) and (5, 5) will be a sheep (and thus get the sheep). For the rabbit, it has a pattern of 4 vertical adjacent squares, so the squares (2, 1) and (4, 1) will be the rabbit. For the cow, it has a pattern of 3 horizontal adjacent squares, and since square (4, 2) was selected (and no animal placed there), the only square left for the cow is (4, 5). This is assuming that we do have attempts left (but there aren't any for this example).

More formally, we are given a 2D array $a\[1..n\]\[1..n\]$, and $m$ animals $A\_1,...A\_m$ such that $A\_i$ has value $p\_i$. In the grid are the values of the $p\_i$'s (in their respective positions) and all the rest are 0. Each cell either has 0 or one non-zero value (i.e., only one animal). However, none of the values are given to us at the start. Once we "select" a cell, that cell's value is revealed to us. Our objective is to find all or the maximum possible number of non-zero cells in the grid within $g$ turns.

What is the complexity of this problem in general?

**Edit**: after some thinking about the problem, let's restrict ourselves to having $m$ copies of the same animal $A$, and let that animal be a 2x2 square (i.e., occupies coordinates $(x, y), (x+1, y), (x, y+1), (x+1, y+1)$). What is the complexity of this version of the problem?

Even if we restrict further by looking at 1x1 squares, this is equivalent to finding nonzero elements in the matrix - it is trivially solvable in $\Theta(n^2)$ time, but can we do better?

# Answer
> 1 votes
For the 2 by 2 block version in the edit, consider the promise problem where there is guaranteed to be just one block in each 3 by 3 region, where the regions have coordinates $(3i+1,3j+1)$ to $(3i+3,3j+3)$ for non-negative integers $i$ and $j$. By an adversary argument, in the worst case one may have to probe one square in each of the first $\lfloor n/3\rfloor^2-m$ regions and then two squares in each of the last $m$ regions, so in the worst case at least $\lfloor n/3\rfloor^2+m \ge ((n-2)/3)^2+m\ge \Omega(n^2)$ probes.

---
Tags: complexity-theory
---


# Question
Title: How Cellular Automata is related to Automata Theory?
I have read about Automata Theory where it is about the study of abstract machines and automata.

And i know that an abstract machine takes the input, process it and create the output, just like Conway's Game of life.

But, what a formal defination can relate it to Cellular Automata, what about Elementary Cellular Automata, can it related also?

# Answer
> 6 votes
There's no particular relationship. "Automaton" just means "machine" and it's unfortunate that we use the term "automata theory" to describe the study of one particular kind of automaton, rather than using a more specific name. (You can imagine a parallel universe in whcih automotive engineering is called "machine theory" and other mechanical engineers are standing around saying, "We build machines, too!")

Having said that, I assume there's some relationship between cellular automata and automata-theory automata. It's well-known that some automata are Turing complete, in the sense that you can code up a Turing machine as an input to the automaton, set it running and decode what the cellular automaton does as being the operation of the Turing machine. It would not be surprising (to me, as a non-expert in cellular automata) if there are cellular automata that have the same expressive power as regular expressions, i.e., if there are cellular automata that can simulate automata-theory automata but not simulate anything more powerful.

# Answer
> 3 votes
You can actually see cellular automata as various ways to generalize the automata studied by automata theory. While automata studied in automata theory typically have only one reading (and possibly writing) head, have access to a single cell of memory storage at a time (per storage), cellular automata may use multiple reading/writing heads and read multiple cells of the memory storage per operation. Also, unlike other automata, cellular automata may output more than one symbol per operation.

But traditional texbooks on automata theory don't treat cellular automata as a member of the automata family. Cellular automata didn't see much practical use and, maybe because of that, it doesn't have a kind of established hierarchy and a host of theorems covering each aspect as does the automata of automata theory.

There's also a "personal" aspect of this relation. Stephen Wolfram, the person who invested a lot of effort into popularizing the subject has done so with a lot of controversy. He might have been overly "enthusiastic" about his research, while the rest of scientific community responded with patronizing and diminishing commentary (something you might be familiar with from visiting popular social Q&A sites). And so much so that today, for "serious" figures in the said scientific community embracing cellular automata into the family of automata would be too embarrassing (and nobody likes that, yikes!)

---
Tags: automata, computation-models, cellular-automata
---


title: Branch and bound stanford slides doubt

text:
# Question
Title: Branch and bound stanford slides doubt
On the 6th slide at https://web.stanford.edu/class/ee364b/lectures/bb\_slides.pdf, while defining L2 and U2, why are we taking min for both?

# Answer
> 3 votes
The slides are correct: remember that we are trying to find a bound on the *optimal value* of $f$, which is defined as $$\Phi\_\mbox{min}({\cal Q}\_\mbox{init}) =\min\_{x\in{\cal Q}\_{\tiny\mbox{init}}}f(x)$$

To find that minimum, we *approximate it* by upper and lower bounds $\Phi\_\mbox{ub}$ and $\Phi\_{\mbox{lb}}$. Let's concentrate on $\Phi\_{\mbox{ub}}$. Note that if ${\cal Q}={\cal Q}\_1\cup{\cal Q}\_2$, then *both* $$ \min(\Phi\_{\mbox{ub}}(\cal Q\_1),\Phi\_{\mbox{ub}}(\cal Q\_2))\geq\Phi\_\mbox{min}(\cal Q)$$ and $$ \max(\Phi\_{\mbox{ub}}(\cal Q\_1),\Phi\_{\mbox{ub}}(\cal Q\_2))\geq\Phi\_\mbox{min}(\cal Q)$$

But we might as well take $\min$, since that is the value that is closer to the *global minimum* $\Phi\_\min(\cal Q)$!

In fact, taking the minimum is going to be *necessary* if we want the branch and bound method to converge to the minimum as we sub-divide $\cal Q$ into smaller and smaller pieces.

---
Tags: algorithms, optimization, linear-programming
---


# Question
Title: How does one enter in a boolean expression into an SAT solver?
For example, if we had an extremely large expression, how do we even first get it into the program? I can't imagine entering each clause in one by one..

# Answer
Typically, the huge SAT instance is generated by a reduction from some other problem, so it's computer-generated in the first place. You write it to a file and tell the SAT solver to read it.
> 2 votes

---
Tags: computability, np-complete
---


# Question
Title: How many languages exist with input alphabet {0,1} and all strings in the language have length less than or equal to 5?
I'm trying to write a formal proof in automata theory to show a few properties of DFAs but I am having some trouble with this that I am trying to incorporate into my proof. I want to show how many languages $S$ there are such that $S\subseteq\\{0,1\\}^\*$ and $\forall s\in S, |s|\leq 5$ where $s$ is a string.

I got that there are $2^1+2^2+...+2^5 = 62$ different strings such that $|s|\leq 5$ but that is where I am stuck. How many different languages can I create with $62$ strings? Would it simply be $62!$ ?

# Answer
> 7 votes
First, you seem to have missed the empty string, so there are actually 63 possible strings. In any language, each of the 63 strings could either be in or not in the language, so there will be a total of $2^{63}$ different languages. In the jargon, that's a BFN.

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


# Question
Title: Can quantum computer become perfect chess player?
Can quantum computer become perfect chess player?

Can it determine whether (when both players are perfect) win white or black? (or is it dead heat?)

# Answer
I've already answered essentially this question, on Chess Stack Exchange. The executive summary is that chess doesn't seem particularly well-suited to quantum computation's strengths so there's no particular reason to believe that a quantum computer would be any better at it than a classical one.
> 6 votes

# Answer
Quantum computers can evaluate game trees asymptotically faster than classical computers, but this advantage is not sufficient to solve chess.

Wikipedia gives an estimate of $10^{123}$ for the game tree complexity of chess. The best known classical algorithm can solve a randomized NAND tree of size $N$ in $O(N^{0.793})$ steps. The quantum algorithm mentioned in the blog post I linked to can do it in roughly $O(N^{0.5})$ steps. Ignoring constant factors and other important things, this roughly means the quantum algorithm can explore and solve the chess game tree in $\sqrt{10^{123}} \approx 10^{62}$ steps instead of $10^{92}$ steps.

Unfortunately, $10^{62}$ is still obscenely gigantic. It is "consume all the entropy in the galaxy just to run the computation" levels of absurd. Maybe there's a tractable algorithm out there that can play chess perfectly, by relying on the fact that its game tree has more structure than an arbitrary NAND tree, but just switching from classical to quantum isn't enough.
> 5 votes

---
Tags: quantum-computing
---


# Question
Title: How would I simulate a network to explore the percolation threshold of a network connected by the knight's move?
"If we consider the squares of an infinite chess board as nodes of our graph and consider each to be connected to the other eight squares that are a knight's move away from it what is the percolation threshold of this graph?"

Note:One way I have thought about this problem is to try to use vectors: We can think of a knight's move as a vector of the form $\<\pm1,\pm2\>$ or $\<\pm2,\pm1\>$ for the eight cases.

In answering this question I think I need to create a simulation. How would I create a program to simulate an infinite board, for instance, and remove random nodes to create a graph with a percolation value.

# Answer
> 4 votes
First of all, you don't simulate an infinite board. You simulate larger and larger boards, until the percolation threshold seems to stabilize. For a given size of board, you need to decide on what event signifies that percolation happens. One common option is that the top of the board is connected to the bottom of the board. For each probability $p$, you estimate the probability that this happens by doing many samplings. You then use binary search to estimate the probability $p\_c$.

Here are some more details. Suppose you've decided on some board size. The first step is to compute all the edges, that is all pairs of vertices connected by a knight's move. Given a probability $p$, you run the following experiment many times. Put in each edge with probability $p$ independently. Then check (using DFS/BFS or equivalent) whether the top of the board is connected to the bottom of the board (that is, add a new "top" vertex connected to all vertices at the top of the board, add a similar "bottom" vertex, and check whether the two are connected). Do this many times, and estimate the probability $\theta(p)$ that "bottom" is connected to "top". Then use binary search on $p$ to find a value of $p$ such that $\theta(p) \approx 1/2$, say. This is your estimate for the critical probability.

---
Tags: graphs, graph-traversal, simulation
---


title: Homomorphism Languages

text:
# Question
Title: Homomorphism Languages
Let $h$ be a homomorphism and let $L$ be a language. Writing ${}^\*$ for Kleene star, I want to show that $(h^{-1}(L))^\* \neq h^{-1}(L^\*)$. Can I prove this just by showing that we can have $h^{-1}(L)$ to be empty (because no strings are mapping into $L$) and therefore the right side is the empty set? Doing the same to the left side gives $\emptyset^\* = \\{\epsilon\\}\neq\emptyset$.

# Answer
> 3 votes
Unfortunately both sides contain the empty string. As you say, the Kleene star of the empty set also contains the empty string: $\varnothing^\* = \\{ \lambda\\}$. The Kleene star of a language $L$, equals $L^\* = \cup\_{i\ge 0} L^i$, where $L^0 = \\{\lambda\\}$ and $L^i = L \cdot L^{i-1}$ for $i\ge 1$.

On the other hand $h(\lambda) = \lambda$ for any morphism $h$, so $\lambda \in h^{-1}(K)$ whenever $\lambda \in K$. As $L^\*$ contains the empty string this is the case here.

However, this does not mean the two sets are equal. Consider $h:\\{a,b\\}^\*\to \\{a\\}^\*$ defined by $h(a) = a$ and $h(b) = aa$ and $L=\\{a\\}$.

---
Tags: formal-languages, correctness-proof
---


# Question
Title: How to draw a automaton with this description?
I'm having trouble drawing an automata with this description S ← abb|aab|aaabbb|aaaS|Sbbb.

I have tried drawing the abb and aab states but am having trouble making this into one automaton

# Answer
This is an option

an alternative method to solve this:

1. Convert to Right Linear Grammar G

G = (N, T, P, S)

N = no terminals

T = terminals

P = productions

S = Initial symbol
2. Your new automaton A is

A = (N U {qf}, T, d, S, {qf})

qf is a new element

d:

Y belongs d(X, a) if X -\> aY belongs to P

qf belongs d(X, a) if X -\> a belongs of P
> 1 votes

---
Tags: automata
---


# Question
Title: Can I write a regular expression or regular grammar for this language?
Let's say I have a formal language,

> a^n b^n which mean ab,aabb,aaabbb

Can I write any regular expression or grammar to create a language like this? I am positive not entirely sure that there is not regex possible, however have no idea about the grammar part?

# Answer
This language is context-free but not regular. It is isomorphic to the problem of matching open and closed parentheses: `(<sup>n</sup>)<sup>n</sup>` which is a well-known non-regular language. To prove this yourself, you would use the pumping lemma for regular languages.

Every regular grammar describes a regular language.
This language is not regular.
Therefore, there cannot be a regular grammar that describes it.
> 3 votes

---
Tags: regular-languages, regular-expressions
---


# Question
Title: Calculating execution time for recursive algorithm
How would I calculate the execution time, T(n), for this algorithm?

```
int search(int a[], int l, int r, int x) {
    int m = (l+r)>>1;
    if (l > r) return -1; // not found
    if (a[m] == x) return m;
    if (a[m] > x) return search(a, l, m-1, x);
    return search(a, m+1, r, x);
}

```

# Answer
> 4 votes
I'm assuming that the one if statement is not supposed to be on the same line as the comment... if that is intentional it does change things up somewhat :)

```
int search(int a[], int l, int r, int x) {
1.    int m = (l+r)>>1;
2.    if (l > r) return -1; // not found
3.    if (a[m] == x) return m;
4.    if (a[m] > x) return search(a, l, m-1, x);
5.    return search(a, m+1, r, x);
}

```

I am also assuming T(n) means you are looking for the worst-case scenario (eg. the number you are searching for was the last one you checked, or was not found at all). The most straight forward way of solving these is to simply trace it through line by line, keeping track of the values of the variables in a table, until you notice a pattern emerge. Now, note that finding a pattern by itself **never proves** that the pattern you found is actually correct, but it will give you a good place to start, and will frequently (but not always) even yield the correct solution to the problem.

So, that being said, here's the gist of how I traced through it, minus a table with variable values like r/2, r/4, etc.

* m is being set to halfway between l and r in line 1 (I suppose doing it with a bitshift is more efficient...)
* The worst case would definitely involve running the search again. However, you can tell that this time either r is going to be halfway closer to l (line 4) or l is going to be halfway to r (line 5)
* m is being set to halfway between l and r again, and so on, until m cannot be cut in half anymore (this will occur in line 2 where l \> r)

m keeps getting cut in half again and again until it cannot get cut in half. This pattern implies that maybe (probably) T(n) = O(log2 n). If you need to prove its correctness you would need to do a more formal direct proof than a trace. You could use Master's Theorem to prove its correctness as well.

If you are going to be doing a lot of these or if you need to prove the correctness of these it may be worth your time to look up how Master Theorem works, as getting your mind around that will make these a lot easier.

---
Tags: time-complexity, asymptotics, runtime-analysis
---


# Question
Title: Data strucutre for finite graphs on a cylinder
My problem is to find an efficient data structure that allows the encoding of a (non-directed) graph on the surface of a cylinder (without top and bottom discs). Usually I would store a graph as a list of edges, which are pairs $(a,b)$ of vertices. My problem is that I can have two kinds of edge from $a$ to $b$ either by taking the shortest path or going around the cylinder. These two edges should be considered as being different.

My set of vertices is fixed ($n$ vertices on the top circle, $n$ vertices on the bottom circle of the cylinder) and I requires that, for any vertex, there exists precisely one edge to another vertex. Furthermore crossings of edges are not allowed (that is why it is important to be able of "going around" the cylinder; taking a "longer" way).

The aim then is to glue two such cylinders together (the bottom of one goes on the top of the other) and compute the connected components of the "glued" graphs, which will produce another graph on a cylinder.

Of course one could just tag the edges, depending whether one goes the shortest or longest way, but maybe someone has a better idea!?

# Answer
Let the vertices at the top be $a\_0, \dots, a\_{n-1}$ and those at the bottom be $b\_0,\dots, b\_{n-1}$, both ordered, say, clockwise. If the graph has no edge-crossings, the edge set can only be $\\{(a\_i,b\_{i+k})\mid 0\leq i\leq n\\}$ for some $k$, with addition carried out modulo $n$. So the edge set is uniquely determined by the value of $k$.

Beyond that, though, it's not clear what you're asking. The embedding of the graph in the surface of the cylinder could be much more complicated than you're suggesting. For example, the edges could all spiral anticlockwise around the cylinder thirteen times. Or they could spiral anticlockwise three times, then clockwise four times, and then wiggle around lots. Perhaps you have a requirement that the edges can't spiral multiple times? And/or that they're straight lines if you "unwrap" the cylinder and lay it flat? If so, note that gluing two cylinders together doesn't maintain this property: for example, if you glue the cylinder that has edges $(a\_i,b\_{i+1})$ using shortest paths to the cylinder that has edges $(a\_i,b\_{i-1})$ using shortest paths, you get a cylinder whose edges zig-zag, so aren't straight lines, don't use shortest paths and don't "go the long way around". Likewise, if you glue $2n$ copies of the cylinder that uses shortest paths to link $a\_i$ to $a\_{i+1}$, you get a cylinder whose edges spiral twice.
> 1 votes

---
Tags: graphs, data-structures
---


# Question
Title: Why can we not read and write to the same address at the same time?
I was reading Wikipedia about the von Neumann bottleneck.

Surely there is some simple answer to this. Why can we not read and write to the same address at the same time? We can if the addresses are different.

# Answer
> 5 votes
In other models (a distributed architecture, for example, with several processors) you can often do concurrent reads, where two or more processors are able to read a word from memory simultaneously. The problem with concurrent writes is more complicated since you have the possibility of a race condition: if one processor wants to write 31 to a memory location and at the same time another processor wants to write 0 to that location, the behavior of the system might not be predictable so running a program twice might result in two different results. Dealing with this problem can be tricky, as you might imagine. That's not to say it can't be handled, only that it's more complicated.

# Answer
> 2 votes
In my understanding, reading and writing to the same address "at the same time" (or called "simultaneously") in your post means that the read and the write "overlaps" with each other: every operation takes time, no matter how short it is.

The "overlapping" can be interpreted in different levels. At a high level, any two concurrent operations (i.e., no one ends before the other one starts) in a multiprocessor computer can be regarded "overlapping" with each other. (Also see the answer by @Rick Decker)

You are probably more interested in the case that "simultaneous" read & write happen on a physical level. If so, dual-port RAM may be relevant.

Quote from the "dual-port RAM" document:

> The dual-port configuration has two separate blocks (block A and block B) and corresponding clocks (CLKA and CLKB). This allows the user to perform both read and write operations on both blocks A and B. However, when performing simultaneous operations there may be data collisions and undesired data may be obtained at the output.

---

**Note:** The information about "dual-port RAM" is from a comment on a question about "safe registers" at cs.theory.

---
Tags: computer-architecture
---


title: Where is the ambiguity in this grammar?

text:
# Question
Title: Where is the ambiguity in this grammar?
I am trying to understand ambiguous grammar in programming languages. I was given this ruleset and told it was ambiguous. If my understanding is correct, this means that it is possible to create the same sentence using different parse trees. After looking at it for a while, I can't find the sentence/parse trees that show the ambiguity.

s ::= a

a ::= a a | A | B | C

# Answer
> 1 votes
More a tip than an answer, but it should get you to the solution:

Try to produce a word with 3 terminal symbols. Can you find more than one syntax tree for the same word?

---
Tags: formal-grammars, ambiguity
---


title: Starting BFS at s and t

text:
# Question
Title: Starting BFS at s and t
INPUT: undirected graph, s, t

OUTPUT: connectivity of s and t

I perform BFS on s AND t, each taking turns to make one traversal.

When a vertex exists in both s and t's BFS tree, we can assume it is connected.

When one tree is done traversing but the other is not, s and t are not connected.

Does such an algorithm exist or am I making stuff up?

# Answer
> 4 votes
Yes, this is a known thing. It's called bidirectional search. It will find shortest paths in unweighted graphs and, in graphs of where every vertex has degree $d$, it will visit at most $2d^{\ell/2}=2\sqrt{d^\ell}$ vertices (where $\ell$ is the length of the shortest path), whereas ordinary BFS could visit up to $d^\ell$ vertices.

---
Tags: algorithms, graphs, search-algorithms, search-trees, graph-traversal
---


# Question
Title: Can Eve impersonate Alice or Bob by using a replay attack?
For my computer science study, I have to design a replay attack (if possible) for the following authentication protocols.

I use the standard security protocol notation. In these protocols, $A$ is Alice, $B$ is Bob and $E(A)$ is for example Eve impersonating Alice. $K\_{AB}$ is a shared secret key only Alice and Bob know, $K\_{AB}\\{x\\}$ is the data $x$ encrypted with this key, and $N\_A$ and $N\_B$ are fresh random nonces generated by $A$ and $B$. We assume that Eve cannot simply break the encryption.

a)
$1. A \rightarrow B : A, K\_{AB}${$N\_A$}
$2. B \rightarrow A : B, N\_A, K\_{AB}${$N\_B$}
$3. A \rightarrow B : A, B, N\_A, N\_B, K\_{AB}${$N\_A, N\_B$}

For this, I designed the following replay attack:

$1. A \rightarrow E(B) : A, K\_{AB}${$N\_A$}
$2. E(A) \rightarrow B : A, K\_{AB}${$N\_A$}
$3. B \rightarrow E(A) : B, N\_A, K\_{AB}${$N\_B$}
$4. E(B) \rightarrow A : B, N\_A, K\_{AB}${$N\_B$}

Is this gonna work?

The next example is this:

b)
$1. A \rightarrow B : A, N\_A, K\_{AB}${$A, N\_A$}
$2. B \rightarrow A : B, N\_B, K\_{AB}${$B, N\_A, N\_B$}
$3. A \rightarrow B : K\_{AB}${$A, B, N\_A$}

I have no idea how to solve this one. Could you please help me with that?

# Answer
well, you don't really explain what happens in each step, and how the authentication procedure works, but your first suggestion is at the right direction. However, the impersonator wishes to authenticate himself, so the attack should actually be

$1. A \rightarrow E(B) : A, K\_{AB}${$N\_A$}
$2. E(A) \rightarrow B : E(A), K\_{AB}${$N\_A$}
$3. B \rightarrow E(A) : B, N\_A, K\_{AB}${$N\_B$}
$4. E(B) \rightarrow A : E(B), N\_A, K\_{AB}${$N\_B$}

and you are missing the last reply, but it is easy to see that Eve can generate both $N\_A$ and $N\_B$ and thus succeed with authenticating itself. Try to write it more carefully: what exactly is begin sent at each step (i.e., what is the meaning of sending "A"?), and what verification each side performs at each step.

For the second example, such an attack cannot work. The identity $A$ is included inside the encryption, and Eve has no way to replace it.
> 3 votes

---
Tags: security, protocols, authentication
---


# Question
Title: Heuristics for space-efficient storing of Unordered Finite Sets in a DFA
I've got an algorithm I'm working on that generates, stores, and iterates through a large number of finite sets. I'm finding that memory is a bottleneck long before time is.

The finite sets are subsets of the vertices $V$ in my graph, so each finite set is small, there's just a lot of them.

In an effort to save space, I've started representing the finite sets as binary words of length $|V|$, with a 0 indicating the element is not in the set, a 1 indicating that it is. I'm storing the collection of these words as an acyclic deterministic automaton (also known as DAWG, directed acyclic word graph).

However, this requires a fixed ordering of the potential elements, which is fine, but arbitrary. If a different ordering were more likely to produce a smaller output set, I'd be happy to use it.

I'm wondering:

* Is there a known, efficient algorithm for finding the permutation which gives the smallest DFA representing a set of finite sets?
* If not, has any research been done on heuristics for orderings which have been shown to often produce smaller DFAs?

# Answer
It sounds like you are describing a binary decision diagram, also known as a BDD. BDD's have been studied extensively in the literature, so you might take a look at the literature.

In particular, the question of finding the best permutation is known as the "variable ordering" problem for BDDs. Finding the optimal variable ordering is NP-hard. There are some heuristics, but they don't always work. See https://en.wikipedia.org/wiki/Binary\_decision\_diagram#Variable\_ordering. Probably the easiest approach is to use an existing BDD library (the standard ones will typically incorporate some variable ordering heuristics).

You might also be interested in ZDDs.
> 2 votes

---
Tags: formal-languages, graphs, data-structures, finite-automata, data-compression
---


title: Can a regular expression be infinite?

text:
# Question
Title: Can a regular expression be infinite?
I know that languages which can be defined using regular expressions and those recognisable by DFA/NFA ( finite automata ) are equivalent. Also no DFA exists for the language $\\{0^n1^n|n \ge 0\\}$. But still it can be written using regular expressions ( for that matter any non-regular language can be ) as $\\{ \epsilon \\} \cup \\{01\\} \cup \\{0011\\}......$ . But we know that every language that has a regular expression has a DFA that recognises it ( contradiction to my earlier statement ). I know this is a trivial thing, but does the definition of regular expression includes the condition that it should be finite ?

# Answer
> 24 votes
If regular expressions were allowed to be infinite, then *any* language would have been regular.

Given the language $L=\\{w\_1, w\_2, \ldots\\}$, we can always define the regular expression $R = w\_1 + w\_2 + \cdots$, which exactly defines $L$.
(Example: the regular expression $R\_1 = \epsilon+0+1+00+01+10+11+\cdots$ defines $L\_1=\\{0,1\\}^\*$.)

We know that some languages are not regular, so this shows that infinite regular expressions describe a larger class of languages than finite regular expressions.

# Answer
> 5 votes
Yes, it must be finite. Imagine you have that infinite set of possible matches, and your input is `011`. Would you ever be able to reject it? Would you ever run out of matches to check?

Is there any language that, by that definition, would not be *regular*? What about the set of all pairs of programs and inputs such that the given program halts on the given input?

Now, if you had a program that enumerated the strings in a language in lexicographical order—

### Update

To clarify a bit based on feedback in the comments, the reason not every language of this form is regular is by definition. If, for example, you look up the proof of Kleene’s theorem, it depends on the fact that a regular expression must be finite to prove that it generates a finite state machine.

Why do we define “regular” language that way? Because every formal language is a subset of the strings on an alphabet, and every set of strings can be expressed as a union of singletons, so if we called any set of strings a “regular” language, *regular language* would just be a synonym for *language*. That’s not a very useful definition, especially since we can’t actually implement it in hardware or software. We can’t store an arbitrary infinite list anywhere or build an infinite-state machine.

As I hinted, though, if you have a way to enumerate all the strings in a language in order, you can build a decider from that (accept when you see that exact string, reject when you encounter a string that comes after the one you’re looking for) and vice versa (for each string in order, run it through the decider and output it if and only if it’s accepted). So, if we considered every enumerable language *regular*, every decidable language would be “regular” and we would need a new term for the languages recognized by finite state machines and their equivalent encodings as finite expressions.

# Answer
> 0 votes
Suppose regular expressions were allowed to be infinite.

Thus language defined by {ϵ}∪{01}∪{0011}... will be regular. For every regular language there exists a NFA. One way to get this NFA would be to have individual NFAs for each of {ϵ},{01},{0011}... and combine them using ϵ transitions. Since there are infinite distinct regular expressions, we will need infinite sub-NFAs to be combined. However NFA can have only finite number of states (definition of NFA).

Thus there exists no NFA that can define language defined by union of infinite regular expressions, which implies the language is not regular.

Thus there is no regular expression which can define same language as the language defined by union of infinite regular expressions.

Thus regular expressions can have only finite expressions.

---
Tags: formal-languages, regular-languages, regular-expressions
---


# Question
Title: Directed cyclic graph with node rewards and arc costs
The problem I have seems fairly simple and I feel it must have some kind of name. I have a (directed cyclic) graph. Each node has an associated reward for visiting it, and each arc costs a certain amount of time to traverse it. The reward is consumed on visiting once, so a path may visit a node multiple times but receives 0 reward for future visits.

Is there an algorithm for maximising the reward while proceeding from node A to node B (or back to A again) in a given maximum amount of time available?

Note that the times and rewards cannot be combined as a single "weight".

The data is sparse and isn't that big: a few hundred nodes which typically have less than 5 arcs each.

Any tips on modelling and/or algorithms greatly appreciated.

# Answer
> 1 votes
---

I think this problem is NP-Complete via reduction to Knapsack Problem

An instance of the Decision Problem involves: a Graph g, time alloted, sum\_reward, and two nodes s,t : *Is there path from s to t with sum of rewards\>=sum\_reward within the alloted time period?*

## Reduction

Add nodes $s,t$ and an edge $s-\>t$ with reward,weight =0. For every item a=(value(a),weight(a)) create a node $n\_{a}$ and the following two edges:

* $e\_{a}= s-\>n\_{a}$ with $reward(e\_{a})=value(a)$ and $cost(e\_{a})=weight(a)$
* $e\_{b}= n\_{a}-\>s$ with both values zero

I just noticed that rewards are on nodes instead of edges. But this does not change the reduction(just transfer reward from edge to node)

Now run the algo for input ($G',knapsack$ $size$,$sum$ $reward,s,t$)$

IFF proof

=\> if knapsack is feasible, simply iterate over edges of nodes contained in the knapsack and finally hop from s to t. This will give the desired sum\_reward

\<= More or less, the same idea.

I hope this helps you somehow :)

Since your data is kind of special, perhaps someone can provide an exact algorithm instead of an approximation one. I cannot (yet :P)

# Answer
> 1 votes
This problem is NP-hard by a simple reduction from the directed Hamilton cycle problem. Given a graph $G$ with $n$ nodes, simply set all edge weights to $1$ and place a positive reward on every node. Observe that $G$ has a directed Hamilton cycle if and only if it is possible to collect all rewards in $n$ time units on a round trip starting at an arbitrary node. Hence your problem is NP-hard and I would not be too hopeful to find an efficient algorithm for solving it exactly.

---
Tags: graph-traversal, weighted-graphs
---


# Question
Title: Variant of (WEAK) PARTITION with 2 distinct solutions
I am interested in the complexity of the following problem:

Input: A list $a\_1\leq ⋯ \leq a\_n$ of positive integers.

Question: Are there two vectors $x, x'\in\\{−1,0,1\\}^n$, with at least one $x\_i$ and one $x'\_i$ non-zero (the subsets must be non-empty), such that $$\sum\_{i=1}^nx\_ia\_i=0, \sum\_{i=1}^nx'\_ia\_i=0 \text{ and } x\_ix'\_i=0 \text{ }\forall i.$$ WEAK PARTITION is a variant of PARTITION where we are looking for a partition of a subset of the input, and not a partition of all the integers. This is the reason why we have $\\{−1,0,1\\}^n$ and not $\\{−1,1\\}^n$. Note that the subset must be non-empty, it means at least one $x\_i$ must be non-zero.

But I am interested in the problem described above where we are looking for two distinct weak partitions. For example, with $A=(1,2,3,4,5,7,11,11)$, we have $x=(1,0,1,0,0,1,-1,0)$, $x'=(0,1,0,1,1,0,0,-1)$ and for each component $i$ we have $x\_ix'\_i=0$. It means we have two disjoint subsets of $A$ where there is a weak partition.

There is clearly a reduction from WEAK PARTITION but I suspect this problem to be NP-hard in the strong sense. Do you see any reduction from a problem which is NP-hard in the strong sense ?

Thank you very much.

# Answer
> 4 votes
No such reduction is likely to exist (unless P=NP). In particular, there's a pseudo-polynomial time algorithm for your problem, so your problem isn't strongly NP-hard (unless P=NP).

The algorithm uses dynamic programming and is a straightforward modification of the dynamic programming algorithm for PARTITION. Define $f(j,y,z)$ to be 1 if there exists two non-zero disjoint vectors $x,x'$ of the required form such that

$$\sum\_{i=1}^j x\_i a\_i = y, \sum\_{i=1}^j x'\_i a\_i = z.$$

Otherwise, $f(j,y,z)=0$. Also define $g(j,y)$ to be 1 if there exists a non-zero vector $x$ such that $\sum\_{i=1}^j x\_i a\_i = y$, or 0 otherwise.

Note that $f,g$ satisfy the following recurrence relations:

$$\begin{align\*} f(j,y,z) = &f(j-1,y,z) \lor f(j-1,y-a\_j,z) \lor f(j-1,y+a\_j,z) \lor f(j-1,y,z-a\_j)\\ &\lor f(j-1,y,z+a\_j) \lor (g(j-1,y) \land z=\pm a\_j) \lor (g(j-1,z) \land y=\pm a\_j).\\ g(j,y) = &g(j-1,y-a\_j) \lor g(j-1,y+a\_j) \lor g(j-1,y) \lor (y=\pm a\_j).\end{align\*}$$

The base cases are $f(0,y,z)=0$ and $g(0,y)=0$ for all $y,z$.

With this recurrence, evaluate $f(j,y,z)$ and $g(j,y)$ for all $0 \le j \le n$ and all $y,z$ satisfying $|y|,|z| \le a\_1 + \dots + a\_n$. Each such value can be computed in $O(1)$ time using memoization / dynamic programming.

Finally, look at the value of $f(n,0,0)$ that you computed. If $f(n,0,0)=1$, then there is a solution to your problem (i.e., there exists two disjoint vectors $x,x'$ that each represent two disjoint weak partitions).

What's the running time of the algorithm? If the inputs are represented in unary, the number of $f$-values we compute is polynomial in the size of the input, and each $f$-value can be computed in $O(1)$ time using the recurrence relation above. It follows that this dynamic programming algorithm runs in polynomial time, if the inputs are provided in unary.

---
Tags: complexity-theory, reductions, partition-problem
---


# Question
Title: How does one find out whether $N = a^b$ for some integer $a$ and $b$?
I was trying to find out how to find whether $N$ is a perfect power or not for some $a$ and $b$ (so the algorithm should discover that it is not a perfect power if it is not expressible in the form $a^b$).

My intuition tells me that for every value of the exponent $b$ we can binary search $a$ in the set $\\{ 1,...,N-1 \\}$. However, what I am not convinced yet is that this algorithm won't run forever, i.e. that we won't try new values of $b$ forever. Are there efficient algorithms?

# Answer
> 6 votes
Yes, your approach is a good one. The only thing you missed is that there's a simple upper bound $b \le \lg N$.

Do you see why? It's easier to see why if you state more carefully the problem you are trying to solve. You are asking whether there exist $a,b \in \mathbb{N}$ such that $a \ge 2$, $b \ge 2$, and $a^b=N$. Taking logs of both sides, we get $b \lg a = \lg N$. From the fact that $a \ge 2$, we see $\lg a \ge 1$, so $b = (\lg N)/(\lg a) \le \lg N$.

Therefore, here is a simple algorithm:

* For $b=2,3,\dots,\lg N$:

+ Use binary search to search for $a \in \mathbb{N}$ such that $a^b=N$.

Each iteration of the loop will take $O(\lg N)$ time (the time for a binary search over at most $N$ possibilities), and you do $\lg N$ iterations of the loop, so the total running time $O((\lg N)^2)$.

In particular, yes, this will always terminate. You don't need to keep trying new values for $b$ forever, since we know that $b$ is an integer and is no larger than $\lg N$.

The running time of the algorithm can be improved a bit by replacing the binary search with a faster algorithm to compute $\sqrt\[b\]{N}$; for instance, you could use Newton's method. But the basic method above is already very efficient.

---

You might be tempted to iterate over all possible values of $a$, and then do a binary search for $b$. Don't do that; there are $\Theta(\sqrt{N})$ possible values of $a$, so this will be unavoidably slow.

Instead, a better approach is to iterate over all possible values of $b$, and then do a binary search for a matching $a$. This is much faster, as it needs only $\Theta(\lg N)$ binary searches rather than $\Theta(\sqrt{N})$ of them.

One person mentioned factoring $N$. This is much slower. Our best algorithms for factoring run in subexponential time; they are much slower than the $\Theta((\lg N)^2)$ running time of the algorithm above.

# Answer
> 0 votes
In addition to what @templatetypedef described, assuming we are talking about natural numbers, $a \> 1$, and $b \> 1$ we can make the following considerations:

* The greatest number $a$ we have to consider is $sqrt(N)$, being that $sqrt(N)^2 = N$, so $a \<= sqrt(N)$.
* From the numbers we got in the previous point we can consider only half of them; even numbers if $N mod 2 = 0$, odd if $N mod 2 = 1$
* The bigger $a$ is, the smaller $b$.

So, summing it up, you can follow the algorithm suggested by @templatetypedef while keeping in mind the lower/upper limits of $a$ and $b$, and avoiding odd/even numbers depending on $N$. If you need the greates $a$ possible you just start with the greatest $a$ such that $a \<= sqrt(N)$. If you need the smallest you can start with $a = 2$.

---
Tags: algorithms, decision-problem, diophantine-equation
---


# Question
Title: Are all minimum spanning trees optimized for fairness?
I know by definition that a minimum spanning tree (MST) of a weighted, connected graph has the lowest global value for for sum of all edges in a path that connects all vertices.

I'm curious if all MSTs are also optimized for lowest individual edge value possible. (I know that ones calculated with Kruskal's Algorithm are!)

As an example, is it possible to have two MSTs in a graph (equal global sum of their edges) but have one of those MSTs contain an edge of higher value than any edge on the other MST in the graph.

Thanks for any help you can give!

# Answer
> is it possible to have two MSTs in a graph (equal global sum of their edges) but have one of those MSTs contain an edge of higher value than any edge on the other MST in the graph.

No, it isn't; assume it is, let $X$ be the MST with the heavy edge, and call that heavy edge $e := \\{u,v\\}$. Now there is some other MST $Y$ that doesn't contain edges that are at least as heavy as $e$. In $Y$, we know that there is a path from $u$ to $v$ since $X$ has such a path, so $Y$ must have one as well. Let $p$ denote that path in $Y$. There must be an edge $f$ on $p$ that isn't in $X$, since otherwise $X$ would contain the cycle formed by $p$ and $e$. Now add $f$ to $X$ and delete $e$ from it to get $X'$, which is a spanning tree as well. However, $X'$ has lower weight than $X$ since $f$ has lower weight than $e$, contradicting the assumption that $X$ is an MST.

For something more general which might answer your question more succinctly, here and here are proofs that all MSTs of a graph have the same multiset of edge weights, that is: if $k$ edges of weight $w$ occur in some MST, then $k$ edges of weight $w$ occur in all MSTs for any $w$ and $k$.

---

Something else that isn't proven in those answers that might be of interest to you: every MST only contains paths with smallest maximum weights for all pairs of vertices $\\{u,v\\}$, or in words: let $p$ be the unique path between $u$ and $v$ in a given MST $T$ of graph $G$; then for any $u$-$v$-path $q$ in $G$, the heaviest edge on $q$ is at least as heavy as the heaviest edge on $p$.

To prove this, assume that there is some pair $\\{u,v\\}$ such that the heaviest edge in the unique $u$-$v$-path $p$ in some MST $T$ is heavier than the heaviest edge in some other $u$-$v$-path $q$ in $G$. Let $e$ denote the heaviest edge in $p$; now remove $e$ from $T$, which partitions $T$ into two connected components $U$ and $V$ such that $u \in U$ and $v \in V$. We know that $q$ starts in $U$ and ends in $V$, so there must be an edge $f$ that belongs to the cut $(U,V)$. Now we find that $(T \cup \\{f\\}) - \\{e\\}$ is a spanning tree again, and since the weight of $f$ is smaller than the weight of $e$ by assumption, we find that $(T \cup \\{f\\}) - \\{e\\}$ has lower weight than the MST $T$, contradicting the minimality of $T$. Thus, no such path $q$ can exist in $G$.

Spanning trees with the heaviest weight being minimal are called minimum bottleneck spanning trees, and you can use the above to show that every MST is an MBST (the converse does not hold, i.e. there may be an MBST that is not an MST, specifically: an MBST might use too many heaviest edges). If an MST $T$ wasn't also an MBST, then there would be a heavier edge in $T$ than in some other spanning tree, and that edge would be on some path, and then the arguments above apply to that path.
> 8 votes

---
Tags: graphs, minimum-spanning-tree
---


# Question
Title: Is it possible to come up with a graph instance that would force Dijkstra to perform a decrease key on every single edge?
From the analysis of Dijkstra there is a $O(mlogn)$ factor that assumes we do a decreasekey for every single edge of the given input graph.

However I find it hard to come up with an instance that can actually require this. All you have to do create the edges and then add the weights in a way that would induce a large number of decrease keys.

Is there any known way of doing that?

# Answer
Yes!

A bit convoluted example is the following:

Suppose you have $n+1$ nodes and you run djikstra from $a\_{0}$ Let $A=\[a\_{0},a\_{1},a\_{2}.....,a\_{n}\]$ the final result of the algorithm(i.e the nodes of the graph sorted by their distance from $a\_{0}$)

We will now create a graph which will require every edge to be updated:

First of all add edge $e\_{i}=(a\_{i} , a\_{i+1}) $ with $cost(e\_{i})=0$ for every $i\<n$

Let $M$ be a really Big Value.

For every $i\<n$ and $j\>i+1$ add the edge $e\_{ij}=(a\_{i},a\_{j})$ with $cost(e\_{ij})=M-i$

At every step $i$ of the algorithm ALL values of the nodes will be updated.

ex. $M=100, n+1=5$

Distance matrix for $A$

step 0: \[-,0,100,100,100,100\]

step 1: \[-,-,0 , 99, 99 ,99\] and so on....
> 4 votes

---
Tags: algorithms, data-structures, shortest-path
---


# Question
Title: What does Big O notation actually specify?
Regarding time complexity I've read conflicting things:

1) That it is worst case.

2) That is average case.

For example if I want to know the time complexity for inserting into an arbitrary point in a linked list ( not the beginning or the end ), on average it will take

(n/2) operations so we can drop the constant and say

it is

n.

So would Big O be n or would Big Omega be n. Or are they the same thing?

# Answer
$O$-notation is for upper bounds, $\Omega$-notation for lower bounds.

They can both be used to specify average and worst case bounds.

In your example it is *both* $O(n)$ and $\Omega(n)$, since both the upper and lower bounds (of the average case running time) are $n/2$.
> 3 votes

# Answer
Big-$O$ and $\Omega$ are actually defined entirely separately from complexity theory. All they are is properties of functions.

$O$ is used for asymptotic upper-bounds of a function, and $\Omega$ is used for asymptotic lower bounds. If for some functions $f,g$ we have $f \in O(g)$, and $f \in \Omega(G)$, you can use big-theta notation, $f \in \Theta(G)$.

So, we can say something like $n^2 \in O(n^3)$, or $n^3 \in \Omega(n^2)$. That statement is entirely separate from what meaning we are attaching to $n^2$ or $n^2$.

For the formal definition of what we mean by "lower bound" or "upper bound", see here.

When we're analyzing an algorithm, there are a few cost functions we like to look at. One is the greatest time required for any input of size $n$ (worst case), one is average number of steps for an input of size $n$. There are numerous other things you can look at, such as the number of bits of memory used, the maximum number of cache misses, the number of queries to a database, etc.

The important thing is, all of these are just functions, and we can describe them with any of $O, \Omega, \Theta$. Big-O and friends describes their growth, but carries no meaning if we don't specify what function's growth we are describing.

Note that worst-case and upper bounds are different things. The "worst-case complexity" means, for any input of size $n$, what is the greatest time the algorithm takes. What's important here is, we're taking the worst over all inputs of size $n$, but imagining a function returns the exact worst case time for any input $n$.

On the other hand, saying that a function is an upper bound just means that we know the function is asymptotically less than that upper bound. So, you can still have an upper bound on the average case analysis (in fact, you usually will).
> 9 votes

---
Tags: algorithm-analysis, landau-notation
---


# Question
Title: Unfeasible linear program becomes feasible if a variable is removed
Apologies, not a computer scientist by trade but I'm playing with linear programming these days.

Let $\\{x\_i\\}$ be $N$ optimization variables with bounds

$$l\_i \leq x\_i \leq u\_i$$

I'm interested in telling if $\exists$ a feasible region under the constraint

$$\sum\_i x\_i = C$$

for a fixed value of $C$.

This is pretty easy (just check that $\sum\_i l\_i \leq C \leq \sum\_i u\_i$). But sometime it happens that while

$$\sum\_i x\_i=C\\,$$

is too constraining,

$$\sum\_{i\notin {\mathcal{S}}} x\_i =C\\, , $$ has a feasible region for some subset of index $\mathcal{S}$.

But at first sight it's hard to tell because there's $N$ variables, such that a brute force check runs in $2^N$.

---

*Examples*: $l\_x=l\_y=10$, $u\_x=u\_y=30$ and $C=15$ is not feasible but it would be feasible if one was to remove either $x$ or $y$ from the problem.

---

Is there some elegant solution to this problem? There's a nice geometrical way of understanding the problem. In the two variable cases, removing either $x$ or $y$ amounts to projecting the region bounded by $\[l\_x, u\_x\],\[l\_y, u\_y\]$ onto $y$ or $x$ axis respectively. Then it's only a matter of asking whether the line $x+y=C$ crosses either of the "projected" regions (which are now lines).

# Answer
> 6 votes
There is (unless $P=NP$) no polynomial time algorithm for this problem, since the problem is $NP$-hard by reduction from Subset Sum. If you set $l\_i=u\_i$ then the problem is to determine if there is a subset of the $u\_i$ that sums to $C$ (which is the Subset Sum problem).

If your problem did not allow $l\_i=u\_i$, if you were to require that $l\_i\<x\_i\<u\_i$, you could get around this by setting $10000\cdot l\_i\<x\_i\<10000\cdot u\_i + 1$ which for sufficiently large values of $10000$ ensures that $x\_i$ will be "close enough".

---
Tags: optimization, linear-programming, linear-algebra
---


title: RSA Encryption & Anonymity

text:
# Question
Title: RSA Encryption & Anonymity
Considering plain RSA encryption, assume we have B who wants to send 10 messages to either A1 or A2. The recipients' public key, namely the exponent e1, e2 and prime product n1, n2 for A1/A2 respectively, is publicly known.

When B sends out, he will either encrypt his messages via $c\_i = (m\_i)^{e\_1} mod (n\_1)$ or $c\_i = (m\_i)^{e\_2} mod (n\_2)$

Let's assume eavesdropper E gets hold of the 10 encrypted messages $c\_i$. Given that she knows e1, e2, n1, n2 - while she can't figure out the messages m themselves, can she figure out whether B sent the messages to A1 or A2, and if so, how?

# Answer
I'll just expand one of the attacks mentioned in D.W.'s comment; this attack seems the most relevant to your question, but other attacks may exist according to the parameters you actually use.

Ideally, an encryption can be viewed as a permutation $\pi\_i$ (determined by $e\_i$), that maps $\\{0,\ldots,n-1\\}$ to itself. If you don't know the two permutations and you don't know the messages $m\_i$, there is no way to tell if you used the permutation $\pi\_1$ or $\pi\_2$ by only seeing a small number of (image only) samples.

Under certain assumptions, RSA is a good encryption. This means you **cannot** decrypt a codeword $c$ and find $m$ such that $m^e=c \mod n$, even if you know $e$. Of course, information-theoretically, knowing $e$ gives you all the information you need to find $m$ from $c$–it fully specifies the permutation. But for a computationally-bounded Eve, we assume this is impossible.

However, if $n\_1 \ne n\_2$, Eve gets a certain advantage in distinguishing ecryptions in the two settings. By definition, $c\_1 \in \\{0,\ldots, n\_1-1\\}$ while $c\_2 \in \\{0, \ldots, n\_2-1\\}$. So if $n\_1$ is very different from $n\_2$ (say, $n\_2\>n\_1$), and Eve is lucky to see $c\_i \in \\{n\_1, \ldots, n\_2-1\\}$, she knows that this message was encrypted using $(e\_2,n\_2)$. Assuming RSA is close to a random permutation, then this has probability of about $1/(n\_2-n\_1)$ per sample.
> 3 votes

---
Tags: encryption
---


# Question
Title: Are these valid counterexamples to proofs for CF languages with Non-CF complements?
Someone asked for examples of context-free languages with non-context-free complements.

The first answer says:

> The language $L\_1= \\{ww \mid w \in \\{a,b\\}^\*\\}$ is not context-free (as can be shown using the pumping lemma; see here). Its complement $L\_2 = \\{a,b\\}^\* \setminus L\_1$ is context-free (as shown here).

Maybe in reality this is true, but given the above information, I am not convinced this is a valid example of such a language. I have proved before that $L$ is not CF, so I have no problem accepting that. However, the CFG and proof given for $L\_2$ are wrong. I can give a really simple counterexample: when the string $s=aaabaa$. Clearly $s \in L\_2$ because it's not of the form $ww$. However, $s$ cannot be constructed using the CFG described for $L\_2$.

Proof: The string $s$ is not of the form $A$ or $B$ since the length of the string is even. Therefore it must be of the form $AB$ or $BA$, but this is impossible because both halves of the string have the same character ($a$) in the center. Therefore $s \notin L\_2$, which is a contradiction.

The second answer says:

> The example you see on Wikipedia: put $A=\\{a^n b^n c^m\\}$, $B=\\{a^m b^n c^n\\}$. It's easy to see $\overline{A}$ and $\overline{B}$ are context-free by defining a PDA; you can note that they're deterministic context-free languages, which is a class closed under complement. Therefore $\overline{A} \cup \overline{B}$ is a context-free language with a non-contextfree complement $A \cap B=\\{a^n b^n c^n\\}$.

This one is even easier to disprove. Sure, deterministic context-free languages are closed under complement, but they're *not* closed under union. Therefore, the language $\overline{A} \cup \overline{B}$ is not necessarily context free.

I am currently still taking Theory of Computing, so perhaps I've gotten something wrong or overlooked some obvious truth. Can anyone disprove my claims? If not, can you provide a valid example of a CF language with a non-CF complement?

# Answer
For the first question, $aaabaa$ is generated by the grammar: $$\begin{align\*} S&\to AB \\ &\to aB &&\text{using }A\to a\\ &\to aaBa &&\text{using }B\to aBa\\ &\to aaaBaa &&\text{using }B\to aBa\\ &\to aaabaa &&\text{using }B\to b\\,. \end{align\*}$$ Your attempt to prove the converse is incorrect because you assume that, when the string is split as $AB$, the part generated by $A$ must have the same length as the part generated by $B$. As the derivation above shows, this is not true.

For the second, you're correct that the class of deterministic CFLs is not closed under union. However, the class of CFLs *is* closed under union. That is, the union of two DCFLs is not necessarily a DCFL but it is definitely a CFL. The argument "$\overline{A}$ and $\overline{B}$ are deterministic context-free, so they are context-free, so $\overline{A}\cup\overline{B}$ is context-free" is implicit in the proof you quote.
> 8 votes

---
Tags: formal-languages, context-free, formal-grammars
---


# Question
Title: Determining if (infinite) binary language DFAs contain at least 1 prime?
This problem has been given by Shallit as an open DFA/ complexity theory problem and is currently not even known to be decidable. It seems to be circulating on the internet in a few places (e.g. \[1\]\[2\]) but not in any papers. Almost nothing seems to be known or published. I am looking for any nontrivial analysis or references.

> Given: binary DFA D. Does L(D) contain at least 1 prime?

(Binary means Σ = {0, 1}.) As an example of something nontrivial about it (a subproblem), what can be said of the base-2 DFA language representations, what is their general form? Or, given any *d,* does there exist a DFA (language) that contains only multiples of *d* in binary? Are there arithmetic progressions embedded in DFA binary languages? Note there are many number theoretic investigations into primes in arithmetic sequences/ progressions and recent findings/ research, could any be demonstrated to be applicable?

\[1\] a simple problem whose decidability is not known / cstheory.SE

\[2\] are there any open problems left about DFAs? / cstheory.SE

# Answer
> 6 votes
It's a standard intro theory exercise that for any $d\ge 0$ there's a FA that accepts all and only those strings in $\\{0, 1\\}^\*$ that are the binary representations of integer multiples of $d$. Thus, the answer to your second question is "yes".

For your third question, the answer is "no". Consider the regular language denoted by $1(10)^\*0$. This language consists of those binary representations of $$ \frac{10\cdot 4^n-4}{3} $$ and clearly this sequence is too sparse to contain an arithmetic subsequence of any length greater than 2.

---
Tags: regular-languages, automata, discrete-mathematics, number-theory
---


title: How to challenge Hutter's algorithm?

text:
# Question
Title: How to challenge Hutter's algorithm?
For a given sufficiently strong formal axiomatic system $\mathsf{F}$ (like $\mathsf{PA}$ or $\mathsf{ZFC}$) and any given function $p^\*(x)$ that can be specified within the formal system $\mathsf{F}$, Hutter's algorithm $M\_{\mathsf{F},p^\*}$ computes the function $p^\*(x)$ nearly as quickly as any (provably quick) algorithm $p$ provably computing $p^\*(x)$. More precisely

> Let $p$ be any algorithm, computing provably the same function as $p^∗$ with computation time provably bounded by the function $t\_p(\xi)$ for all $\xi$. $time\_{t\_p}(x)$ is the time needed to compute the time bound $t\_p(x)$. Then Hutter's algorithm $M\_{\mathsf{F},p^∗}$ computes $p^∗(x)$ in time $$time\_{M\_{\mathsf{F},p^∗}}(x) ≤ 5·t\_p(x)+d\_p·time\_{t\_p}(x)+c\_p$$ with constants $c\_p$ and $d\_p$ depending on $p$ but not on $x$.

Here "provably" means that a proof can be found in $\mathsf{F}$. The algorithm could be interpreted as a generalization and improvement of Levin search, but I wonder whether it is always an improvement.

---

Can we use the formal system $F$ to construct a function $p^\*$ for which Hutter's algorithm $M\_{\mathsf{F},p^\*}$ performs badly? How about asking whether a short proof of $\bot$ (i.e. a contradiction) can be found in $\mathsf{F}$? A short proof would be a proof with fewer than $n$ symbols, and we would use $x$ to encode $n$ in binary form. The function $p^\*$ would just be a brute force search for the contradiction.

I think this should give a problem in $NEXP$, but the optimal algorithm to compute $p^\*$ would have complexity $O(1)$, because the answer is always "no". But $M\_{\mathsf{F},p^\*}$ will take double exponential time in the length of $x$ to arrive at that conclusion, if I'm not mistaken. Now I wonder whether there are more interesting ways to make $M\_{\mathsf{F},p^\*}$ look bad, perhaps similar in spirit to Rice's theorem?

# Answer
> 1 votes
> But $M\_{\mathsf{F},p^\*}$ will take double exponential time in the length of $x$ to arrive at that conclusion, if I'm not mistaken.

That $M\_{\mathsf{F},p^\*}$ will take double exponential time is a conjecture at best. Too see that this conjecture is pretty strong, take any formula $\phi$ that is formally independent of $\mathsf F$, and ask whether a short proof of $\phi$ can be found in $\mathsf F$. Any algorithm that can answer this question quickly (with "no") can also answer the same question for $\phi=\bot$ quickly (with "no"), because any formula can be derived in a single step from $\bot$.

> Now I wonder whether there are more interesting ways to make $M\_{\mathsf{F},p^\*}$ look bad, perhaps similar in spirit to Rice's theorem?

Formal systems are not just bad at proving their own consistency, they are also famously bad at proving some sequence to be random. So we could ask whether a given finite sequence can be reproduced by some program shorter than $m$ symbols taking fewer than $n$ steps. The restriction to fewer than $n$ steps allows us to implement $p^\*$ as a brute force search. If the sequence and $m$ are kept fixed and binary encoding is used for $n$, the resulting problem seems to be in $EXP$. Maybe it's better not to fix the sequence and $m$, because then the problem seems to be in $NEXP$.

What about a function $p^\*$ based on Rice's theorem? No progress yet...

# Answer
> 1 votes
We could do something similar to Squark's question here:

Let $p^\*$ be the program that takes an input $n$ and does the following: "Run $M\_{p^\*}(n)$ for $n$ steps. If it halted, output $|M\_{p\*}(n)| + 1$. Otherwise output $0$."

Now $M\_{p^\*}(n)$ takes at least $n$ steps (proof by contradiction) but $M\_{p^\*}(n)$ can be computed by just printing $0$, which takes $1$ step.

However, in this argument we're implicitly assuming that the formal system Hutter Search uses is consistent. The system itself can't assume that, so it doesn't find the 'proof' that $M\_{p^\*}(n) = 0$ for all $n$.

---
Tags: complexity-theory
---


# Question
Title: Write down at least 20 possible boolean functions of 3 inputs?
I can only write down 16 and cannot go further.

8 of

$f(x\_{1},x\_{2},x\_{3})=0$

000 = 0

001 = 0

010 = 0

110 = 0

111 = 0

110 = 0

101 = 0

011 = 0

and

8 of

$f(x\_{1},x\_{2},x\_{3})=1$

000 = 1

001 = 1

010 = 1

110 = 1

111 = 1

110 = 1

101 = 1

011 = 1

That's the maximum I can go. How do I proceed?

# Answer
There are $2^{2^3}=256$ different boolean functions of 3 inputs.

Here is the truth table for one of the functions.

Every different permutation of column $X$ is a different function. There are a total of 256 permutaions.
> 2 votes

---
Tags: combinatorics
---


# Question
Title: Clarification notation in CLRS runtime analysis
I am learning algorithms from the clrs book. I am having trouble understanding the notation the book has placed.

The book wrote the following:

> $t\_j$ denote the number of times the `while` loop test in line 5 is executed for that value of $j$."

So does that mean $t\_2$ would represent the entire set time the while loop was hit when $j = 2$?

# Answer
> 3 votes
The number of iterations of the `while`-loop depends on `j` which changes during across iterations of the `for`-loop. Thus, the total runtime of lines 5-7 *must* depend on $j$, and the runtime of lines 6-7 *may* depend on $i$ (it does not here).

I can add nothing more over the quote you give; $t\_2$ is the number of times line 5 is reached during the `for`-iteration with $j=2$, indeed.

Our reference question shows you how to obtain such formulae in a structured way. Try to follow the techniques from a blank start and you will see how this comes about.

---
Tags: algorithm-analysis, notation
---


# Question
Title: Does applying a homomorphism to the intersection of two CSLs yield RE languages?
For each language $L \in L(RE)$ there are a homomorphism $h$ and two context-free languages $L\_1$ and $L\_2$ such that $L = h(L\_1 \cap L\_2)$.

I understand that this is because context-free languages are not closed under intersection so $L\_1 \cap L\_2$ will produce non-context-free languages. Since context-sensitive grammars doesn't allow erasing rules which context-free grammars allow to, then the language must be recursively enumerable language. Then recursively enumerable languages are closed under homomorphism.

If $L\_1$ and $L\_2$ are context-sensitive languages, does $L = h(L\_1 \cap L\_2)$ still result in $L \in L(RE)$, as context-sensitive languages do closed under intersection but not morphisms?

# Answer
This follows from closure properties of CSL: it's closed against intersection and $\epsilon$-free homomorphism, but not against (general) homomorphism.

Thus, $h(L\_1 \cap L\_2)$ is always context-sensitive if $h$ is $\epsilon$-free.

If $h$ is not, $h(L\_1 \cap L\_2)$ *may* not be. As an example, take $L\_1$ and $h$ from the proof that CSL is not closed against general homomorphism, and $L\_2 = \Sigma^\*$.

Since CSL $\subseteq$ RE *and* RE is closed against intersection as well as (general) homomorphism, $h(L\_1 \cap L\_2)$ is indeed always in RE.
> 4 votes

---
Tags: formal-languages, closure-properties, semi-decidability, context-sensitive
---


# Question
Title: Generative power and classification of matrix grammars
\[Edited\] I am reading about matrix grammars from several sources and got confused about its generative power and classification to the Chomsky hierarchy.

In here it is stated that:

* A matrix grammar is a quintuple $G = (N, T, M, S, F)$, where $N,T$, and $S$ are specified as for a context-free grammar, $M = \\{m\_1, m\_2, \dots m\_n \\}$ is a finite set of finite sequences of context free rules (i.e. for $1 \leq m\_1 \leq n$, $m\_i = (A\_{i,1} \rightarrow w\_{i,1}, A\_{i,2} \rightarrow w\_{i,2}, \dots A\_{i,r\_i} \rightarrow w\_{i,r\_i})$ for some $r\_i \geq 1$, $A\_{i,j} \in N$, $w\_{i,j} \in (N \cup T)\*$, and $1 \leq j \leq r\_i$) and $F$ is a subset occurring in the matrices $m\_i$
* $L(MAT)$ denotes the set of all languages that can be generated by matrix grammars -
* **Theorem** $L(MAT) = L(RE)$
* **Theorem** For each recursively enumerable language $L$, there is a matrix grammar $G$ in normal form such that $L (G) = L$.

While although this paper is about simple matrix grammars, it also states a definition of matrix grammars (not simple matrix grammars) that is a bit different with the above definition. It is stated that

* A matrix grammar (MG for short) is a pair $H = (G, M)$ where $G = (N,T,P,S)$ is a context-free grammar; $M$ is a finite language over the alphabet of rules $(M \subseteq P^\*)$. For $x, y \in (N \cup T)^\*, m \in M$, $x \Rightarrow y\[m\]$ in $H$, if and only if there are $x\_0, x\_1,\dots, x\_n$ such that $x\_0 = x, x\_n = y$, and $x\_0 \Rightarrow x\_1\[p\_1\] \Rightarrow x\_2\[p\_2\]) \Rightarrow \dots \Rightarrow x\_n\[p\_n\]$ in $G$, and $m = p\_1 p\_2 \dots p\_n$, where $p\_i \in P, 1 \leq i \leq n$, for some $n \geq 1$.
* Let $MT$ denotes the family of languages that is generated by matrix grammars
* $CF \subset MT \subset CS$

*Question.* How come when matrix grammars can generate recursively enumerable languages but it is still classified as a proper subset of the family of context-sensitive languages? Perhaps because they are different matrix grammars? I also read about it in this book but it is too complicated for me.

*Additional Question.* If a grammars $G$ can generate some context-sensitive languages (let's say that the family of languages generated as $XG$ ), is it still possible that the family of languages is going to be classified as a proper subset (strict inclusion) of $CS$, i.e. $XG \subset CS$?

# Answer
> 3 votes
Isn't the difference because matrix grammars exist with and without appearance checking? In the usual notation $\mathrm{MAT} \subset \mathrm{MAT}\_\mathrm{ac} = \mathrm{RE}$.

A matrix grammar basically is a grammar with so-called matrices, lists of context-free type of productions $(A\_1\to x\_1, \dots, A\_k\to x\_k)$. There are two main variants of how to apply productions in matrix grammars. Either a matrix is applicable if all its productions can be applied in the given order. This is the less powerful variant, although we can generate $\\{ a^nb^n c^n \mid n\ge 1\\}$ that way.

Alternatively in a more powerful version some of the productions in a matrix may be marked as skipping productions. If the left-hand nonterminal in such production is present in the string it must be applied, when it is not present the production can be skipped. It is called *appearance checking*, and turns out to be a very powerful feature.

(added) In your new explicit definition of matrix grammars the set $F$ of occurrences of productions in the matrices are in fact the productions that can be skipped whenever the left side is not present (normally they would block the application of the matrix). So, when $F\neq\varnothing $ your model has appearance checking. Your first reference indeed has this feature, but does not mention it explicitly by name.

---
Tags: formal-languages, formal-grammars, computation-models
---


# Question
Title: If $n^{\log n}$ is not polynomial or exponential, then what this function is called?
I just found this sentence on page 6 of Garey and Johnson's "Computers and Intractability".

> Any algorithm whose time complexity function cannot be so bounded is called an exponential time algorithm (although it should be noted that this definition includes certain non-polynomial time complexity functions, like $n^{\log n}$, which are not normally regarded as exponential functions).

My question as following,

If $n^{\log n}$ is not polynomial nor exponential, then what this function is called? Does this have a name or special cases or not?

Thank you.

# Answer
> 13 votes
There is no fixed terminology for these types of functions. You might sometimes see "subexponential" or "superpolynomial" used to refer to this kind of behavior.

---
Tags: algorithms, terminology, polynomial-time
---


# Question
Title: Operating Systems TestAndSet instruction
I was reading operating systems concurrency control topics where I came across `TestAndSet()` intruction. I first referred this book. But it has got very less coverage on `TestAndSet` and then I googled. Obviously I came across wiki page.

The wikipedia page gives two code excerpts.

**The TestAndSet() function**

```
#define LOCKED 1

int TestAndSet(int* lockPtr)
{
   int oldValue;
   oldValue = *lockPtr;
   *lockPtr = LOCKED;
   return oldValue;
}

```

**Lock() built using TestAndSet()**

```
function Lock(boolean *lock)
{
   while (test_and_set(lock) == 1);
}

```

I have two doubts:

* It seems that the `TestAndSet()` does not actually have test, it does contain only set part and `Lock()` contains the set part. Is it like that?
* Below first excerpt, wikipedia page days:

> The code also shows that TestAndSet is really two operations: an atomic read-modify-write and a test. Only the read-modify-write needs to be atomic. (This is true because delaying the value comparison itself by any amount of time will not change the result of the test, once the value to test has been obtained. Once the code writes the initial value, the result of the test has been determined, even if it has not been computed yet)

Does that mean we can call `TestAnsSet()` inside `Lock()`, save its return value and test against that return value anytime inside `Lock()`?

# Answer
You are right, `TestAndSet` doesn't test the value of the flag, it merely sets it, but returns the previous value, which must be tested elsewhere.

The trick is that as the assignment is atomic, only one process can cause a transition from 0 to 1 (others only cause a "transition" from 1 to 1), and only it can pass the while.
> 3 votes

---
Tags: operating-systems, concurrency, memory-management
---


# Question
Title: Where does entanglement fit into quantum computing?
I've been reading up on quantum computing online from various sources, including this link http://twistedoakstudios.com/blog/Post2644\_grovers-quantum-search-algorithm.

I get how quantum gates work, destructive interference, and how you can simulate a quantum computer using matrix math and complex numbers.

Does entanglement have a use in quantum computing? I haven't yet seen anything explicitly talk about entanglement and whether it's used in QC, but I feel like it's possible it might be implicitly stated and I could be missing it - or maybe not!

Thanks!

# Answer
The entanglement of quantum particles is, implicitly or explicitly, the reason why quantum computing is so fast. You will know by now that a qubit (implemented for example as a photon's polarization) can be represented as a unit vector of two complex numbers, and that it may be manipulated by a 2-by-2 matrix of complex numbers. If you have two quantum systems described by their respective state vectors $|a\rangle$ and $|b\rangle$, which describe the two systems in isolation, their composite state is described by the tensor product of these two vectors: $|a\rangle \otimes |b\rangle$. If you operate on $|a\rangle$ with matrix $U$, you get the composite state $(U|a\rangle) \otimes |b\rangle$, and so forth.

Entanglement comes when you operate on this composite state and bring it to a state which cannot emerge as the tensor product of two state vectors. For example, the state $\frac{1}{\sqrt{2}}(|00\rangle + |11\rangle)$ is not the tensor product of any two vectors (verify this as an excercise). In such states, measuring qubit $|a\rangle$ has an effect on $|b\rangle$. For example, if you performed a partial measurement (that is, a measurement of ostensibly only one qubit) on the most significant bit of $\frac{1}{\sqrt{2}}(|00\rangle+|11\rangle)$, and you measured it to be $0$, then measuring the least significant bit will yield $0$ with certainty, too, and vice versa.

A good first example for studying entanglement is Deutsch' problem, where the algorithm goes from $(|0\rangle+|1\rangle) \otimes (|0\rangle - |1\rangle)$, a state which can be expressed as the tensor product, to a state which can no longer be expressed as any tensor product, using an operator which cannot be expressed as the tensor product of two operators.
> 4 votes

---
Tags: quantum-computing
---


# Question
Title: Testing two DFAs generate the same language by trying all strings upto a certain length
Given the language

$EQ\_{\mathrm{dfa}} =$ $\\{\langle A, B\rangle\mid A$ and $B$ are two DFAs and $L(A) = L(B)$ $\\}$

Prove that $EQ\_{\mathrm{dfa}}$ is decidable by testing the two DFAs on all strings upto a certain size. Calculate a size that works.

(This is from Sipser chapter 4)

I make a directed graph as usual but if two transitions $\delta(q\_1, c\_1) = q\_2$ and $\delta(q\_1, c\_2) = q\_2$ then the graph I am making will just have one edge for these two characters. My idea is to walk the directed graph in a way so that every transition is traversed, but when I walk over an edge forming a cycle, I would need to traverse the edges I have previously walked through in the cycle once again. Do this for both the DFAs and choose the greater number of edges traversed. Then enumerate through all the strings of this length (from the given alphabet) and the two DFAs are equal only if they accept and reject on the same strings.

I could probably write some pseudocode, but I'm not sure if this is the correct way to approach the problem even.

# Answer
> 7 votes
It can be tested that way, provided we may use the number of states of both automata $A$ and $B$ to compute the bound.

Note that if a finite automaton $C$ has $n$ states then *any* state in $C$ is reachable by a string of at most $n-1$ letters, or that state is not reachable at all. Assume I want to check whether $L(C)=\Sigma^\*$. If $C$ is deterministic then all reachable states must be accepting. This can be tested by checking that all strings up to length $n-1$ are in the language.

The check $L(A)=L(B)$ can be analyzed similarly by considering the product automaton, i.e., the automaton that simulates $A$ and $B$ in parallel.

The product construction needs a little twist. Rather than accepting if both automata accept (computing the intersection) you need to see whether both automata make the same yes/no decision. Thus accept when both components are accepting **or** when both components are not accepting. Thus the language is $(L(A)\cap L(B))\cup (L(A)^c\cap L(B)^c)$. If that language is $\Sigma^\*$ then both automata are equivalent.

# Answer
> 1 votes
By the (proof of the) pumping lemma, you'll need to check only strings of length up to the number of states of the DFA, probably the larger one. Would need to think it through, but I'm intrinsecally lazy.

# Answer
> -2 votes
This seems an unusual method of attempting to determine equivalence of the languages of two DFAs and obviously will never do so if the languages are infinite.

It is possible to impose a 'normal form' on DFAs by minimising and sorting transitions: equivalence can then be determined even in the infinite case.

---
Tags: automata, undecidability
---


# Question
Title: Can context-free grammar generate $a^{2^n}$?
Context-free grammar can generate the string a 2 n for n≥0 .

The production rule P is S→SS|a .

The derivations is, for example:

1) S⇒a (this is when n = 0)

2) S⇒SS⇒aa (this is when n = 1)

3) S⇒SS⇒SSSS⇒aaaa (this is when n = 2)

4) S⇒SS⇒SSSS⇒SSSSSSSS⇒aaaaaaaa (this is when n = 3).

Am I right?

Someone told me yes but it takes a very long time for big enough n;

someone told me no - that this grammar actually generates $a^+$ because it can be $S \Rightarrow SS \Rightarrow SSS \Rightarrow aaa$.

So, does this mean context-free grammar cannot generate the string $a^{2^n}$?

Is there exist any other context-free grammars that can generate this language?

# Answer
It is well known (and not very difficult to prove) that a context-free language over a unary alphabet $\\{a\\}$ is regular.

Thus, your question is essentially, "is $\\{a^{2^n}:n\in \mathbb N\\}$ regular?" And the answer to that is no (easy to prove using the pumping lemma).
> 5 votes

# Answer
I just realize that my question is the duplicate of this question, but I'll try to put additional answer here myself, now knowing that $a^{2^n}$ is a context-sensitive language, not a context-free language.

An example of the production rules to generate $a^{2^n}, n \geq 0$:

$S \rightarrow \lambda |AA$

$A \rightarrow AA$

Until the above part, it's okay with context-free grammar rules (the derivation being beautifully $S \Rightarrow AA \Rightarrow A^{2^2} \Rightarrow A^{2^3} \Rightarrow \dots$), but then how to change the non-terminal symbols $A$ to the terminal symbols $a$ is tricky. We cannot simply apply $A \rightarrow a$ because it can affect the numbers for example $S \Rightarrow AA \Rightarrow aAA \Rightarrow aaa$, which is not $a^{2^n}$.

This is where the context-sensitive grammar rule comes in handy, simply change both $AA$ to terminal symbols thus preserve the number of $a$'s generated as $a^{2^n}$, i.e.

$AA \rightarrow aa$.

The need to apply this rule is why this language is not a context-free language.
> -1 votes

---
Tags: formal-languages, context-free, formal-grammars
---


# Question
Title: How to show that the set of TMs that accept languages of size two is recognizable?
I know how to show $\overline{Lx}$ is unrecognizable. I know how to show Lx is undecidable.

I would like the mapping reduction function that shows that Lx is recognizable or unrecognizable.

For instance, to show $\overline{Lx}$ is unrecognizable, show $\overline{Htm}$ \<= $\overline{Lx}$

Given $\overline{Htm}$ = {M description: M is a TM and M loops on ''}

```
def R(<M>):
    def N(x):
        M('')
        if x == 0 or x == 1 then accept
    return <N>

```

> If M is in $\overline{Htm}$ then M loops then N will not accept any strings then |L(N)| = 0 then N is in $\overline{Lx}$
>
> if M is not in $\overline{Htm}$ then M halts then N will accept either 0 or 1 so |L(N)| = 2 then N is not in $\overline{Lx}$

I would like a similar proof to show that Lx is either recognizable or unrecognizable.

# Answer
Based on RanG. answer in comments.

To show ${Lx}$ is unrecognizable, show $\overline{Htm}$ \<= ${Lx}$

Given $\overline{Htm}$ = {M description: M is a TM and M loops on ''}

```
def R(<M>):
    def N(x):
        if x == 0 or x == 1 then accept
        M('')
        return accept
    return <N>

```

> If M is in $\overline{Htm}$ then M loops then N will accept either 0 or 1 then |L(N)| = 2 then N is in ${Lx}$
>
> if M is not in $\overline{Htm}$ then M halts then N will accept all x so |L(N)| = $\infty$ then N is not in ${Lx}$
> 1 votes

---
Tags: computability, turing-machines, semi-decidability
---


# Question
Title: Algorithm for grid with obstacles and movement restriction
We are given an $n \times n$ grid with some of the squares darkened.

Our goal is to move from the bottom-left to the top-right corner with the following constraints:

1) We cannot step on a darkened square.

2) Each move must be up or to the right.

3) We cannot move in the same direction consecutively four times.

Design an algorithm that runs in $O(n^2)$ time and outputs the set of all squares that can be reached from the bottom-left corner.

My thoughts: We can convert the grid to a graph in $O(n^2)$: each square (darkened or not) becomes a node, and adjacent squares correspond to edges; each edge is directed either rightwards or upwards. We can then remove the nodes that correspond to darkened squares. At this point, we can BFS or DFS from the top-left node, but we must keep track of condition 3 somehow, with some sort of "cost" array.

Another idea is to "chop off" (this can be formalized) a triangle from the upper left and lower right, which are "too high" and "too right" respectively. But then, the existence of the darkened squares causes some additional squares to be unreachable.

Any help would be appreciated.

# Answer
You can depict states of the graph as following: (grid\_position,|consecutive\_left|,|consecutive\_up|) if you are at state (\[2,3\],3,0) then you have no other option but to go up to (\[3,3\],0,1)

so you have n^2 * 4 * 4=16\*n^2 states=O(n^2) states. And you can also save some space by noticing that states such as (\[x,y\],2,1) are impossible.
> 2 votes

# Answer
Here's a version that's slightly more efficient than jjohn's answer, though only by constant factors.

The idea is that, instead of two kinds of move (up and right) with the annoying restriction that we can't move the same way four times consecutively, we'll have six kinds of move (up one, up two, up three, right one, right two, right three) and the restriction that moving up must be followed by moving right, and vice-versa. That means, you're forbidden from moving up one, then up one again but that's OK because you could have just moved up two as a single move.

To implement this, the state space is the set of triples $(x,y,d)$, where $(x,y)$ is the co-ordinates in the grid and $d\in\\{\uparrow,\rightarrow\\}$ is the direction of the previous move. We'll adopt the convention that the "previous move" from the initial position was $\uparrow$. The potential edges are as follows:

* from $(1,1,\uparrow)$ to $(1,i,\uparrow)$ and $(i,1,\rightarrow)$ for each $i\in\\{2,3,4\\}$;
* from $(x,y,\uparrow)$ to $(x+i,y,\rightarrow)$ for each $i\in\\{1,2,3\\}$;
* from $(x,y,\rightarrow)$ to $(x,y+i,\uparrow)$ for each $i\in\\{1,2,3\\}$.

From this set of potential edges, delete any edge that starts at, ends at or "jumps over" a forbidden square and, of course, any edge that would take you off the board ($x\>n$ or $y\>n$). So far, our two goal states are $(n,n,\uparrow)$ and $(n,n,\rightarrow)$. Life would be very slightly easier if we only had one goal state, so redirect any edge that points to $(n,n,\rightarrow)$ so it points to $(n,n,\uparrow)$ instead.

Now, use your favourite $s$–$t$ connectivity algorithm to find if there's a path from $(1,1,\uparrow)$ to $(n,n,\uparrow)$. All of this can be done in quadratic time, since the only expensive part is building the graph.

If you care, you can be much more space-efficient by building the graph on the fly. Savitch's theorem says that you can solve $s$–$t$ connectivity on a graph with $n^2$ vertices in space $O((\log n^2)^2) = O((\log n)^2)$.
> 2 votes

---
Tags: algorithms, graphs, graph-traversal
---


# Question
Title: What is the relation between pure mathematics, applied mathematics and Cellular Automata?
I was reading about pure mathematics and I am wondering if there is a relation between it and Cellular Automata.

> Broadly speaking, pure mathematics is mathematics that studies entirely abstract concepts.

For example, elementary cellular automata transforms an input of {3 cells} based on a rule set to a fractal like rule 90, how this will be described in pure mathematics perspective?

Another fractal like Pascal's Triangle can determine the coefficients that arise in binomial expansions, how it can be related to applied mathematics?

> Applied mathematics is a branch of mathematics that deals with mathematical methods that find use in science, engineering, business, computer science, and industry.

The use here of Pascal's triangle is determining the coefficients of binomial expansion, so how it can be related to applied mathematics?

# Answer
> 2 votes
The definitions given in Wikipedia are trying to convey a very abstract concept by means of examples, which, to my taste, isn't satisfactory.

Thus, before answering this question we'd need to ask ourselves why are there two in the first place. And if there is a real need for two, then:

> How is mathematics (both pure and applied) possible? -- *Immanuel Kant*

# History

The answer to the first question appears to be very involved. In European tradition, the question goes back to Plato's distinction between the ideal and the concrete. These roughly translate into *analytic* and *synthetic* in modern philosophical language. Plato ultimately believed that mathematics is discovered rather than constructed, but this still puts mathematics in the realm of ideal due to Plato believing that only the ideal actually exists, and that the concrete is but an imperfect reflection of the ideal. This was in stark contrast to the existing tradition of viewing mathematics as a practical skill of measuring and counting.

Since that time on, multiple attempts were made to either unify both, or to define one in terms of the other, or to completely dismiss one of the two. Ultimately, in the beginning of the 20'th century the argument boiled down to the ability of defining the classical mathematics. This split the philosophy of mathematics into logicism (with Frege as its forerunner), formalism (with Hilbert as its advocate) and psychologism (intutionism), the idea advanced by Brouwer. Somewhat under-represented here are the universalist views held by Klein (no good online quotes, sorry). The later is the view that synthetic and analytic truth are the same, and that when a seeming contradiction arises, it is probably because we either don't have a proper observation technique, or that we don't have a proper mathematical explanation for the observation.

# The Problem

It all boils down to the question of what is truth, and are there different kinds of truths? I will first give an example of the problem and then discuss it.

Stating that

$$ \textit{bachelors are males} $$

Imposes a restriction that the interpretation of "bachelors" must be a subset of the interpretation of "males", but this restriction doesn't result from logical construction of the sentence, rather it is our experience (and the reasoning non-included in this sentence) that all bachelors we've seen so far, and are likely to meet in the future will be male. This is an example of synthetic truth. While in this example it may look like it could be possible to resolve the problem by adding more logical predicates, the problem is in fact unresolved as of now. More generally, this can be seen as the disparity between material implication and "real" implication.

Using material implication, typically denoted as $\implies$ we can obtain:

$$ \textit{water is wet} \implies \textit{sky is blue} $$

And while the sentence is true in a pure logical sense. From the perspective of non-logical, or extra-logical reasoning it is false, since the perceived properties of water have no immediate impact on the perceived color of the sky.

Lewis was, perhaps, the first to notice and try to address this general problem by creating more restricting logical systems. Another way to approach this problem, and the stance taken by many contemporary philosophers is laid out in Two Dogmas by Quine. To quote the later:

> Physical objects, small and large, are not the only posits. Forces are another example; and indeed we are told nowadays that the boundary between energy and matter is obsolete. Moreover, the abstract entities which are the substance of mathematics -- ultimately classes and classes of classes and so on up -- are another posit in the same spirit. Epistemologically these are myths on the same footing with physical objects and gods, neither better nor worse except for differences in the degree to which they expedite our dealings with sense experiences.

Put simpler: "pure" mathematics is just a convenience, a make-believe thing that doesn't have any factual content and has no bearings on what truth is. Surprising as it may sound, we still use the terminology in its pre-Quinean sense.

# Finally

When forced to define abstract and applied mathematics, I'd say that:

1. **Applied mathematics** is pure mathematics restricted to the synthetic truth. I.e. the kind of mathematics that can be verified by experimentation.
2. **Pure mathematics** is the art of discovery of patterns. The parallel between art and mathematics is not new, and, in fact, Hardy, the iconic pure mathematician holds that:

> I am interested in mathematics only as a creative art.

# Your question

So, having dealt with preliminaries :) to answer your question!

1. Pure mathematics can find more than one interesting aspect of cellular automata to study. There are so-called "free objects" in mathematics - those possess only one interesting property which defines them. CA isn't one of those. It is a whole area of research, so any example of its treatment in pure mathematics will not be exhaustive. One such (non-exhaustive!) example is to represent this particular CA as a function in domains being CA's input and output, and study the function's behavior in the usual way (answering questions about totality, bijection etc.)
2. Pascal's triangle can be a subject of applied mathematics as you can easily build a physical model for it and convince yourself of the calculation that you do by means of counting the elements of the model. Since, at least from my perspective, applied mathematics is the restricted version of pure mathematics, this means that regardless of your ability to build a physical model, this is still valid pure mathematics.

# PS

The views expressed above are certainly biased and don't represent the absolute majority of the people involved in this field. You would benefit a lot from reading literature dealing with subject matter.

---
Tags: cellular-automata
---


# Question
Title: 'Quick' way to show non-regularity of languages that are 'close' to other non-regular langauges
Take the language $L = \\{a b^n c^n \\; : \\; n \geq 0\\}$.

It's obvious that $L$ is non-regular because $\\{b^n c^n \\; : \\; n \geq 0\\}$ is non-regular, but I don't know a satisfying way to show that to the hypothetical Devil's advocate reading my proof without dragging out a full argument using the pumping lemma.

Is there some property of languages that can allow us to easily deduce that $L$ is non-regular if its accepted as known that $\\{b^n c^n \\; : \\; n \geq 0\\}$ is non-regular?

# Answer
It is known that regular languages are closed under homomorphisms. In particular, if $L$ were regular than so would $h(L) = \\{b^nc^n : n \geq 0\\}$ be, where $h$ is the homomorphism given by $h(a) = \epsilon$, $h(b) = b$, $h(c) = c$. Since $h(L)$ is not regular, so is $L$ non-regular.

More generally, you can use proof by contradiction together with operations under which regular languages are closed. The idea is to start with your language, perform a bunch of operations, and end up with a non-regular language. If all operations you used preserve regularity, then you can conclude that the original language is not regular.
> 3 votes

---
Tags: formal-languages, pumping-lemma
---


# Question
Title: What is the best you can do with a noisy message?
You play a TV game in which you have to open one door out of $n$. Behind each door, there is a treasure with probability 1/2, independent of the other doors, so your apriori chance of winning is 1/2.

In order to increase your chances, you can coordinate with a friend. You do the coordination before the game starts. Then, the friend can see what's behind all the doors, and send you a single integer number between 1 and $n$.

You receive your friend's number, *but*, in addition to that number, you receive $k-1$ more numbers between 1 and $n$, which are selected at random without replacement between 1 and $n$. You don't know which of the $k$ numbers is the real message and which is fake.

What strategy can you and your friend can coordinate, such that your probability of finding a treasure is maximized?

EXAMPLE: suppose $k=2$. Then, one possible strategy is that the friend just selects a door with a treasure behind it, and sends its number to you. You receive your friend's number and another number, in random order. Suppose you just pick the first number that you receive and open the door with that number. If it is your friend's number then you win; if this is a fake number then you have a chance of 1/2 to win. Hence, your total chance of winning with this strategy is 3/4. Is this correct? Is there a better strategy?

# Answer
> 7 votes
Suppose that $k \ll n$. In that case, your friend can send you the index of the first door containing a treasure. Of the $k$ numbers you get, you pick the smallest one. If $k$ is small enough compared to $n$, then it is very likely that the smallest of the $k$ numbers is the one that your friend sent you.

More concretely, suppose that $k$ is constant. With probability $1-1/n$, the number that your friend sends you is at most $\log n$. The probability that the other $k-1$ numbers are more than $\log n$ is $(1-\log n/n)^{k-1} \approx 1-k\log n/n$. We conclude that this strategy fails with probability at most roughly $1/n + k\log n/n$, which tends to $0$ as $n \to \infty$.

To determine how small $k$ should be, let us be a bit more careful. Denote by $m$ the number that your friend sends you; the distribution of $m$ is geometric (we ignore for now the event in which there are no treasures at all), and so $\Pr\[m\] = 2^{-m}$. The probability that one of the other $k-1$ numbers is smaller than $m$ is $1-(1-(m-1)/n)^{k-1}$. Overall, this strategy fails with probability $$ \frac{1}{2^n} + \sum\_{m=1}^n 2^{-m} \left(1 - \left(1 - \frac{m-1}{n}\right)^{k-1}\right) = 1 - \sum\_{m=1}^n 2^{-m} \left(1 - \frac{m-1}{n}\right)^{k-1}. $$ We can non-rigorously estimate this as $$ 1 - \sum\_{m=1}^\infty 2^{-m}e^{-(m-1)k/n} = 1 - \frac{1}{2-e^{-k/n}} = \frac{1-e^{-k/n}}{2-e^{-k/n}} \approx \frac{k}{n}. $$ This suggests that if $k = o(n)$ then you win with probability $1-o(1)$.

---
Tags: probability-theory, probabilistic-algorithms, communication-protocols
---


# Question
Title: Context-free grammar for $L = \{a^{2^k}, k \in\mathbb{N}\}$
In an exercise, I am asked to find a context free grammar for language $L = \\{a^{2^k}, k \in \mathbb{N}\\}$.

I have been trying to use a "doubling" variable. If $a^{2n} \in L, n\in\mathbb{N}$ then use this variable to double the $a$'s that have been produced by the other language rules.

Is this thinking valid? So far I haven't been able to get anywhere with it, but it seems logical given the double-stack of powers.

# Answer
$L = \\{a^{2^k}, k \in \mathbb{N}\\}$ is not a context-free language according to Pumping lemma for context-free languages.

Suppose $L$ is context-free. The pumping lemma says there exists some integer $p \ge 1$ such that every string $s$ in $L$ where $|s| \ge p$ can be written as $s=uvwxy$ where $|vwx|\le p$, $|vx|\ge 1$ and $uv^nwx^ny$ is in $L$ for all $n \ge 0$.

Let $s$ be a string in $L$ longer than $p$, and $u$, $v$, $w$, $x$, and $y$ have the properties given by the pumping lemma. Thus $uwy, uvwxy, uv^2wx^2y\in L$. Let $a$ and $b$ be such that $$|uwy|=2^a, |uvwxy|=2^b$$ Note $b\>a$. Then $$|uv^2wx^2y|=2|uvwxy|-|uwy| = 2^{b+1}-2^a = 2^a(2^{b+1-a}-1)$$ But $2^a(2^{b+1-a}-1)$ is not a power of 2, and so $uv^2wx^2y\notin L$.
> 11 votes

# Answer
Your approach does not work: you can't force all the variables to "double" at once using only context-free rules.

As the other answers show, your effort is futile: $L$ is not context-free, so there can be no such grammar.

For reference, context-*sensitive* rules allow you to control the "doubling". Idea: move markers through the sentence; only with the marker can doubling rules be applied. A second marker triggers termination.

Try for yourself to translate this idea into a grammar!

---

No luck? here goes:

> $\qquad\begin{align\*} S &\to \\$ A \\$ \\ \\$ A &\to \\$ \bullet A \mid \circ A \\\\[1ex\] \bullet A &\to AA \bullet \\ \bullet \\$ &\to \\$ \\\\[1ex\] \circ A &\to a \circ \\ \circ \\$ &\to \varepsilon\end{align\*}$

Note:

* The first rule sets up end markers.
* The second rule(s) spawn the two markers; only one $\circ$ can be spawned!
* Markers can only move to the right, and are absorbed by the last end marker.
* Markers can not overtake each other.

I'll leave a formal proof of correctness as an exercise; see here for some ideas.

> *Hint:* Each marker is a "phase"; you have $k-1$ $\bullet$-phases that generate $A^{2^k}$, then a single $\circ$-phase that translates all $a$ into $A$.
> 11 votes

# Answer
A language which is a subset of $a^\*$ is known as a *unary language*. There is a complete classification of unary languages which are context-free. In particular, if $L$ is a unary language then the following are equivalent:

1. $L$ is context-free.
2. $L$ is regular.
3. There exists $m$ such that $a^n \in L$ iff $a^{n+m} \in L$.
4. There exist $m\_1,m\_2$ and subsets $S\_1 \subseteq \[m\_1\],S\_2 \subseteq \[m\_2\]$ such that $a^n \in L$ iff $n \in S\_1$ or $n-m\_1-rm\_2 \in S\_2$ for some integer $r \geq 0$.
> 6 votes

---
Tags: context-free, formal-grammars, computational-linguistics
---