# Question
Title: When do we need to change the state of a push down automata?
I'm new to the subject of automata theory. I get most of the stuff, but I cannot figure out when to change the state of the machine, and when to keep the state unchanged for a particular transition operation. An explanation would be appreciated. Thanks!

Also, my understanding of states is that they're basically the indicators in the machine, which let it know which operation is going on. Is this the correct analogy? If not, can you give a better one?

**Edit**: Regarding finite automata, I can understand when to change the state. But I'm confused in push down automata. Do you change the state only during push and pop, and during introduction of a new character? Or are there more reasons to change the state?

# Answer
> 2 votes
As Renato suggests, you never *need* to change state in a PDA. Even without useing a CFG as an intermediate, we can take a PDA and construct another that does the same job with using only a single state (a proof can be found here). The basic trick is to use the tape alphabet to encode the state of the original machine (and part of the transition). This works perfectly well for both deterministic and non-deterministic PDAs.

This is a little unsatisfying however, as a single state machine with a huge tape alphabet is not a particularly natural way to design a PDA (at least if you're like most humans I have met, there might be someone who thinks that way, if so, well done\[!|?\]). One intuitive reason to change state is as you suggest, because the machine is meant to be doing something different. Analogously to how we would talk about what we as humans are doing, for example, when we're working. We might break a task into steps, and perform them in a "sensible" sequence. The idea is the same with designing PDAs, break the recognition task into a series of steps, and change state when you move from one step to another.

As an example, consider the canonical non-regular context free language $\\{a^{n}b^{n}\mid n\in\mathbb{N}\\}$. In processing this language, we might have a starting state, a state for processing $a$s, a state for processing $b$s and an accept state. We move from the start state to the "$a$" state by pushing a botoom-of-the-stack symbol, then process the $a$s (probably by pushing a symbol for each $a$), then move to the "$b$" state using a $\varepsilon$-transistion, process the $b$s (popping off the symbols we put on for the $a$s), then move to the accept state if we have reached the end of the input and can see the bottom-of-the-stack symbol.

This is not the only way to build a PDA for this language, but the changing of states has a natural, intuitive meaning that is useful to us as humans in the design process (and for others trying to understand or implement it).

Unfortunately there's no simple "this is when to change states" rule. As the single state example shows, you can design things in a very arcane, incomprehensible manner, but they are still correct. Like a number of things in maths, CS and programming, you really have to just practice it a bit, look at other solutions and develop your own intuition. It is in many ways like programming (funnily enough) - there's lots of ways to solve a problem, only some are good ways, but there is at best only general guidelines to what to do when and where.

# Answer
> 0 votes
This is a tricky question because we know that a CFL is generated by at least one CFG. Exist an algorithm to generate a PDA(accepts by empty stack) from a CFG. This PDA has only one state $q\_0$ and the transitions are:

$\forall a \in \Sigma: \delta(q\_0,a,a)=\\{(q\_0,\epsilon)\\}$

$\forall A \in N: (q\_0,\alpha)\in \delta(q\_0,\epsilon,A)$

Where $\alpha$ is the right side of a production rule of $A$(expanding non-terminal in the stack). So, answering your question I would say that from this perspective at least it is not necessary to change state of a PDA.

---
Tags: automata, pushdown-automata
---


# Question
Title: Finding A String Using A Suffix Array/Table
Is it possible to find out a string only having its corresponding suffix array/table and knowing that the string contains only, for instance, letters "f", "g", "r"? If so, how is that possible?

# Answer
> 1 votes
Sure: the longest stored suffix is the string itself.

In a suffix array, it's particularly easy to find: scan the array for starting index $1$ -- the suffix starting at the first character is, quite obviously, the string itself.

# Answer
> 1 votes
Understanding the definition of a *suffix array* will come in handy here.

http://en.wikipedia.org/wiki/Suffix\_array

**Suffix Array for the string attcatg$.**

So like Raphael Suggested either look for the **index 1 string attcatg$** or look for the longest string in that array which is the same if it doesn't store indices but it should store indices as per definition.

---
Tags: data-structures, strings, suffix-array
---


# Question
Title: Best pathfinding algorithm for undirected unweighted graph
I have an unweighted undirected graph with every node connected with an average of two hundred other nodes (nodes are people from social network). What will be the fastest algorithm to find the shortest path from one node to another?

# Answer
> 1 votes
assuming you don't have any heuristic function about the distance to the target, a good solution that is valid is bi-directional BFS:
**Algorithm idea:** do a BFS search simultaneously from the source and the target: \[BFS until depth 1 in both, until depth 2 in both, ....\].
The algorithm will end when you find a vertex v, which is in both BFS's front.

**Algorithm behavior**: The vertex v that terminates the algorithm's run will be exactly in the middle between the source and the target.
This algorithm will yield much better result in most cases then BFS from the source \[explanation why it is better then BFS follows\], and will surely provide an answer, if one exist.

**why is it better then BFS from the source?**
assume the distance between source to target is `k`, and the branch factor is `B` \[every vertex has B edges\].
BFS will open: `1 + B + B^2 + ... + B^k` vertices.
bi-directional BFS will open: `2 + 2B + 2B^2 + 2B^3 + .. + 2B^(k/2)` vertices.

for large B and k, the second is obviously much better than the first.

NOTE, that this solution does NOT require storing the whole graph in memory, it only requires implementing a function: `successor(v)` which returns all the successors of a vertex \[all vertices you can get to, within 1 step from v\]. With this, only the nodes you open \[`2 + 2B + ... + 2B^(k/2)` as explained above\] should be stored. To further save memory, you can use Iterative Deepening DFS from one direction, instead of BFS, but it will consume more time.

---

In your case, the difference between BFS and bi-directional BFS, assuming 6 degrees of seperation is between developing ~`200^6 = 2.4e13` nodes, and `2*200^3=16,000,000`. As you can see, bi-directional BFS needs much less nodes to be developed than the alternative.

---

**Disclaimer:** Most of this answer (except the last part) is copied from my answer on StackOverflow.com, as suggested in meta (and effectively applied by a mod in security.SE)

---
Tags: algorithms, graphs, shortest-path
---


# Question
Title: Proving that f(N) = N lg N + O(N) implies f(N) = Θ(NlogN)
How do you prove the following?

$$f(N)=N\space lg\space N + O(N) \implies f(N) = \Theta(N \space log \space N)$$

Here $lg\space N \equiv log\_2\space N$, and $O$ stands for the big-O, and $\Theta$ stands for big-theta. And $log \space N \equiv log\_e \space N$, i.e. natural logarithm

My reasoning may not be all that mathematically pleasing (or even correct)...but here goes...

> We have $f(N)=N\space lg\space N + O(N)$
>
> By definition, $O(f(N))$ stands for the some upper bound for the function $f(N)$.
>
> Therefore, in our relation $O(N)$ (being an upper bound function) should theoretically contain $f(N)$ as $N \rightarrow \infty$.
>
> Now consider the lower bound of $f(N)$ to be some function of $N \space lg \space N$, i.e. $\Omega(f(N)) \equiv f(N \space lg \space N)$
>
> Now, $lg \space N \equiv log\_2 \space N \> log \space N$, where $log$ stands for natural logarithm. Hence natural logarithm is some constant factor of "binary" logarithm, where that constant is less than 1.

So all the above reasoning naturally implies our above assertion, right? Where am I wrong?

# Answer
> 4 votes
Your third line (of the proof) doesn't seem to make sense, are you trying to say $f(N) \in O(N)$? If so, that's not true (you're trying to prove that it's not true!). Lines 4 and 5 are not clear, but if you were to write that in an exam or paper, you'd get in trouble.

As usual with asymptotic analysis, we just need to go back to the definitions. $f(N) \in \Theta(N\log N)$ means there exists constants $N\_{0}$, $c\_{1}$ and $c\_{2}$ such that $c\_{1}\times Nlog N \leq f(N) \leq c\_{2}\times N\log N$ for all $N \geq n\_{0}$.

There's a method involving limits that works, but I'll do it the old fashioned way first:

**Lower bound ($f(N) \in \Omega(N\log N)$):**

As $f(N) = N\log N + O(N)$ (and because we're dealing with CS so we make mathematical unjustified assumptions like everything is non-negative) we have $f(N) \geq N \log N$, so we can pick $c\_{1} = 1$ and any $n\_{0} \geq 0$ and we have $f(N) \in \Omega(N\log N)$.

**Upper bound ($f(N) \in O(N\log N)$):**

By the definition of $O(\cdot)$, we know that $f(N) \leq N \log N + b\times N$ for all $N \geq m\_{0}$, for some constants $b$ and $m\_{0}$. We can assume that we're using base 2 logarithms and that $N \> 2$, so we know then that $\log N \geq 1$. Therefore $f(N) \leq N\log N + b\times N \leq N\log N + b\times N \log N$.

Thus we can pick $c\_{2} = b+1$ and andy $n\_{0} \geq \max\\{m\_{0},2\\}$ and we get $f(N) \in O(N\log N)$.

**Putting it together:** So we have $f(N) \in O(N\log N)$ and $f(N) \in \Omega(N\log N)$, which gives $f(N) \in \Theta(N\log N)$ where $c\_{1} = 1$, $c\_{2} = b+1$ and $n\_{0} = \max\\{m\_{0},2,0\\}$ (obviously the $0$ is extraneous).

**The Limit Approach:**

We can also take the limit of the ratio of two functions to determine some asymptotic relationships. In particular for us, if $\lim\_{n\rightarrow \infty}\frac{f(n)}{g(n)} = k$ for some constant $k$, then $f(n) \in \Theta(g(n))$.

So for our two funtion, we take $\lim\_{n\rightarrow \infty}\frac{f(N)}{N\log N}$ apply l'Hopital's rule a couple of times, and conclude that $f(N) \in \Theta(N\log N)$.

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


title: Question on NP $\cap$ coNP

text:
# Question
Title: Question on NP $\cap$ coNP
I'm struggling with a past paper question and would appreciate any hints:

Suppose $L\_1, L\_2 \in $ NP $ \cap $ coNP and $L\_1 \oplus L\_2 = \\{ x : x $ is in exactly one of $L\_1 $ or $ L\_2 \\} $. Then prove that $L\_1 \oplus L\_2 \in NP \cap coNP$

# Answer
> 5 votes
Hint: What $L \in \mathsf{NP} \cap \mathsf{coNP}$ means is that if $x \in L$ then there is a witness for this, and if $x \notin L$ then there is a witness this. From these witnesses for $L\_1,L\_2$ you can easily construct witnesses for $L\_1 \oplus L\_2$. A witness for $x \in L\_1 \oplus L\_2$ would be:

1. A witness for $x \in L\_1$ and a witness for $x \notin L\_2$; or
2. A witness for $x \notin L\_1$ and a witness for $x \in L\_2$.

A witness for $x \notin L\_1 \oplus L\_2$ is similar and left as an exercise.

More generally, if $L\_1,\ldots,L\_k \in \mathsf{NP} \cap \mathsf{coNP}$ and $\phi$ is any function on $k$ inputs, then $\phi(L\_1,\ldots,L\_k) \in \mathsf{NP} \cap \mathsf{coNP}$ (defined analogously to $L\_1 \oplus L\_2$), for similar reasons.

---
Tags: complexity-theory, closure-properties, complexity-classes, np
---


# Question
Title: How to state that a complexity bound does not depend on a given parameter size?
I am often ill at ease with Landau (Big O) notation, because it seems often to be abusing mathematical notation. The best example is the use of the equal sign to express a set membership. And this can be misleading.

I have an algorithm that is dependent on two parameters $n$ and $m$, which are the respective sizes of the two pieces of data it works on, like (for example) in the case of a substring search, where you have the size $n$ of the string being searched and the size $m$ of the pattern to be found.

I want to express that the algorithm is $O(n)$, but with a constant that is independent of the value of $m$.

A simple example is the recognition of a regular set, which is linear in the size of the input string, independently of the size of the regular expression defining the regular set, provided it has been compiled into a DFA (which is supposed to be amortized on many recognitions). This is usually implicit, but can I make it explicit when it is less obvious, or less well known.

The problem seems to be that people will often write $f(n)\in O(g(n))$ to mean that ultimately $|f(n)|\leq k\cdot |g(n)|$ even when $k$ actually depends on $m$. I realize that this depends on how you look at the problem, and whether you consider that the parameter of size $m$ is part of the data.

But then, how can one state unambiguously and clearly, *but without being too verbose*, that, though the size $m$ parameter is part of the data, the algorithm is $O(g(n))$ independently of $m$, i.e. the same constant $k$ can be used even though $m$ may grow arbitrarily? Is there a notation or terminology for it?

Is there a better way recommended by HABON (the High Authority on Big O Notation)?

# Answer
> 2 votes
The usual convention is to state upfront that your big O notations are with respect to $n$, and that whenever the constant depends on some parameter $m$, then you write $O\_m(\cdot)$.

If in another paper you are fine with allowing the constant to also depend on the parameter $m$, then instead you state upfront that your big O notations are with respect to $n$, and the underlying constant could depend on $m$. Then you can use Luke Matheison's suggestions that if in some case your big O doesn't depend on $m$, then you mention that in that case the underlying constant doesn't depend on $m$; but that could be more confusing than the convention in the preceding paragraph.

---
Tags: complexity-theory, terminology, asymptotics, landau-notation, notation
---


title: What is the triangulation angle?

text:
# Question
Title: What is the triangulation angle?
I start to work in the field of computer vision and read a paper in which the author states "When suitable correspondences between salient image structures have been established, the 3D uncerntainty of these structures mainly depends on the triangulation angle between the oberservations and the 3D structures". So what is the triangulation angle? In the wikipedia article on triangulation (http://en.wikipedia.org/wiki/Triangulation\_%28computer\_vision%29) there is a really nice pictures that explains the triangulation but which angle in this picture is the trinagulation angle?

# Answer
The angle between the projections of the target point, along the host surfaces, is technically called `Triangulation Angle`.
> 2 votes

---
Tags: computer-vision, robotics
---


title: Is there a continuous hash?

text:
# Question
Title: Is there a continuous hash?
### Questions:

Can there be a (cryptographically secure) hash that preserves the information topology of $\\{0,1\\}^{\*}$?

Can we add an efficiently computable closeness predicate which given $h\_k(x)$ and $h\_k(y)$ (or $y$ itself) tells us if $y$ is *very* close to $x$ (e.g. the Levenshtein distance or Hamming distance of $x$ and $y$ is less than a fixed constant $c$)?

---

### Background:

By information topology on $\Sigma^\*$ on I mean the topology space with points $\Sigma^\*$ and with the base $\\{x\Sigma^\* : x \in \Sigma^\* \\}$.

A nice way to think about topology is considering open sets as properties of points which are *affirmable*/*verifiable* (i.e. if it is true, it can be verify/observe that it is true). With this in mind, closed sets are *refutable* properties.

A function $f:\Sigma^\* \to \Sigma^\*$ is continuous if the inverse image of opens sets are open. In our case this means that for all $y \in \Sigma^\*$, there is $I \subseteq \Sigma^\*$ such that $$f^{-1}(y\Sigma^\*) = \bigcup\_{x\in I} x\Sigma^\*. $$

A nice way to think about the information topology is looking at it as a tree of binary strings. Each subtree is a an base open set (and other open set can be obtained from taking a union of base open sets).

This is sometimes referred to as information topology of strings because each point in $\Sigma^\*$ can be considered as a finite approximation to a binary string/sequence. $x$ approximates $y$ iff $x$ is an initial substring of $y$ ($x \sqsubseteq y$). E.g. $0011\Sigma^\*$ is an approximation to $00110^\*$ because $0011 \subseteq 00110^\*$.

And for continuity, if we take a sequence $\\{x\_i\\}\_i$ which approximate and converge to binary sequence $y$ (think of $y$ as an infinite branch in the tree and $x\_i$s as points on that branch) then $\\{f(x\_i)\\}$ converge to $f(y)$, $$f(y) = \bigsqcup\_i f(x\_i).$$

# Answer
For modern cryptographic hash functions, no, there is no efficiently computable closeness predicate, assuming the distribution on $x$ has sufficient entropy. The intuition is that these hash functions are designed to "have no structure", so they don't admit anything like this.

In technical terms, modern cryptographic hash functions behave "like a random oracle". For a random oracle, there is no such closeness predicate: the best you can do appears to be to invert the hash function and then enumerate all close strings and hash them. As a result, there's no way to do this for modern cryptographic hash functions.

Heuristically, it does possible to design a custom hash function which does admit an efficiently closeness predicate, and which is (roughly) "as secure as possible" given this fact. Let's assume the strings we are going to hash are of fixed length. Suppose we have a good error-correcting code, and let $D$ be the decoding algorithm (so it maps a bit-string to a nearby codeword, if it can).

To get a simple but imperfect scheme, imagine defining $h(x) = \text{SHA256}(D(x))$. If $x,y$ are two random strings that are sufficiently close, then there is a decent chance that $h(x)=h(y)$. If $x,y$ are not close, then $h(x)$ will look nothing like $h(y)$, and we'll get no information beyond the fact that $x,y$ are not close. This is simple. However, it is also imperfect. There are many pairs $x,y$ that are close but where we can't detect this fact from $h(x),h(y)$ (e.g., because the decoding function $D$ fails).

Heuristically, it looks possible to improve this construction. At design time, choose random bit-strings $r\_1,\dots,r\_k$. Now, define the following hash function:

$$h(x) = (\text{SHA256}(D(x \oplus r\_1), \dots, \text{SHA256}(D(x \oplus r\_k)).$$

Now if $x,y$ are sufficiently close, it is likely that there exists $i$ such that $D(x \oplus r\_i) = D(y \oplus r\_i)$, and thus $h(x)\_i = h(y)\_i$. This immediately suggests a closeness predicate: if $h(x)$ matches $h(y)$ in any of its $k$ components, then $x,y$ are close; otherwise, infer that they are not close.

If you additionally want collision resistance, a simple construction is the following: let $h\_1(\cdot)$ be a hash function with a closeness predicate; then $h(x) = (h\_1(x), \text{SHA256}(x))$ is collision-resistant (any collision for this is also a collision for SHA256) and has a closeness predicate (simply use the closeness predicate for $h\_1$). You can let $h\_1(\cdot)$ be the hash function defined above.

This is all for Hamming distance. Edit distance is probably significantly harder.

In coming up with the above construction, I was inspired by the following paper:

Ari Juels, Martin Wattenberg. A Fuzzy Commitment Scheme.

Ari Juels, Madhi Sudhan. A Fuzzy Vault Scheme. Designs, Codes, and Cryptography 38(2): 237-257, 2006.

Incidentally: in cryptography, hash functions are unkeyed. If you wanted a keyed thing, you might want to take a look at pseudorandom functions.
> 5 votes

---
Tags: complexity-theory, cryptography, hash, string-metrics, topology
---


# Question
Title: Prove/ Disprove: If $L$ is a CFL then $A(L)$ is a CFL too
Consider the operation $A(L)$:

$$A(L) = \\{ w: w\in L \land w\_R \notin L \\}$$

where $w\_R$ is the reverse of $w$.

> Prove/ Disprove: if $L$ is a CFL language so does $A(L)$.

I am almost certain there's a counter-example but I couldn't find a proper one. I'd be glad for help!

Thanks

# Answer
> 3 votes
A simple first step.

Consider any language $K \subseteq \\{a,b\\}^\*$, and let $1,2$ be two new symbols. Let $L = 1\cdot \\{a,b\\}^\* \cdot 2 \cup 2 \cdot K \cdot 1$.

What if $1x2\in A(L)$?

# Answer
> 1 votes
Hint: First, try the following. Prove/disprove: if $L$ is regular, then so is $A(L)$.

Another hint: That should help you narrow down your search for a counterexample. Next, try to come up with a language that you know is context-free but not regular. Try tweaking it a little bit so that it has a non-trivial intersection with its reversal. What do you come up with? I was able to very quickly solve this problem using this approach -- the first example language I came up with, and the first modification I tried, worked.

---
Tags: formal-languages, context-free, closure-properties
---


# Question
Title: What is the minimal number of states for the DFA?
> Let the regular expression $R = ((a^\*\cup \emptyset \cup \varepsilon^\*)^\*b)^\*$ above $\Sigma = \\{a,b,c,d\\}$. What is the minimal number of states for a DFA accepting this regex?

1. $1$
2. $2$
3. $4$
4. $5$ or more

So for my understanding, this regex is equivalent to $(a^\*b)^\*$. I was able to build the following DFA, nevertheless, I know the **answer is $2$**. How is it possible?

# Answer
Your $\Sigma=\\{a,b,c,d\\}$ so you have to add at least one dead state. The DFA is:
> 2 votes

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


# Question
Title: Why can Multilayer neural networks solve non-linear problems
I understand what a multilayer neural network is, but what about them allows them to solve non-linear problems unlike perceptrons? Is it the fact that they can extend to any number of outputs/hidden layers? Or is it another feature?

# Answer
A single-layer network is already nonlinear, but it's only a limited kind of nonlinearity.

Yes, the ability to have multiple layers and multiple hidden nodes is what allows multi-layer neural networks to express any function.

Let me give you an analogy that provides intuition but shouldn't be taken too seriously. A single NAND gate can compute only a single, simple function. However, when you consider circuits containing NAND gates, they can express any boolean function: the ability to have multiple layers of NAND gates, and multiple intermediate gates in the middle, allows you to express any boolean function. Something vaguely similar happens with multi-layer neural networks: each individual unit provides a limited amount of nonlinearity, like a NAND gate, and the ability to compose them is what lets you express more complex nonlinear functions.
> 3 votes

# Answer
Artificial neural networks are intrinsically supposed to handle the simulation and tracking of every function, if the sufficient number of the neurons in addition to enough number of the trials (to acquire the desired resolution) will be taken into account.

Of course, one might assert that above argument is actually realizable within the territory of the pattern recognition. In the other words, ANNs are able to use the imitations of the simulated functions within the decision making problems of pattern recognition stuffs.

Multilayer neural networks can increase their ability to cluster the hyper space of the network and approximate more complicated polynomial functions. As from a theoretical perspective, multitude of nonlinear functions could be approximated with the functions of polynomials. Hence, increment the number of hidden neurons and even extending the input stimulative signals and outputs will lead to better performance of the ANN regarding its functionality for aforementioned approximation.
> 1 votes

---
Tags: artificial-intelligence, neural-networks, intuition
---


title: Power of variants of Turing machines

text:
# Question
Title: Power of variants of Turing machines
I'm having trouble with this problem as I haven't discovered a good way to determine the power of a Turing machine. I was under the impression that if a Turing machine can perform the same actions and satifies unrestricted access to unlimited memory they're all pretty much equivalent. Such as multiple tapes and nondeterministic Turing machines.

I am to determine if a and b are equal, more powerful or less powerful then a single-tape Turing machine. Where do I start?

a) A Turing Machine that can only make moves to the right and never left.

b) A Turing Machine that can move right one space or move left two spaces.

# Answer
> I was under the impression that if a Turing machine can perform the same actions and satifies unrestricted access to unlimited memory they're all pretty much equivalent.

Hint 1: So your first step should be to determine whether a and b have, or can obtain, unrestricted access to unlimited memory.

Hint 2: If yes, then try to emulate the missing pieces of your preferred Turing machine model.

Hint 3: If no, then try to show that the halting problem (with empty tape as input) is decidable.
> 2 votes

---
Tags: computability, turing-machines
---


# Question
Title: What is a standard way to construct a turing machine for any function to compute
I am new to turing machines, I am having problems with mapping a function to a turing maching that computes that particular function. for example:

1. f(x) = 2x + 3 n\>= 0
2. MIN(x,y) leaves the smallest between x and y on the tape. e.g. x=2 y = 3 i.e. #aabaaa

I am not looking for a solution to the above but some kind of pattern i can use to solve these kind of particular problems quicker, in terms of transitions and what to have in mind before starting to solve.

# Answer
> 3 votes
Designing a Turing machine is pretty much like writing a program. You have to choose a representation for the data and a corresponding code (read * transitions\*) to manipulate the data. Remember how we do arithmetics (addition, multiplication, quotient, ...) by manipulating in strange ways strings of symbols that represent numbers, whether in unary or positional representation, or even with Roman numerals.

The difficulty is generally that the means for data representation are pretty elementary: symbols on a tape. So you have to find ways to encode everything into that. Also the programming instructions are very simple. So you have to find a way (for complex machines) to decompose the problem into parts, and to assemble the coresponding machine parts. Pretty much what you do when you define functions and subprograms in usual programming.

You can make your life easier by using different sets of states for each subprogram. But basically people rarely design Turing machines, except for specific proofs. Then the problem is often how to combine into one several simpler machines that have been separately designed. You can find that in textbooks.

It can be amusing to find elegant solutions for simple problems. Like puzzles. You can add constraints. For example, you second question can be solved in several ways. Some use more tape than others.

Exercise: do long multiplication of two binary numbers, then two ternary numbers. Well, just think about it. Where would you store the multiplication table?

---
Tags: computability, turing-machines
---


title: Proof of $P^{\text{#}P} = P^{PP}$

text:
# Question
Title: Proof of $P^{\text{#}P} = P^{PP}$
I was reading this article on the complexity class $PP$.

In the fourth paragraph there is a claim that $P^{\text{#}P} = P^{PP}$ and that it can be proved using binary search. Can anyone please explain this in better detail?
The author himself gives the following explanation: If $f$ is a $\text{#P}$ function then the language $L= {(x,k) | f(x) \geq k}$ is in $PP$. Then do binary search on $k$.

This is still not clear to me. The other direction, $P^{PP} \subseteq P^{\text{#}P}$ is clear.

# Answer
> 3 votes
It all boils down to simulating a $\mathsf{\\# P}$ oracle using a $\mathsf{PP}$ oracle. Consider a $\mathsf{\\# P}$ oracle call: a polytime non-deterministic Turing machine $T$ and an input $x$. We want to know how many runs of $T$ result in the output $1$. Denote this number by $T\_1(x)$, and denote the total number of runs of $T$ on $x$ by $T(x)$.

First, let's show that using a $\mathsf{PP}$ oracle we can decide whether $T(x) \geq y$ for any polysize $y$. We construct a Turing machine $T'$ that acts as follows:

1. Guess a non-deterministic bit $b$.
2. If $b = 0$, then simulate $T$ on $x$ in such a way that there are $2T(x)+1$ different paths, and in all of them return $1$.
3. If $b = 1$, then have $2y$ different paths, all of them returning $0$.

The $\mathsf{PP}$ oracle returns *Yes* iff $T(x) \geq y$. I'll let you show how to implement steps 2 and 3.

Second, we can use binary search to determine $T(x)$ exactly. We start by determining some upper bound on $T(x)$: ask whether $T(x) \geq 2^k$ for $k=0,1,\ldots$, until you find a value of $k$ such that $T(x) \< 2^k$. Since $T$ runs in polytime, $k$ is polynomial, and so this step takes polytime. Next, you do classical binary search (starting from $0 \leq T(x) \< 2^k$), and determine $T(x)$ exactly. Again, this takes polytime since $k$ is polynomial.

Third, using our knowledge of $T(x)$, we can decide whether $T\_1(x) \geq y$ in a similar way. For example, we could construct a new machine $T'$ with $T'(x) = T(x) + T\_1(x)$, and then decide whether $T'(x) \geq T(x) + y$. You fill in the details.

Finally, we calculate $T\_1(x)$ using binary search. This time we can skip the first half-step since we already know that $T\_1(x) \leq T(x)$.

---
Tags: complexity-theory, complexity-classes, counting
---


title: DFA for regular language

text:
# Question
Title: DFA for regular language
I need to construct a DFA which accepts the following language: $$ L = \\{w \in \\{a,b\\}^{\ast}\mid \\#\_{a}(w) \bmod 3 = \\#\_{b}(w) \bmod 2\\} $$ I have no clue how to solve this issue. Can you please help me?

# Answer
> 3 votes
Hint: Keep track of $\\#\_a(w) \pmod{3}$ and $\\#\_b(w) \pmod{2}$, using $3\times 2$ states.

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


# Question
Title: Perceptron learning rule past exam question
I'm struggling to solve this past paper question and my lecturer is being less than helpful. The question is:

**Apply the perceptron learning rule to update the current weight vector (0.1, 0.3) when the learning rate is 0.01, the input vector is (2.0, 4.0), and the error vector is (1, -1).**

What has me confused is the use of vectors for the current weight, input and error value. We've never used vectors for this before (only regular numbers) and no examples I can find online use 2D vectors like this.

I know the perceptron learning rule is:

```
New weight = old weight + (learning rate * perceptron input * error value)

```

But I'm not sure how to do this kind of maths with 2D vectors to get a 2D vector as my result (which is what I assume I want, since the question seems to be asking for the new weight).

# Answer
> 2 votes
Firstly let me say that I am not going to solve this for you. What I would do instead is help you figure out how to solve it all by yourself.

* How many inputs will your perceptron have if your input vector is in ***n***-D?
* Conceptually, what does the output from a perceptron represent?
* Following from the second point, what does updating the weights do to the output from your perceptron?
* Ideally, what ***should*** the updating of the weights do to the output?
* When do you need to update the weights?

Think about this by plotting the inputs and output from the perceptron on a graph.

These are some of the basic concepts you need to understand to get the basics of Artificial Neural Networks (ANNs).

Good Luck

---
Tags: artificial-intelligence
---


# Question
Title: Good introduction to Turing's work and complexity theory?
I'm currently an undergrad whose been amazed by what Turing has done for the world. I know there are plenty of other amazing individuals, but Turing's work specifically has always sounded the most interesting to me and I'm finally at the point where I can understand some of it. So my question is, where do I really begin to dive into his work? I have yet to take an official theory course, but I'm determined enough to go through important works that will help me get where I need. I'm currently reading his 1936 thesis and I find it mostly understandable, but I want to go deeper into the mathematics behind it all.

On a similar note, I think what I overall am interested in is complexity theory. I have some experience with basic abstract algebra, and some mathematical maturity. Can anyone list some books/papers to read, some introductions and some deeper, that can help me fully understand the implications of some topics, i.e. P=NP? How T.M.s were and are currently being used as foundational tools to prove and disprove ideas? I realize these are vague questions, but I want people to suggest books/papers that have been most influential to them that are related to these topics (or any other influential reads that one might have).

If I said anything incorrectly please feel free to correct me!

# Answer
> 7 votes
Some popular books are *Computational Complexity* by Papadimitriou and *Introduction to the Theory of Computation* by Sipser. If you are very ambitious, you can also try *Computational Complexity: A Modern Approach* by Arora and Barak, which is an advanced textbook.

I would recommend against the historical approach of reading old papers. While some old papers are a good read (some of Turing's papers, Shannon's 1948 paper), old papers tend not to follow modern conventions, have a somewhat different focus, are less streamlined than modern treatments, could contain weaker results, and (in some cases) wrong results or at least wrong proofs. A good textbook is much preferable.

Regarding Turing machines, while they have some theoretical advantages in some circumstances, they are poor models of actual computers. Indeed, even in the theoretical computer science community, algorithms are usually described in the so-called *RAM machine* model which conforms much more closely to actual computers. Even historically speaking, Turing's model wasn't the first universal computation model, though (if I remember correctly) it was the first one that Gödel found convincing (Gödel's own general recursive functions, for example, predates it).

On your way to complexity theory, don't forget to stop at recursion theory (sometimes called computability theory), which had been practiced for a few decades before modern complexity theory started in the early 1970s. The usual course sequence indeed starts at (very basic) recursion theory and progresses to complexity theory.

---
Tags: complexity-theory, turing-machines, books
---


title: Sub-Array with a unique element

text:
# Question
Title: Sub-Array with a unique element
You have an Array of length ***n***. If you pick a sub-array from the array, it must contain at least one unique element. The sub-array could be of any length but must contain consecutive/successive elements.

The question is what is the minimum number of characters you need to ensure that your array has the property mentioned and how should those elements be placed in the array? the answer needs to be in terms of ***n***.

For Instance,

Let ***n*** be 10. Then you can place ***n*** different characters in it.

***a, b, c, d, e, f, g, h, i, j***

such that any sub-array would contain all unique elements. In this case the answer is ***n***. But, of course this is not optimal as you need only one unique element in the sub-array.

In the same example of to pick 2 elements ***a*** and ***b*** and place them as

***a, b, a, b, a, b, a, b, a, b***

and you pick a sub-array of the first 4 elements ***a, b, a, b*** then you do not have any unique element. In this case the answer is 2 but is **Incorrect**.

So, what is the minimum number of unique element (and their placement in the array) you need to ensure your array has the property mentioned.

# Answer
$\lceil \lg n \rceil$.

For example, for $n=10$, try ABACABADAB. See if you can work out the pattern.

(I'll leave it at that, as this is a nice exercise problem and I'll let you have the joy of solving it on your own.)
> 2 votes

---
Tags: algorithms, algorithm-analysis
---


# Question
Title: Spatial data structures are part of Computational Geometry?
Are spatial data structures like BVH - Bounding Volume Hierarchy ,kD-Trees etc are part of Computational Geometry( http://graphics.stanford.edu/courses/cs268-14-fall/) or of

Data structures and Algorithms( http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-851-advanced-data-structures-spring-2012/index.htm ) or of

Geometric modelling( https://graphics.stanford.edu/courses/cs348a-12-winter/ ) ?

If Spatial data structures are not part of neither of these 3, Can you tell which branch of computer science deals with the spatial data structures?

# Answer
> 2 votes
You need spatial data structures as part of *computational geometry*, to have at least some reasonable base reference against which to compare the time and memory consumption of special purpose (sweepline/randomized) algorithm. For this purpose, BVH is too vaguely defined to be useful (except for summarizing a common principle for some better specified data structures), but kD-trees are good enough for this purpose.

I don't see where you would need spatial data structures for non-geometry related *data structures and algorithms*, so I would say it is only a part of it, if you study geometry (or GIS) related problems. But if anybody shows me a non-geometry related application, then I'm quite willing to change my mind.

For *geometric modeling*, things like constructive solid geometry, homogeneous coordinates, Bézier curves, B-splines and NURBS should come first, because understanding them is also important when just using existing geometry modeling software. But BVH fits in well, because it is an intuitive geometric concept. It can sometimes be useful for understanding the performance behavior of existing geometry modeling software (sometimes the user can even influence the BVH to improve performance). I see fewer reasons why kD-trees should be part of geometric modeling.

---
Tags: data-structures
---


title: Amdahl's law or gustafson's law

text:
# Question
Title: Amdahl's law or gustafson's law
I am a little confused which of the two laws above i should use:

Suppose I have a computer program that can be parallelized by 70%. 30% cannot be parallelized. Every single data (100% of data) will pass the parallelizable part and also pass the non-parallelizable part.

I want to calculate how much more data i can process in a fixed amount of time if i use 2 processors instead of 1 processor.

My thinking is that since the 30% doesn't change when I increase the data, the total time spent in the non-parallelizable part will increase. Therefore, I would guess I have to use Amdahl's Law.

I think Gustafson's Law is used when the total time spent in the non-parallelizable part is constant, therefore the parallism will go up.

I cannot find a solution to this since usually Gustafson's Law is related to problems where the time is fixed and you have to find the amount of data that can be processed for given number of processors. But this case might be different?

# Answer
I finally found the solution and I want to share it with you,

The solution is that you have to use Amdahl's Law. Iff 30% of time is sequential you should use Gustafson's Law.
> -1 votes

# Answer
The difference between Amdahl’s Law and Gustafson’s Law lies basically in the application’s objectives, whether to make the application run faster with the same problem size or run the application in the same time with increasing problem size.

Gustafson’s approach introduces time constraints taking the execution time as a constant, therefore the parallel and the non-parallel executed time are considered as constants.

http://www.techcliste.com/speedup-factor-in-parallel-computing/
> 3 votes

---
Tags: computer-architecture, parallel-computing, performance
---


# Question
Title: Why are syntax trees used in genetic programming?
Reading a course on genetic programming, the first chapter describes the syntax tree as the basic representation of programs in genetic programming.

What are the reasons leading to the choice of a syntax tree in genetic programming? Are there any particular assets in using this representation?

# Answer
> 5 votes
*In short*: **AST representations of programs are more easily analyzed, manipulated, and transformed, while preserving and enforcing the existence of a formally defined program meaning through the transformations.**

*I am asssuming that the reader knows already what is an abstract syntax tree (AST), and does not need to be shown examples.*

The question is an issue about abstract objects (semantics) and their representations (syntax). We are usually interested in the semantics, applying transformations to entities to change or combine their meanings, their semantics, which can belong to all kinds of domains. But semantics is elusive, mathematical abstraction, and all we can actually manipulate to express our intent is syntax representations.

That is the basis of all programming, but is also to be found in logic, proofs, and finally all of mathematics. That is what makes the choice of representations and notations often so important. Good choice of representation will lead to easier, possibly more perspicuous or intuitive understanding of the problem and be better adapted at expressing answers, and proofs, for given questions.

The point is well known to programmers, as they are taught that it is essential to choose the right data structure in order to implement an algorithmic solution to a given problem. The choice of data structure is the choice of representation. And I just made a similar answer to a question on constructing (programming?) Turing Machines.

Note that there is a partially ambiguous use of the word syntax, which can be any concrete representation of an abstraction, or can be intended to mean only textual representation as strings (we are getting close to Turing machines), possibly structured by some logical system (a context-free (CF) grammar for example that specifies what are the legitimate strings, the *well-formed-strings*.

In fact, the existing parsing-unparsing technology, especially for CF grammars, makes it generally easy to switch between textual and an associated tree representation, to the point that they are often not distinguished much. Actually, mathematicians have been using tree representation (formally defined as Algebras), long before that technology existed, and this is what lead to using the representation of AST in manipulating programs.

So what was so convenient about these tree (or AST) representations?

**The key points are:**

* **it is very convenient for associating precisely semantic meaning to syntactic constructs, in a compositional way, by means of a simple mathematical concept: the homomorphism;**
* **it provides and enforces a syntactic type system (statement, expression, ...) that preserve the existence of some meaning when the program representation is transformed in a way that preserves the syntactic typing constraints;**
* **it is easily manipulated to actually perform analysis and transformations;**
* **it is easy to decorate it with localized information to help or guide these analyses and transformations.**

First, if you take a string representation of a program, without further structural information, there is no simple way to delimit substrings that have naturally a meaning of their own (I am saying *naturally*, because some people may always try to play at abstracting syntactic context or indulge in syntactic (text oriented) continuation games - ignore this if you do not get it).

The idea of a tree structure, with nodes labeled with operators, possibly restricted by syntactic types (statement, expression, variable, ...) is that they naturally decompose the syntactic structure into subparts (the subtrees) that can have fairly naturally, and perspicuously with respect to computational concepts, a semantic meaning of their own.

Then, if we associate a semantic function to each operator, we can get the meaning of a tree representation by applying the semantic function of the root operators to the semantic meaning of each of its subtrees. If we also provide some semantics to leafs operators (which may be defined as a mapping from syntactic representations to some semantic domains possibly by other means, for example associating the integer 23 to the string "`23`"), we know how to define simply the semantics of any well-formed tree, whether complete program or well-formed program fragment. This is the basis of what is known as denotational semantics.

In other word, the homomorphism thus defined gives a rather simple and tractable way to associate meaning to well-formed program fragments, by composing the meanings of its well-formed sub-fragments (this is known as semantic compositionality). Then, it becomes much easier to attempt defining semantically meaningful transformations. And semantics, what the program (fragment) does is what we really care about.

Furthemore, AST are fairly easy to manipulate by programs to express these transformations that somewhat respect the semantic structure (as they manipulate subtrees that are semantically meaningful), which initially justified their use in program editors, program manipulation systems, and programming environment.

Actually, the concept of AST in programming appeared with the language Lisp (and its ability to manipulate Lisp programs syntactically) in the very late fifties. But it developed mostly in the seventies (Emily, Cornell synthesizer, Mentor/Centaur), and further in the eighties, at the same time as denotational semantics (which is based on the above approach), and most likely under the influence of denotational semantics. The early work (LCF) on automated proofs about computation may also have been influencial.

**From the point of view of genetic programming**, the use of AST both facilitates and enforces the creation of syntactic structures that are more likely to have some meaning. Manipulating unstructured string representations would be likely to result in being swamped with string representations to which no meaning can be associated.

Another advantage of AST representations is that they are fairly easy to decorate with additional information: precomputed semantic properties, weights, or whatever is deemed useful for the intended program transformation or manipulation, including genetically programed transformations.

## A detailed example

*This section has been added later to answer some comments.*

I will try to work out one example in some details to explain the relation between manipulations on the AST and their semantics conterpart.

We take a very simple example of crossover between two ASTs: T1=`foo(exp1,exp2)` and T2=`bar(exp3, exp4)`. I keep it small for readability. Actually, `exp1` to `exp4` are meant to be subtrees of some AST, while you may also see what is around them as standing for the rest of some AST (or some AST subtree) that is the context in which they occur.

We suppose first that the language does not have typing (in the usual sense of programing languages), and accept any value in any context expecting a value, so that any expression can legitimately replace any other.

Then given T1 and T2, it is legitimate to apply a crossover that swaps `exp1` and `exp4`, thus producing T1'=`foo(exp4,exp2)` and T2'=`bar(exp3, exp1)`. Note that the algorithm could also consider only one of these two trees (I am incompetent regarding genetic splicing strategies).

Now, let us see what can be said about semantics, without getting too much into details.

Let $S$ be the semantic function, $V$ the domain of values, $M$ the domain of environments that map identifiers to values. The semantics $S$(`exp`) of an expression `exp` is a function $e: M\to V$ that takes an environment $m$ as argument (so that we have values for identifiers) and returns the value of the expression in that environment.

Now, if the operators `foo` and `bar` are supposed to compute respectively two functions $f$ and $b$ on their arguments, the semantics of T1, for example, will be defined as

$S$(`foo(exp1,exp2)`)=$S$(`foo`)($S$(`exp1`),$S$(`exp2`))=$\lambda m.f(e\_1(m),e\_2(m))$

You notice that the semantic function is not necessarily easy to define in the complex case of a programming language, since for `foo` we have here $S$(`foo`)=$\lambda e, e', m\\,.\\, f(e(m), e'(m))$.

This complexity results from the choice of the Abstract Syntax, that considers here `foo` and `bar` as AST operator nodes. Instead, the AST could have a `call` operator that has several daughters, for example as in `call(foo, exp1, exp2)`. Then the complexity of dealing with the environment $m$ would be factorized in the semantics of `call`, while the semantics of `foo` would simply be the function $f$.

Sorry for this complexity.

The whole point is that we can define the semantics of an AST subtree such as `exp1` independently of any context, but as a function $e\_1$. Whatever information it needs from the context to be evaluated is summarized in the arguments (here the environment $m$) that are passed to its semantics. And this information is in turn passed to the semantic functions associated to subexpressions.

So now we know that a subtree of AST can have a well defined semantics, independently of its context.

But what about the context? Does it have a well defined semantics when a subtree is missing. The nice point is that it does.

If you consider the context `foo(??,exp2)`, what can its semantics be. The natural answer is that it is whatever semantics it would have if you provided the missing part. In other words, it is a functional semantics that takes as argument the semantics of the missing part. This is very similar to the semantics of the complete expression $S$(`foo(exp1,exp2)`) that we defined above, except that the missing `exp1` must be accounted for with an argument $e$ standing for the semantics of whatever expression could replace `exp1`.

We had $S$(`foo(exp1,exp2)`)=$\lambda m.f(e\_1(m),e\_2(m))$

So, without going into further details, you have

$S$(`foo(??,exp2)`)=$\lambda e.\lambda m.f(e(m),e\_2(m))$

Then, given that $S$(`exp1`)=$e\_1: M\to V$, we have
$S$(`foo(exp1,exp2)`)= $S$(`foo(??,exp2)`)($S$(`exp1`))

which is precisely what we would like: syntactic abstraction directly translate into semantic abstraction.

Then we also have, of course:

$S$(`foo(exp4,exp2)`)= $S$(`foo(??,exp2)`)($S$(`exp4`))

In other words, both AST subtrees and AST contexts (of subtree) have well defined semantics, that do not change, and they compose to give the semantics of the whole AST tree when a subtree is placed in a permitted context.

But of course: $S$(`foo(exp1,exp2)`) $\neq$ $S$(`foo(exp4,exp2)`)

I hope this explains how things work. Using well-formed AST will ensure that you are actually manipulating semantic fragments that compose meaningfully.

Actually, things may be a bit more complicated, because you want to include in the process what is usually called static semantics, i.e. constraints on the AST that are usually checked at compile time. The best known examples are type constraints for statically typed languages, or declaration of identifiers when that is required. Thus you may want to decorate ASTs with this statically computable information, and use splicing techniques that will incrementally preserve the information and check the required constraints on the AST, so that you produce only programs that at least compile.

Then as a last comment, I would like to remarks that linear genetic programming seems to be doing pretty much the same, but restricts splicing to sequences of statements, so that there is always some executable semantics preserved. But I am not specialist of that.

# Answer
> 3 votes
Syntax trees provide an abstract representation of a program with a certain kind of *type* information at each vertex. This allows, when attempting to evolve a program, the swapping/changing of subtrees as long as the root vertex of the subtrees have the same type. As long as the program was valid, (and the subtrees are also valid), the result will still be a valid program.

As a somewhat trivial example if your programming language has a rule for addition expressions along the lines of $\langle plus \rangle ::= \langle expression\_{1}\rangle + \langle expression\_{2} \rangle$, then anything that is an $expression$ (i.e. that satisfies the typing rules for $expression$) can be put in place for $\langle expression\_{1}\rangle$ or $\langle expression\_{2} \rangle$. So if you're trying to implement a crossover operator for example, you know the places where you can swap subtrees and still get something that makes at least a basic level of sense.

This is also why syntax trees are a very important tool in compilation - they have the same utility as representations of the flat text of the program.

Note that tree representations aren't the only way, see for example linear genetic programming.

---
Tags: algorithms, semantics, genetic-algorithms, syntax-trees, syntax
---


# Question
Title: Prove that regular languages and context-free languages aren't closed under $Perm(L)$
Let the operation $$Perm(L) = \\{ w | \exists u \in L \text{ such that } u \text{ is a permutation of } w \\}$$

> Prove that both regular languages and CFLs aren't closed under $Perm(L)$.

I've tried to use several well-known languages (like $\\{0^n1^n\\}$) and applying $Perm(L)$ and afterward manipulate them or using the pumping lemma in order to get a contradiction, but nothing worked out.

# Answer
> 6 votes
Hints:

1. For regular languages, consider $Perm((01)^\*) \cap 0^\* 1^\*$.
2. For context-free languages, consider $Perm(0^n 1^n 2^m 3^m) \cap 0^\* 2^\* 1^\* 3^\*$.

---
Tags: formal-languages, regular-languages, context-free, closure-properties
---


# Question
Title: Show that regular languages are closed under Mix operations
Let $L\_1, L\_2$, two regular languages and the operations:

$$Mix\_1(L\_1, L\_2) =\\{ a\_1b\_1a\_2b\_2\ldots a\_nb\_n | n\ge 0 \land a\_1,a\_2,\ldots ,a\_n,b\_1,b\_2,\ldots ,b\_n\in\Sigma\\ \land a\_1a\_2\ldots a\_n\in L\_1 , b\_1b\_2\ldots b\_n\in L\_2\\}$$

$$Mix\_2(L\_1, L\_2) = \\{ x\_1y\_1x\_2y\_2\ldots x\_ny\_n | n\ge 0 \land x\_1,x\_2,\ldots,x\_n,y\_1,y\_2,\ldots,y\_n\in\Sigma^\* , x\_1x\_2\ldots x\_n\in L\_1 \land y\_1y\_2\ldots y\_n\in L\_2\\}$$

> Prove that regular languages are closed under $Mix\_1$ and $Mix\_2$ operations.

So for the first operation:
Let $D\_1, D\_2$, two DFA's accepting $L\_1, L\_2$, respectively. We define $D = (Q,\Sigma, \delta, q\_0, F)$.

Where $Q = Q\_1 \cup Q\_2$. The transition function, $\delta$ will behave as $\delta\_1$ and $\delta\_2$. But in addition, Let's define $n = \left|\Sigma\right|$, then we make $n$ transitions from every $q\_i\in Q\_1$ to $q\_j\in Q\_2$ (and vice versa) for every $\sigma \in \Sigma$.

So it's pretty easy to see that $D$ accepts $Mix\_1(L\_1, L\_2)$.

**Question:**
How can I show that regular languages are closed under $Mix\_2$?

# Answer
> 5 votes
Take any string over the alphabet $\Sigma$. Colour some of the letters red and the remaining letters green. Accept the original string if the red letters form a string in $L\_1$ and the green ones are in $L\_2$.

More technically, regular languages are closed onder intersection and under (inverse) homomorpisms.

Let $\Gamma = \Sigma \times \\{1,2\\}$ be an alphabet with colours.

Define the homomorphisms $h\_i:\Gamma^\* \to\Sigma^\*$, $i=1,2$ by $h\_i(a,i) = a$ and $h\_i(a,j) = \varepsilon$ for $i\neq j$. These keep only letters of their assigned colour, whereas their inverses colour the letters into that asigned colour while inserting arbitrary letters of the other colour.

Finally let $g:\Gamma^\* \to\Sigma^\*$ be the morphism $g(a,i) = a$ (which removes the colour).

Then $Mix\_2(L\_1,L\_2) = g(\\; h\_1^{-1}(L\_1) \cap h\_2^{-1}(L\_2) \\;)$.

PS. Let $R\_{12}$ be the regular language $\[(\Sigma\times \\{1\\})(\Sigma\times \\{2\\})\]^\*$. Then $Mix\_1(L\_1,L\_2) = g(\\; h\_1^{-1}(L\_1) \cap h\_2^{-1}(L\_2) \cap R\_{12} \\;)$.

Just for fun, $L\_1 \cdot L\_2 = g(\\; h\_1^{-1}(L\_1) \cap h\_2^{-1}(L\_2) \cap (\Sigma\times \\{1\\})^\*(\Sigma\times \\{2\\})^\* \\;)$. Regular languages are closed under concatenation :)

# Answer
> 3 votes
The solution you give for $Mix\_1$ doesn't seem quite right - consider the simple case $\Sigma=\\{a\\}$ and $L\_1=L\_2=\\{\epsilon\\}$, where $\epsilon$ is the empty word; obviously in this case, $Mix\_1(L\_1,L\_2)$ should also be $\\{\epsilon\\}$. The minimal DFA for this language is $(\\{q\_0,q\_1\\},\Sigma,\delta,q\_0,\\{q\_0\\})$ with $\delta(q\_0,a)=\delta(q\_1,a)=q\_1$. Your construction for $Mix\_1$ gives an NFA with set of states $\\{q\_{0,1},q\_{0,2},q\_{1,1},q\_{1,2}\\}$, where $q\_{0,1},q\_{0,2}$ are both initial and accepting, with set of transitions $\\{(q\_{i,j},a,q\_{1,j})\ |\ i\in\\{0,1\\},j\in\\{1,2\\}\\}\cup\\{(q\_{i,1},a,q\_{j,2}),(q\_{i,2},a,q\_{j,1})\ |\ i,j\in\\{0,1\\}\\}$; this will accept all $w\in\Sigma^\*$.

In order to solve this problem, both for $Mix\_1$ and $Mix\_2$, the automaton you want needs to do the following:

* keep track of the state of a DFA $A\_1$ for $L\_1$ while parsing one subset of the letters in the input,
* keep track of the state of a DFA $A\_2$ for $L\_2$ while parsing the remaining letters in the input,
* alternate between progressing in $A\_1$ and $A\_2$,
* accept when the last step was in $A\_2$ and both $A\_1,A\_2$ are in an accepting state.

The only difference between $Mix\_1$ and $Mix\_2$ in this regard is when to alternate (for $Mix\_1$: after each letter, for $Mix\_2$: whenever you want).

In order to keep track of the necessary information, the states should be of the form $(q\_1,q\_2,i)\in Q\_1\times Q\_2\times\\{1,2\\}$, where $q\_j$ represents the current state of $A\_j (j=1,2)$, and $i$ indicates in which automaton we will next progress. The initial state is $(q\_{01},q\_{02},1)$, representing the fact that each $A\_j$ is in its initial state $q\_{0j}$ and we want to first progress in $A\_1$. The accepting states are those $(q\_1,q\_2,1)$ with $q\_1\in F\_1$ and $q\_2\in F\_2$, i.e. both $A\_j$ accepting.

This leaves the transition relation. For $Mix\_1$ this involves taking one step in component $i$ and then toggling $i$ (this is also the reason for requiring $i=1$ in the accepting states, since the last step should be in $A\_2$). For $Mix\_2$, you can either toggle $i$ or take a step in component $i$ (note that this given an NFA, i.e. you still need to determinize).

# Answer
> 2 votes
Hint: This is very similar to $Mix\_1$, only you don't know when to jump from a part of the first word to a part of the second word. Use non-determinism to help you.

---
Tags: formal-languages, regular-languages, closure-properties
---


title: Multiple of Hamiltonian Cycles

text:
# Question
Title: Multiple of Hamiltonian Cycles
I'm currently confused whether a graph should contain strictly one distinct Hamiltonian Cycle. (given that **\[1,2,3,4,1\]** and **\[2,3,4,1,2\]** are the same).

I was wondering if, by definition, there can be multiple distinct Hamiltonian Cycles in a graph? something like **H1 = \[1,2,3,1\]** and **H2 = \[6,7,8,6\]**

can someone kindly confirm?

(*addt'l sources and references would really be great so I can dive in deeper*)

Cheers!

# Answer
Recall a Hamiltonian cycle visits each vertex of a graph exactly once. Thus, the cycles **H1** and **H2** in your second example can't be Hamiltonian cycles in the same graph.

In your first example, the two cycles could be distinct Hamiltonian cycles in e.g. the complete graph on 4 vertices. That is to say, there can definitely be multiple Hamiltonian cycles in a graph.

If you care about naming conventions, you can call two cycles that don't share any vertices *vertex-disjoint cycles*. Similarly, two cycles can be *edge-disjoint* if they don't share edges.
> 2 votes

---
Tags: graphs, hamiltonian-circuit
---


# Question
Title: where is all deleted data will go from memory system/internet?
where is all **deleted data** will go from a memory system ? if it is not deleting actually where it storing ? i am always wonder about this when we are sending something to a memory system it takes long time (depends up on usb port) and when we are deleting it not taking more than a bling of eyes and disappears actually where it goes ? \** deletion process is happening on both memory device and internet is same or different \** ? can we recover data from internet ?

# Answer
> 4 votes
Deleting is not necessarily destroying data. It can be done (much faster, indeed) by making it inaccessible. You can do it by erasing critical information from the data structures that are used to index the data you want to delete. How exactly this is done depends on how the storage device is organized (formatted).

# Answer
> 4 votes
First there is the answer already given by André Souza Lemos. The data need not be destroyed. It is usually sufficient to mark the corresponding space as unused in some table, so that the system will no longer try to read it: it considers that there is nothing stored there. But the data is often still there, often fairly easy to find, even when some key organization information has been destroyed. That is why deleting data is fast: it is not done, unless actually replaced by some other data in the same memory chunk (and even then ...), and that would take time as you expect.

Actually, back in history, the way MS office used to save documents on disk was such that it copied on disk large chunks of main memory of which it had used only some part. So the file thus created did contain whatever data was lying in that unused part of the chunk of memory when it was attributed to MS Office as work space.

So you saved an edited document on disk thus creating a file, and part of that file contained whatever junk was lying in the main memory of the computer in some subpart of what was attributed to Office. Then you send your innocuous document around, for example to invite friend to your daughter's birthday, and you find out much later that it contained also your credit card number, or a love letter to someone not your spouse, that you thought erased from your computer.

You cannot really rely much on your computer for destroying data it is not supposed to keep.

Now, for data in volatile memory, it is usually enough to turn off the computer. That is the case usually for the registers and main memory, but not for the disk.

So for data stored on disk, if you wand to destroy the information stored in a file, you have to identify the location of that file and store something different in the same location. This is not necessarily easy for the average person. Another possibility is to completely overwrite the disk, to make sure you do not miss any location. This make take some time when you have 5 TB, but there are applications to do it.

With that you are pretty safe from most eavesdropping. But not completely: I once read that disk are not precise enough to always write exactly on the same spot for a given address, so that, with very advanced tools, forensic investigators can read the former content of a disk that has been overwritten several times. I do not know how much is true.

There is probably a lot more to be said, and more precisely. But the conclusion is: if you want to keep your secrets safe: don't tell your computer. It tends to remember too much and occasionally to repeat what it knows.

---
Tags: memory-management, memory-hardware, memory-access, memory-allocation, shared-memory
---


# Question
Title: Is a single tape Turing machine equal in power to a Turing machine that can only move right?
I assume no, because a Turing machine that can only move right feels like it is not a Turing machine. But, I wonder if I can add a Reset to the right moving Turing machine that resets the what head is pointing at all the way to the left of the TM. However, doesn't this make it left moving??

hmm...

# Answer
> 1 votes
The usual answer would be that they are indeed much less powerful, somewhat like a finite state automaton, if I am not mistaken.

*But there is a catch*. Imagine a TM with *two heads*, one which is reading, another which is writing. Both only move right! If the reading head is always left of the writing head, the part of the tape in between can act as a queue, which makes the machine Turing complete.

---
Tags: complexity-theory
---


# Question
Title: Updating the MST of a graph G = (V,E) when decreasing the weight of one of the edges that is not part of the MST
You are given a weighted undirected graph G = (V,E). You have run Prim's algorithm and found the MST of this graph. Now you pick one edge that is not part of the MST and reduce its weight by some value. You now want to come up with a smart way to find the new MST of the graph.

My approach would be the following. Take this edge `(u,v)` that you changed and add it to your MST. Start from `u` and travel around in your MST until you end up back in `u`, since it is guaranteed that after inserting `(u,v)` you will create a cycle (MST is a tree). Then from the cycle that you found, remove the edge with the maximum weight.

I feel like this is correct but I don't know how to prove it. Can someone guide me?

Here's what I've tried:

My intuition about the problem is the following. Let's call T, the MST that we found before updating an edge (u,v). Now after updating this edge (u,v), let's just add it to our MST. What is the resulting structure? Since we connect two nodes that are part of the MST with an edge that was previously not in the MST, we create a cycle. Of course this indicates that some edge/edges need to go, since what we just created is not a valid MST. We can not remove any edges that are not part of the cycle that we just created, since this action would give us two components that are not connected. If we look at the cycle that we created, we can only remove exactly one edge and no more than that. Since we want to minimize the weight of all the edges part of the MST, we simply remove the edge with the largest weight. So in the end we get something that is definitely a spaning tree, and it is also minimal. Proving that it's spanning tree is trivial. To prove the latter, the edges that are not part of the cycle, should definitely be part of some MST (they are light edges of some cut), so it's ok to leave them there, as for the cycle removing the max weight will give a min total weight.

# Answer
> 1 votes
You are definitely on the right track. As D.W. notes, you have to prove two things:

1. The new tree is a spanning tree.
2. There is no spanning tree of lower total weight (i.e. minimality).

For (1), consider what it means to be a spanning tree:

* Every vertex must be a part of it (this is the spanning part).
* It must be a tree (i.e. a connected acyclic graph).

So with your construction, you have a starting MST $T$ for the graph $G$, and you create a new potential MST $T'$ for $G'$, which is $G$ with a single modified edge weight (which may or may not be the added edge).

* Is every vertex of $G$ (and hence $G'$) in $T'$?
* Is $T'$ connected?

For (2), you want to show that there's no other tree that is better. Proofs of this kind are normally done by contradiction. So start by assume there is a tree $R$ that is a spanning tree of $G'$ and has lower weight than $T'$, what would this imply?

In thinking about this consider what it means for $R$ to be different, and what this would imply for $T$, the original MST.

---
Tags: algorithms, greedy-algorithms
---


title: Chomsky Normal Form of |a|<|b|

text:
# Question
Title: Chomsky Normal Form of |a|<|b|
Hello Everyone I was hoping I could ask you to check to my work on this CNF, These are a pain to me and I want to make sure I'm doing it right the first time

```
The language:
     L = {w|w accepts |a|<|b|} i.e.abb, bab, b
    ____________
    The Grammar:
    S-> Tb,bT,SS,b
    T->aTb,bTa,TT,lamda
    ______________
    The CNF:
    S-> Tb,bT,SS,b
    T->aTb,bTa,TT
    *take out lamda* *I see no unit rules so we can skip a step*(right?)
    ______________
    S-> TB,BT,SS,B
    T->ATB,BTA,TT
    A->a
     B->b

    ______________
    S-> C,D,SS,B
    T->AC,DA,TT
    A->a
    B->b
    C->TB
    D->BT

```

I think this is correct but I am not confident. Thanks for looking!

# Answer
> 1 votes
In your last grammar you included some unitary productions like $S \to C \mid D \mid B$ so it is incorrect. Remember the steps to transform a CFG into CNF are:

1) Eliminate $\epsilon$ productions.

2) \[Optional\] Eliminate useless productions.

3) Eliminate unitary productions.

4) Adjust the resulting productions to meet CNF requirements.

You didn't have to replace $C \to TB$ in $S \to TB$ because it already meet the CNF requirements.

---
Tags: context-free, formal-grammars, normal-forms
---


# Question
Title: What is the minimal states for the language DFA?
> Let the language $$L = \\{ w: \text{ for any prefix } u \text{ of } w : \left|\\#\_o(u) - 2\cdot \\#\_1(u) \right| \le 2 \\}$$
>
> What is the minimal number of states for a DFA, accepting $L$?
>
> 1. $4$
> 2. $5$
> 3. $6$
> 4. $\infty$ (The language isn't regular)

Now, although the intuition says the answer is $\\#4$ it's actually a regular language and the minimal number of states is $6$ (answer $\\#3$).

I've tried to think about a construction for a DFA accepting $L$, unsuccessfully.

# Answer
> 2 votes
Here's a hint to get you started. To save typing, let $x=\\#\_o(u), y=\\#\_1(u)$. Make a DFA where the states correspond to the value $x-2y$ seen so far. You'll then have states $q\_{-2},q\_{-1},q\_0, q\_1, q\_2, p$ where $q\_0$ is the start state, $q\_{-2}, \dotsc, q\_2$ are final and $p$ is a "dead" state.

Then, for example, suppose you're in state $q\_1$ and see an input of $0$. Then, since $x-2y=1$ and you see another $0$, you'll now have $x$ increased by $1$ so now $x-2y$ is $2$ so on a $0$ you'll pass from $q\_1$ to $q\_2$. Similarly, on a $1$ you'll pass from $q\_1$ to $q\_{-1}$.

The prefix condition makes it easy to use our dead state $p$, since if you ever get there, you'll never leave (since any subsequent input will still violate the prefix condition that got you there). You can fill in the details: you get to $p$ from either $q\_{-2}$ or $q\_{-1}$ on a $1$ or $q\_2$ on a $0$.

Finally, note that without the prefix condition, the language is not regular.

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


# Question
Title: Assign numbers to letters with respect to lowest graph peaks
I have string which is composed of letters. I want to assign each letter a unique number (letters that repeats should have assigned same number as first unique letter occurrence) and plot those numbers on graph. X-axis will represent the particular letters of string (read from left to right) and y-axis will represent the particular value assigned to letter. The problem is that I want to have graph with minimum peaks. String can be long sequence with repeating letters. In other words I need to assign to letters such numbers that will cause that the plot change over time will be minimal.

So basically this is OK:

```
STRING
123456

```

But this not, because graph does not grows/decreases continuously and there are peaks e.g. between S-T, T-R, R-I and I-N (actually it fits criteria only for N-G)

```
STRING
162534

```

More complicated example: imagine string "STRINGS" and those two possibilities:

```
##############
# 1s example #
##############

Letter-Number mapping:
######################
STRINGS
6431256

Distances:
##########
S-T:2
T-R:1
R-I:2
I-N:1
N-G:3
G-S:1

Peak changes:
#############
2-1:T
1-2:T
2-1:T
1-3:T
3-1:T

###############
# 2nd example #
###############

Letter-Number mapping:
######################
STRINGS
1356421

Distances:
##########
S-T:2
T-R:2
R-I:1
I-N:2
N-G:2
G-S:1

Peak changes:
#############
2-2:F
2-1:T
1-2:T
2-2:F
2-1:T

```

Then the winner is 2nd example because it's maximum distance is less than the maximum distance in 1st example. I can imagine situations where both max distances can be same then the criteria should be the peak changes. In this case 2nd also beats 1st (F - does not change, T - change) because 1st is always changing and 2nd does not change in 2/5 cases

```
1st: TTTTT
vs
2nd: TFTFT

```

Is there any theory related to this? Is this even CS theory or some genetic algorithm or what problem set is this? Some library that already does this would be fine e.g. for python, perl etc.

PS: Sorry but I did not know which tags or what title describe this problem the best.

# Answer
This smells like it might be hard (e.g., NP-hard).

Therefore, I suggest solving it with a SAT solver. SAT solvers implement a number of clever optimizations. Rather than trying to devise custom optimizations for this specific problem, you might try using an off-the-shelf SAT solver: that might be a much more efficient use of your time. In particular, here's what I would try. I would formulate the problem as follows:

Input: a string $S$ with $n$ unique letters, an integer $d$

Question: is there an assignment that maps each letter to a different number in $\\{1,2,\dots,n\\}$, such that any pair of adjacent letters are mapped to numbers that differ by at most $d$?

You can then formulate this as a SAT instance, in a fairly straightforward way. For instance, you can use a one-hot encoding: introduce boolean variables $x\_{c,j}$, where $x\_{c,j}=$ True means that the letter $c$ is mapped to the number $j$. Now if letters $c,c'$ are adjacent in the string $S$, you get a constraint $\bigvee\_{|j-j'|\le d} (x\_{c,j} \land x\_{c',j'})$. You also get constraints forcing different letters to map to different numbers.

Finally, throw this to an off-the-shelf SAT solver. If it finds a solution, you know that distance $d$ is achievable. Otherwise, it's not: distance $d$ is unattainable. You can now iterate over $d=1$, $d=2$, $d=3$, etc., until you get the first solution. (You can also try binary search, but I suspect it might be less efficient.)

This doesn't account for peaks, because I couldn't understand your definition of the peak stuff.
> 1 votes

---
Tags: substrings, string-metrics
---


title: n-polygon lattice datastructure?

text:
# Question
Title: n-polygon lattice datastructure?
I'm trying to simulate a boardgame what can be played on a board with an arbitrary lattice, anything from triangles to heptagons to 37-sided regular polygons is allowed. Moreover the shape of the board is also arbitrary.

I need to represent this board in a data structure in which each tile has as its property a list of all its neighbouring tiles.

I was wondering if there is already some work done related to this that I might find helpful?

The way I'm trying to approach this problem is as follows: I first devise a coordinate system. Then I situate the virtual board within the coordinate system. Then I lay down the first tile and recursively lay down all neighbouring tiles until I cross the border. The approach is quite ugly and there is some uncertainty involved as I'm using angles and such to figure out the coordinates of each tile and it's all very messy. There must surely be a better way.

# Answer
The board you want to draw is a planar graph whose faces (enclosed areas between edges) are the polygonal tiles: call this $G\_\mathrm{b}$. The data structure you have in memory is a graph $G\_\mathrm{m}$ whose vertices are the tiles and whose edges are the adjacency relation on the tiles. This graph is known as the dual of $G\_\mathrm{b}$. So, you need to compute the dual of $G\_\mathrm{m}$ and use one of the algorithms for drawing planar graphs to draw that.

One possibe headache is that duals are not uniquely defined, as the Wikipedia article shows, so you might need to be careful to get the "correct" dual for your application. If you can't get that to work, another option would be to use a graph drawing algorithm to draw $G\_\mathrm{m}$ and then obtain the board by using the perpendicular bisector of each edge.
> 2 votes

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


# Question
Title: DFA which visit a specific state at least once
Given a DFA M that satisfies language A, how do I modify M such that a new language B consisting of all strings that are accepted by M and cause M to enter a specific state r at least once are satisfied by the modified DFA?

I try to remember whether state r is visited or not. But as I known, unlike turing machine, DFA does not have any memory.

# Answer
You can add the "have seen $r$" information as follows.

Based on the old DFA $A = (Q, \Sigma, \delta, q\_0,F)$ construct a new one $A' = (Q', \Sigma, \delta', q'\_0,F')$. State set of $A'$ equals $Q'=Q\times \\{0,1\\}$, which adds a bit to the original states.

In each step you mave along just like the original automaton, except when entering state $r$ when we set the bit to $1$.

Initial state $(q\_0,0)$: initial, not seen $r$. Final states $F' = F \times\\{1\\}$: final *and* seen $r$.
> 1 votes

# Answer
You can break the problem down into two parts: strings that make it to state $r$, and strings that, starting at $r$, make it to an accepting state.

To get a DFA $M'$ for the first one, we take $M$, make all the accept states non-accepting, and make $r$ an accept state, call this state $r\_{M'}$. So $M'$ accepts all strings that finish at $r$.

Then we can make a second DFA $M''$ that accepts all strings that start at $r$ and reach an accepting state of $M$. Take $M$, and make $r$ the start state instead of whichever state was the original starting state, call this state $r\_{M''}$.

We can then use the concatenation construction to get a DFA for $L(M') \circ L(M'')$, which is all strings which go from the start state to $r$, then to an accept state. To do this we take $M'$, remove $r\_{M'}$'s accept status, take $M''$, and make $r\_{M''}$ no longer a start state, then add an $\varepsilon$-transition from $r\_{M'}$ to $r\_{M''}$. This gives an NFA, which we can then turn into a DFA in the usual manner. In this case we can shortcut this just by identifying $r\_{M'}$ and $r\_{M''}$ (i.e. joining the two DFAs at those states).
> 0 votes

---
Tags: automata, finite-automata
---


# Question
Title: Can well-formed formulas in predicate logic for a given signature be recognized in LOGSPACE?
I read that visibly pushdown languages are supposed to model the typical simple formal languages like XML better than deterministic context free languages. The visibly pushdown languages can be recognized in LOGSPACE. I wonder whether the well-formed formulas in predicate logic for a given signature are a visibly pushdown language, or can at least be recognized in LOGSPACE.

Here is a typical well-formed formula in predicate logic, for the given signature $(f(\cdot,\cdot), g(\cdot))$:

$\forall x (f(x,y)=z \land g(z)=x)$

A corresponding context free grammar would be

> $P \to T=T$
> $P \to (P \land P)$
> $P \to (P \lor P)$
> $P \to \lnot P$
> $P \to \forall V P$
> $P \to \exists V P$
> $T \to V$
>
> $V \to x$
> $V \to y$
> $V \to z$
>
> $T \to f(T,T)$
> $T \to g(T)$

Some people prefer to use reverse polish notation:

$xyfz=zgx=\land x\forall$

A corresponding context free grammar would be

> $P \to TT=$
> $P \to PP\land$
> $P \to PP\lor$
> $P \to P\lnot$
> $P \to PV\forall$
> $P \to PV\exists$
> $T \to V$
>
> $V \to x$
> $V \to y$
> $V \to z$
>
> $T \to TTf$
> $T \to Tg$

Because I have now written down two explicit grammars, let the question just be whether these two grammars generate visibly pushdown languages, or can at least be recognized in LOGSPACE.

# Answer
> 2 votes
Yes, well-formed formulas in predicate logic for a given signature be recognized in LOGSPACE, at least for the two notations (grammars) given in the question!

The normal notation is indeed a visibly pushdown language, with $\Sigma\_c=\\{(\\}$, $\Sigma\_r=\\{)\\}$. When we encounter the symbol $($, then we push the number of still expected occurrences of of terms or proposition (and whether we expect terms or propositions) on the stack. When we encounter the symbol $)$, then we first check that exactly the expected number of terms or proposition occurred, then overwrite the counter by the value on the stack, and decrease it by one. The counter is finite, because its maximum value is the maximum arity of the signature, and zero is its minimal value, because we reject when the counter would become negative.

---

The given RPN grammar is also a visibly pushdown language, because the maximum arity of the given signature doesn't exceed two. You push on the stack the variables, pop from the stack for the binary function, the quantifier and the equality relation, and do nothing for the rest. What we actually push on the stack is the type (empty, term, or proposition) of the top element of the "real RPN" stack, before the new element is pushed. Convince yourself that we can always know this type (variable is not a type here).

Also RNP formulas for signatures with higher arity can be recognized in LOGSPACE, because they can be converted in constant time and space to an equivalent signature that whose arity doesn't exceed two, by using a pair constructor.

---
Tags: complexity-theory, formal-languages, first-order-logic
---


title: Inventory Routing - Subtour Elimination

text:
# Question
Title: Inventory Routing - Subtour Elimination
I'm trying to implement a Inventory Routing Problem with Branch-and-Cut. But I'm facing with an issue regarding subtour elimination. (http://www.danflash.com/files/irp.pdf)

The paper describes the constraint like this: $$\sum\_{i \in S} \sum\_{j \in S, j\<i} y^t\_{ij} \le \sum\_{i \in S} z\_{it} -z\_{kt} \quad S \subseteq M \quad t \in T \quad \text{for some} \ k \in S$$ And some page further I've found this: $k=arg max\_j\\{z\_{jt}\\}$ but no idea how to interpret this.

Where $y^t\_{ij}$ is $1$ when the edge is used from $i$ to $j$ at time $t$. And $z\_{it}$ is $1$ when vertex $i$ is visited at time $t$.

What is the exact definition of $S$? The set of all subtours or one specific subtour? Let say $M = \\{1, 2, ...,7\\}$ and $M' = \\{0, 1, ..., 7\\}$ ($M'$ with supplier/depot).

And the solution I get contains the following subtours: $0,1,3,0$ and $2,4,5,2$ and $6,7,6$

Know how would a pseudo code look like to implement this? And what is $k$?

My current solution look like this (implemented in C# with Gurobi solver). But I'm not sure if this should be implemented as a lazy constraint in the callback or adding the constraint after `model.Optimize()` if a subtour exists and call `model.Optimize()` again.

I did an implementation but I guess it's not worth to post it before I really understand the equation.

# Answer
> 1 votes
$S$ contains every subtour except the tour with the depot. And for each subtour a constraint has to be added.

The meaning of $k=argmax\_j\\{z\_{jt}\\}$ has been answered in https://math.stackexchange.com/questions/1290142/explanation-of-textrmargmax-jz-jt-and-how-to-implement-it/1290178#1290178

I solved this with a callback as soon as a subtour is found.

---
Tags: optimization, linear-programming, traveling-salesman
---


# Question
Title: Prove the language of numbers divisible by 3 is not regular using pumping lemma
I have a language $L$ that I think is not regular:

$L = \\{w\in \\{0,1,...,9\\}^\* \\; | \enspace w \enspace \text{is a decimal representation of a number divisible by 3}\\}$

I'm using pumping lemma in my proof. My main main idea is the following. I choose $w = 3$, according to the pumping lemma $w = xyz$ with $xy^iz$ where $i \in \mathbb{N}\_0$. But for $i=0$ we have $\varepsilon$ which is not in the language ($\varepsilon$ is not divisible by 3). Therefore the language is not regular.

Is my idea right?

# Answer
> 4 votes
You cannot choose any string for the pumping lemma. You have to choose one that is at least as long as the pumping distance of the language (which exists when it is regular), but you do not know which it is, so you have to assume it is some value named $p$ (or some other name) and you assume you have a well chosen string in the language that is greater than $p$.

Another point is that I would say that $\epsilon$ is not the representation of a decimal number, rather than say it is not divisible by $3$.

All this being said, modular arithmetics works pretty well with divisibility constraints, divisibility by a constant, I mean. And Finite Automata are usually friendly to modular arithmetics because it is defined on finite sets of values (or classes of numbers).

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