# Question
Title: Tutorials/resources for building a toy SMT solver
I've built a rudimentary SAT Solver from scratch, and wanted to do the same with SMT solvers as well.

While I've found two toy SMT Solver implementations in Haskell and Ocaml, but no tutorials or examples, which is a stark contrast from all SAT Solver tutorials out there.

Is there a resource for building a toy SMT Solver from scratch?

# Answer
Have a look at the material on Leonardo de Moura's website. For starters, I can recommend the talk he gave at the Aalto SAT/SMT Summer School in 2013 titled Internals of SMT solvers.
> 0 votes

# Answer
I think these slides give a foundation of building a SMT solver, somewhat
> 0 votes

---
Tags: smt-solvers
---


# Question
Title: What does deep binding mean for static scope?
When I self-study "Programming Languages: Principles and Paradigms, by Maurizio Gabbrielli, Simone Martini", I have a question: what does deep binding mean for static scope?

1. I learned the concepts of deep and shallow bindings for functional parameters from the following part in the book

> The general case, the one we want to analyse, is that of a language with functional parameters, nested environments and the ability to deﬁne functions at every nesting level. Let us consider the example shown in Fig. 7.13. The name x is deﬁned more than once, so it is necessary to establish which is the (nonlocal) environment in which f will be evaluated. Concerning this question, the reader will not be surprised if we observe that there are two possibilities for selecting the nonlocal environment to use when executing a function f invoked using a formal parameter h:
>
> • Use the environment that is active at the time when the link between h and f is created (which happens on line 11). We say, in this case, that the language uses a **deep binding** policy.
>
> • Use the environment that is active when the call of f using h occurs (which happens on line 7). In this case, we say that the language uses a **shallow binding** policy.
>
> ```
> {int x = 1;
>  int f(int y){
>      return x+y;
>  }
>  void g (int h(int b)){
>      int x = 2;
>      return h(3) + x;
>  }
>  ...
>  {int x = 4;
>   int z = g(f);
>  }
> }
>
> ```
>
> Fig. 7.13 Functional parameters
>
> **All common languages that use static scope also use deep binding** (because the choice of a shallow policy appears contradictory at the methodological level). The matter is not as clear for languages with dynamic scope, among which there are languages with deep as well as shallow binding. Returning to the example of Fig. 7.13, the different scope and binding policies yield the following behaviours:
>
> • Under static scope and deep binding, the call h(3) returns 4 (and g returns 6). The x in the body of f when it is called using h is the one in the outermost block;
>
> • Under dynamic scope and deep binding, the call h(3) returns 7 (and g returns 9). The x in the body of f when it is called using h is the one local to the block in which the call g(f) occurs;
>
> • Under dynamic scope and shallow binding, the call h(3) returns 5 (and g returns 7). The x in the body of f at the moment of its call through h is the one

The above example 7.13 makes me think that the concepts of deep binding and shallow binding only apply to dynamic scope but not to static scope.

But it also says "All common languages that use static scope also use deep binding", so I have the question: what does deep binding mean to static scope?
2. Later in the book, it seems to address my question in the following quote

> **Binding policy and static scope**
>
> We have already observed how all languages with static scope use deep binding. At ﬁrst sight it could rather seem that deep or shallow binding make no difference in the case of static scope. After all, the nonlocal environment of a function is determined from the (static) position of its declaration and not by the way in which it is invoked. In the case in Fig. 7.13, it is the scope (and not binding) rule that establishes that every invocation of f (whether direct, using its name, or indirect, using a formal parameter) is evaluated in the outermost nonlocal environment.
>
> In general, however, it is not like this. The reason for this is that there can be many activation records for the same function simultaneously present on the stack (this clearly happens when we have recursive or mutually recursive functions). If a procedure is passed out from one of these activations, it is possible to create a situation in which the scope rules alone are not enough to determine which nonlocal environment to use in invoking the functional parameter. As an example, we will discuss the code in Fig. 7.15, which, as usual, we assume was written in a pseudo- language with **static scope**.
>
> ```
> {void foo (int f(), int x){
>     int fie(){
>         return x;
>     }
>     int z;
>     if (x==0) z=f();
>     else foo(fie,0);
>  }
>  int g(){
>      return 1;
>  }
>  foo(g,1);
> }
>
> ```
>
> Fig. 7.15 The binding policy is necessary for determining the environment
>
> The heart of the problem is the (nonlocal) reference to x inside fie. The scope rules tell us that such an x refers to the formal parameter to foo (which, as it happens, is the only x declared in the program). But when fie is called (using the formal f), there are two active instances of foo (and therefore two instances of its local environment). A ﬁrst activation from the call foo(g,1), in which x is associated (to a location which contains) the value 1, and a second one from the (recursive) call foo(fie, 0), in which x is associated with the value 0. It is inside this second activation that the call to fie through f is made. The scope rules say nothing about which of the instances of x should be used in the body of f. It is at this point that the binding policy intervenes. **Using deep binding**, the environment is established when the association between fie and f is created, that is when x is associated with the value 1. The variable z will therefore be assigned the value 1.
>
> **In the case of shallow binding** (which, let us repeat, is not used with static scope), the environment would be determined at the time f is invoked and z would be assigned the value 0.

In example 7.15 of recursion, it seems to me that the book tries to explain how deep binding works for static scope. But to me, it actually explains how deep binding works for dynamic scope instead of static scope. So how does the example explain how deep binding works for static scope?

Thanks.

# Answer
> 2 votes
Admittedly, the parts dedicated to binding policies in the Programming Languages: Principles and Paradigms book could be more detailed. I'll try to convey some additional and contextual information, and answer directly to your questions along the way.

# Scope policies and binding policies

As described around chapter 9, scope policies and binding policies are effectively two separate, yet related, mechanisms for binding names to objects. I assume the notions of static scope and dynamic scope are already known, so I will delve directly into binding policies.

There are two binding policies

* Deep binding
* Shallow binding

and they are another level of variability beyond scoping rules; that is, once you've fixed the type of scoping rule (either static or dynamic) there could still be some uncertainty around the decision of which objects to assign to a given name.

## Static scope

For static scope, the *only* situation\[1\] I know of where this ambiguity could arise is that of a nested function definition, as in the following example

```
function f(function g (int), int y) {
    function h (x) {
        return x + y;
    }

    if (y == 0) {
        return g(1);
    } else {
        return f(h, 0);
    }
}

int y = 4;
function k (x) {
    return x * y;
}

{
    print(f(k, 1));
}

```

In this example, the occurrence of `y` in `h()` belongs to the non-local environment, and since we are using static scope that `y` must be the one declared as a formal parameter of `f()`. However, `f()` is also a recursive function, and **multiple occurrences of variable `y` could coexist at the same time**. Which "instantiation" of variable `y` should we refer to in the body of `h()` then? The static scope rule is not enough to answer to this question.

> The above example 7.13 makes me think that the concepts of deep binding and shallow binding only apply to dynamic scope but not to static scope.

No, deep binding and shallow binding can also mean a difference when applied to static scope. If you fix a static scope discipline then

* A deep binding rule means binding at the time when the formal function parameter is assigned to an actual function
* A shallow binding rule means binding at the time the function is called via the formal function parameter

To make this easier to understand, consider my former example.

### Deep binding

If we use static scope and *deep* binding, then

* `k()` reference to `y` refers to the global `y`, initially set to `4`. This binding remains the same even if `k()` is used as an actual function parameter, because static scope has greater "precedence" over any binding policy
* When `f()` is invoked, `g()` is initially set to `k()`. However, in the recursive call to `f(h, 0)`, it is later set to the internally defined `h()` function. **Since we are using deep binding**, `h()`'s `y` will be the one set to `1`

### Shallow binding

If we use static scope and *shallow* binding, then

* `k()` reference to `y` is the same as in the point before
* When `f()` is invoked, `g()` is initially set to `k()`. However, in the recursive call to `f(h, 0)`, it is later set to the internally defined `h()` function. **Since we are using shallow binding**, `h()`'s `y` will be the one found at the needed moment, which in our case is the one set to `0`

So my last few words should have given an answer to

> But it also says "All common languages that use static scope also use deep binding", so I have the question: what does deep binding mean to static scope?

Although I did not make an intentional effort, I might also have answered to

> So how does the example explain how deep binding works for static scope?

If I didn't, feel free to report it in the comments.

## Dynamic scope

I will not detail the impact of the two binding policies in the context of dynamic scope, since this was not called for in the question body. However, if I see this answer to raise enough interest, I may expand it to also include this point.

\[1\] I had the luck to ask to Maurizio Gabrielli himself, who was my professor, and he too could not find another occasion where this ambiguity could take place.

---
Tags: programming-languages
---


title: Explaining NFA in words

text:
# Question
Title: Explaining NFA in words
I have an NFA, and the question I am asked is :

Let \< \< . Now in simple English, express the language of the NFA to explain what type of strings are accepted by it.

In simple English, my answer is

The NFA accepts strings over alphabet {a, b, c} such that the last symbol appears twice.

Which I know is correct, however my problem lies in the question where "a \< b \< c". How does this affect my NFA and is my answer still correct? My answer seems really short for 6 marks.

# Answer
> 2 votes
The automaton accepts all non-empty strings in which the last symbol $\sigma$ appears at least twice, and all symbols appearing between its penultimate appearance and its last appearance are smaller than $\sigma$.

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


# Question
Title: Karger's min cut and tips on bounding nonlinear recurrences
I was recently working on an old qualifying exam problem asking us to generalize Karger's randomized global min cut algorithm to that of a global min $k$-cut. I recalled the strategy of running a recursive version of the randomized edge contraction algorithm to help with the shrinking the error probability and ultimately help with an efficient algorithm for getting the global min $k$-cut with probability $1/2$.

Most of the analysis was going well until I started to analyze the probability of success of the recursive algorithm. I found that this probability was ultimately described as $$P\_i \geq P\_{i-1} - \frac{1}{4} P\_{i-1}^2$$ where $P\_{i}$ is the probability of success on some call of the algorithm at level $i$ of the recursion tree, with a leaf having $i = 0$. One could show that the depth of the tree was $d = \frac{c \log\_2(n)}{(k-1)}$ for some constant $c$ and ultimately I was looking to lower bound $P\_{d}$. However, I struggled to lower bound this recurrence. I knew from studying the algorithm for a min cut that this recurrence should have the lower bound $P\_{d} = \Omega(1/\log(n))$. I wanted to try and show this but the best I got on my own was doing \begin{align} P\_{i} &\geq P\_{i-1} - \frac{1}{4} P\_{i-1}^2 \\ &\geq P\_{i-1}\left( 1 - \frac{1}{4}\right) \tag{ $P\_{i-1} \leq 1$ } \\ &= \frac{3}{4} P\_{i-1} \\ &\geq \left(\frac{3}{4}\right)^{i} P\_{0} \end{align} which, when we evaluate $P\_{d}$, gives us that \begin{align} P\_{d} &\geq (3/4)^{d} P\_0 \\ &= (4/3)^{-c \log\_2(n)/(k-1)} \\ &= n^{-\frac{c}{(k-1) \log\_{4/3}(2)}} \\ &\geq n^{-\frac{2.41 c}{(k-1)}} \end{align}

This is a much worse lower bound than what can be found. After this point, I investigated the original paper for the recursive randomized min cut algorithm. The trick they used was to perform a nonlinear change of variables to the recursion, something of the form $P\_{k} = 4/Z\_{k}$, where $Z\_{k}$ is the new recurrence variable. This change leads to a new recurrence of the form $$Z\_{k} \leq Z\_{k-1} + 1 + 1 / (Z\_{k-1} - 1)$$ Since $Z\_{k} = 4 / P\_{k} \geq 4$, this implies we can upper bound the above recurrence as $$Z\_{k} \leq Z\_{k-1} + 2 \leq 2 k + Z\_{0} = 2 k + 4/P\_{0}$$ which finally implies that indeed $P\_{d} = \Omega(1/\log(n))$. I see that this transformation worked, but I do not have intuition for why one might think to try such a transformation. Can anyone help me with that intuition? Are there any other useful tips for tackling bounds of nonlinear recurrences?

# Answer
First of all, let me explain why your estimate is lossy: when $P\_i$ becomes small, $P\_{i-1} - P\_{i-1}^2/4$ is very close to $P\_{i-1}$, and in particular, it doesn't decrease exponentially.

Since the function $x - x^2/4$ is monotone in the range $\[0,1\]$, if you solve the corresponding recurrence $Q\_i = Q\_{i-1} - Q\_{i-1}^2/4$ (with base case $Q\_0 = 1$), then $P\_i \geq Q\_i$.

Let us write the recurrence relation as $Q\_i - Q\_{i-1} = -Q\_{i-1}^2/4$. This is a difference equation which can be approximated by a differential equation $q' = -q^2/4$, with $q(0) = 1$. Using standard techniques, you can determine the solution, which is $q(i) = 4/(4+i)$. This suggests that $Q\_i \approx 4/(4+i)$, and so hints that $4/Q\_i$ is a useful quantity to look at.

Here is another way to estimate the recurrence. Write the recurrence as $$ Q\_i = (1-Q\_{i-1}/4) Q\_{i-1}. $$ In a range of $i$ where $Q\_i \approx \theta$, it takes $\Theta(1/\theta)$ steps to reduce $Q\_i$ by a factor of $1/2$. In particular, after $$ \Theta(1+2+\cdots+2^{\ell-1}) = \Theta(2^\ell) $$ steps, we reach $Q\_i \approx 2^{-\ell}$. This suggests that $Q\_i$ scales like $\Theta(1/i)$. With a little bit of work, this argument can be made completely formal, though it is hard to get a hold on the exact constant factor in this way.
> 3 votes

---
Tags: recurrence-relation, randomized-algorithms, minimum-cuts
---


# Question
Title: How can I make the following grammar unambiguous
Given the below ambiguous grammar how can I make it inambiguous and how can I prove the new modified unambiguous grammar is unambiguous? S -\> S + S | S − S | S ∗ S | S / S | (S) | x | y

My attempt: The ambiguity can be corrected by

S -\> S + T | T , T -\>T - M| M, M * N|N , N / Q | Q , Q-\> (I) | x| y|

But I'm unsure how to provide a proof for this and I do not know if the |x|y| will have an affect on making this grammar ambiguous. I was thinking I could do an induction proof but I'm unsure how I would begin.

# Answer
This is a typical ambiguous grammar for arithmetic expressions. You can write different unambiguous equivalent grammars. For example, if you use the traditional precedences and associativities;

$\begin{align\*} E &\to E + T \mid E - T \mid T \\ T &\to T * F \mid T / F \mid F \\ F &\to x \mid y \mid ( E ) \end{align\*}$

You could also go the way of APL: All operations the same precedence, associate to the right.

$\begin{align\*} E &\to T + E \mid T - E \mid T * E \mid T / E \mid T \\ T &\to x \mid y \mid ( E ) \end{align\*}$

The possibilities are almost endless.

To show the above aren't ambiguous isn't so easy.
> 2 votes

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


# Question
Title: Find the most frequent alphabet appearing in the given string. In case letter with same frequency, choose the one which comes first alphabetically
This is the desired result which I want:

# Answer
> 0 votes
Just use an array indexed by the characters, loop over the string increasing the respective count.

---
Tags: programming-languages, strings, c
---


title: Summation and big theta

text:
# Question
Title: Summation and big theta
Can anyone suggest a starter book or website where I can find information and examples of putting functions under summation signs into Big Theta. basic Arihmetic , geometric, Quadratic are fine , but I would like to work on examples like $$\sum\_{i = 1}^{\log n} i \cdot n \text{ or } \sum\_{i = 1}^{\log n} 10^i$$

# Answer
Take a look at Appendix A in the book "Introduction to Algorithms" by Cormen, Leiserson, Rivest, and Stein.

Besides you say that you'd like to know how to handle summations besides arithmetic and geometric series (and others) but the two examples you provide are (essentially) an arithmetic and a geometric series.
> 1 votes

# Answer
A nice, reasonably rigourous, self-contained text is Hildebrand's "Short Course on Asymptotics" (it goes into mathematics applications, not computer science). It covers quite a bit more than summations.
> 1 votes

---
Tags: summation
---


# Question
Title: How to evaluate a Kleene's Closure through CFG and attribute grammars
For a CFG with the production rules that can represent a regular expression. How can one calculate all the set of strings that regular expression would produce.

For T = {a, b,\*,(,)} and an arbitrary production rule I created to represent a simple regular expression

S-\>SS | S\* | (S) | a | b | ∅

What would be an attribute grammar which can calculate the set of all strings that the regex can evaluate.

For example if we generate b(a)\* Then the output generated by regular expression would be a set of infinte strings {b,baa,ba,baaa......} using set valued expression in the attribute grammar.

I am not sure how to represent set valued concatenation and Kleene closure.

# Answer
> 1 votes
Any "interesting" regular expression (i.e., one that includes Kleene star) represents an infinite set. Thus to "calculate the set of all strings" won't work so well. In a sense, the regular expression *is* a compact description of the language. What other kind of description do you expect to construct?

It is rather easy to construct regular expressions that represent very complex languages, that the reader needs to descypher to make sense of it.

# Answer
> 1 votes
The semantic rules of the attribute grammar "compute" the value of the expression to the left in terms of the values of the expressions to the right. With a grammar for regular expressions as you propose this is straightforward, but precisely because of that this can be confusing.

For instance the meaning of the rule $S\_0\to S\_1 S\_2$ is concatenation, and this operation is directly translated into that operation on languages: $S\_0.\text{val} = (S\_1.\text{val}) \cdot (S\_2.\text{val})$

\[I have indexed the variables of the rules for clarity.\]

Similarly for the Kleene star operation, here the syntactic notation $\*$ in the expression, and in the production rule, is translated into the semantic operation Kleene star on languages which has the intended meaning. Thus $S\_0\to S\_1^\*$ with semantic rule $S\_0.\text{val} = (S\_1.\text{val})^\*$

That's all.

Once however, in a compiler setting, I have seen a different approach. There the semantic value of the expression was not a language, but a finite state automaton (non-deterministic, with $\varepsilon$ rules). In that way the intended meaning of the expression is nicely captured in a computable fashion. The operations in the semantic rules are then the concatenation and star constructions on *automata*.

In that case, the operations you are looking for is Thompson's construction.

---
Tags: formal-languages, formal-grammars, programming-languages, attribute-grammars
---


# Question
Title: Constructing a NFA from a regular expression
I have the following regular expression $R=ab^\*(\epsilon \cup c) \cup c^\*a$ and I want to construct the NFA that accepts languages defined by that regular expression. I started by constructing the NFA that accepts $R=ab^\*(\epsilon \cup c)$

Next I tried to continue the concatenation part by adding the following to the NFA as follows:

Is that correct? is there a quick approach to construct NFA from long regular expressions?

# Answer
Your solution is nearly correct, however you need to remove the $c$-transition of $S\_0$ and the $a$-transition from $S\_0$ to $S\_2$ and add a new state, say $S\_3$, which is reached from $S\_0$ via an $\varepsilon$-transition, has a $c$-transition to itself and an $a$-transition to $S\_2$ (so that the word $cab$ is not recognized anymore, see benrg's comment below).

As for a general algorithm not that REs are built in a recursive manner by taking the symbols in your alphabet as "atoms" and then chaining them together using the basic operations $+$ (or $\cup$ as you denote it), $\ast$ and concatenation. A NFA accepting the same language can then be built in a similar manner:

1. If the RE is just an atom $\alpha$, consider the NFA with one $\alpha$-transition to an accepting state
2. Suppose our RE is of the form $XY$ where $X$ and $Y$ are REs themselves and let $\mathcal A\_X$ and $\mathcal A\_Y$ denote the NFAs representing $X$ and $Y$ respectively. A NFA for $XY$ can be constructed by taking the NFAs $\mathcal A\_X$ and $\mathcal A\_Y$ and adding $\varepsilon$-transitions from all accepting states of $\mathcal A\_X$ to the initial state of $A\_Y$ and making the states of $\mathcal A\_X$ not accepting.
3. Suppose our RE is of the form $X^\ast$ where $X$ is an RE. Take the associated NFA $\mathcal A\_X$ and add $\varepsilon$-edges from its accepting states back to the initial one, which also needs to be made accepting.
4. Suppose our RE is of the form $X + Y$ where again $X$ and $Y$ are REs. Take $\mathcal A\_X$ and $\mathcal A\_Y$ and add a new initial state that has $\varepsilon$-transitions to the initial states of $A\_X$ and $A\_Y$.

Of course, this algorithm does not produce "optimal" NFAs, but it is a simple and general procedure to generate an NFA which accepts the same language as some given RE.
> 1 votes

# Answer
This may not be computationally fast, but the most straightforward algorithm that I know for converting REs to NFAs is to use Brzozowski derivatives. This is so simple that it can be done by hand, and results in NFAs with a number of states that is linear (for the *usual* RE operators; more on this in a moment) in the number of terminal symbols.

To understand Brzozowski derivatives, we need to think of regular expressions as an algebra. The algebra in question is an idempotent semi-ring, with $0$ meaning the empty set, $1$ meaning the empty string, $+$ meaning set union and $\cdot$ meaning the concatenation product:

$$(A + B) + C = A + (B + C)$$ $$A + B = B + A$$ $$0 + A = A + 0 = A$$ $$0 \cdot A = A \cdot 0 = 0$$ $$1 \cdot A = A \cdot 1 = A$$ $$A \cdot (B + C) = (A \cdot B) + (A \cdot C)$$ $$(A + B) \cdot C = (A \cdot C) + (B \cdot C)$$ $$A + A = A$$

That last axiom is that addition is idempotent. And note that I'm going to drop the explicit $\cdot$ when it's clear or if I forget to add it.

To this, we add the Kleene closure operator $A^\*$, which I won't axiomatise here; see the Wikipedia page on Kleene algebra for details.

We also have terminal symbols drawn from an alphabet $\Sigma$. This is going to sound weird, but we're going to interpret these terminal symbols as *variables*. So, for example, we can define the "evaluation at zero" operator $A(0)$ as the regular expression $A$ with all of the terminal symbols replaced with $0$.

$$(ab^\* (1 + c) + c^\* a)(0) = 0\cdot 0^\* (1 + 0) + 0^\*\cdot 0 = 0$$

For any regular expression $A$, $A(0)$ simplifies to either $0$ or $1$.

And now, we can define a derivative operator:

$$\begin{eqnarray\*} \frac{\partial}{\partial x} 0 & = & 0 \\ \frac{\partial}{\partial x} 1 & = & 0 \\ \frac{\partial}{\partial x} x & = & 1 \\ \frac{\partial}{\partial x} y & = & 0, \hbox{if } x \ne y \\ \frac{\partial}{\partial x} (A + B) & = & \frac{\partial}{\partial x} A + \frac{\partial}{\partial x} B \\ \frac{\partial}{\partial x} (A \cdot B) & = & A(0) \cdot \frac{\partial}{\partial x} B + \frac{\partial}{\partial x} A \cdot B \\ \frac{\partial}{\partial x} A^\* & = & \frac{\partial}{\partial x} A \cdot A^\*\end{eqnarray\*}$$

Apart from one tweak to the product rule to deal with the fact that concatenation is not commutative, this looks exactly like a partial derivative operator. Note that the Kleene closure operator acts like exponentiation, where $e^0 = 1$ and $\frac{\partial e^{A}}{\partial x} = \frac{\partial A}{\partial x} e^A$.

The Brzozowski derivative has the following interpretation:

$$\frac{\partial E}{\partial a} = \left\\{\\,w\\,|\\,aw \in E\\,\right\\}$$

That is, it is the set of all strings in $E$ which start with $a$, with that $a$ removed.

This gives us the following identity:

$$E = E(0) + \sum\_{x \in \Sigma} x \frac{\partial E}{\partial x}$$

Remembering that terminal symbols are analogous to variables, this is just the Taylor expansion of the regular expression around $0$. But this identity is also an algorithm for the construction of a DFA or NFA state, since $E(0)$ is $1$ if $E$ is nullable, otherwise $0$, and the sum is the transitions.

You can do this using the definition of the derivative above, or use the following transformation $\mathbf{C}\[\]$:

$$\begin{eqnarray\*}\mathbf{C}\[0\] & = & 0 \\ \mathbf{C}\[1\] & = & 1 \\ \mathbf{C}\[a\] & = & a\cdot 1 \\ \mathbf{C}\[A + B\] & = & \mathbf{C}\[A\] + \mathbf{C}\[B\] \\ \mathbf{C}\[A^\*\] & = & 1 + \mathbf{C}\[A\cdot A^\*\] \\ \mathbf{C}\[0 \cdot B\] & = & 0 \\ \mathbf{C}\[1 \cdot B\] & = & \mathbf{C}\[B\] \\ \mathbf{C}\[a \cdot B\] & = & a \cdot B \\ \mathbf{C}\[(A + B) \cdot C\] & = & \mathbf{C}\[A \cdot C\] + \mathbf{C} \[B \cdot C\] \\ \mathbf{C}\[A^\* \cdot B\] & = & \mathbf{C}\[B\] + \mathbf{C}\[A\cdot(A^\* B)\] \\ \mathbf{C}\[(A \cdot B) \cdot C\] & = & \mathbf{C}\[A\cdot (B \cdot C)\]\end{eqnarray\*}$$

Note that $E$ and $\mathbf{C}\[E\]$ is the same language. Then we can find a NFA by applying this transformation to a regular expression, then recursively applying it to the transition states.

In your case:

$$\begin{eqnarray\*}q\_0 & = & ab^\* (1 + c) + c^\* a \\ & = & \mathbf{C}\[ab^\* (1 + c)\] + C\[c^\* a\] \\ & = & a \cdot (b^\* (1 + c)) + a \cdot 1 + c\cdot (c^\* a) \\ & = & a\cdot q\_1 + a \cdot q\_2 + c \cdot q\_3\end{eqnarray\*}$$

where:

$$\begin{eqnarray\*}q\_1 & = & b^\* (1 + c) \\ q\_2 & = & 1 \\ q\_3 & = & c^\* a\end{eqnarray\*}$$

If a $1$ appears in the sum. then the state is final, so $q\_2$, for example, is a final state with no outgoing transitions.

You only need to invent new states for regular expressions that don't already have names. So, for example:

$$\begin{eqnarray\*}q\_3 & = & c^\* a \\ & = & \mathbf{C}\[c^\* a\] \\ & = & a \cdot 1 + c \cdot(c^\* a) \\ & = & a \cdot q\_2 + c\cdot q\_3\end{eqnarray\*}$$

Note that this method never produces "epsilon transitions". Converting this into an algorithm to transform a regular expression to a DFA is straightforward, but I'll let you discover that for yourself.

One advantage of this algorithm is that it can be extended with other operators, such as set intersecction:

$$\frac{\partial}{\partial x} (A \cap B) = \frac{\partial}{\partial x} A \cap \frac{\partial}{\partial x}B$$

or set difference:

$$\frac{\partial}{\partial x} (A - B) = \frac{\partial}{\partial x} A - \frac{\partial}{\partial x}B$$

However, introducing these "negation" operators does not preserve the property that the final NFA is linear in the size of the original regular expression.

**EDIT**

You may have noticed that the $\mathbf{C}\[\]$ transformation can infinitely loop on pathological input involving $0$, $1$, and the Kleene star; try $\mathbf{C}\[1^\*\cdot a\]$ as an example. The simple fix is to simplify the regular expression first to remove as many literal mentions of $0$ and $1$ as possible, and second to remove redundant Kleene stars:

$$\begin{eqnarray\*} 0^\* & \mapsto & 1 \\ 1^\* & \mapsto & 1 \\ 0 + E & \mapsto & E \\ (1 + E)^\* & \mapsto & E^\* \\ {E^{\*}}^{\*} & \mapsto & E^{\*}\end{eqnarray\*}$$

I can't remember full set of simplifications, but they are fairly straightforward.
> 1 votes

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


# Question
Title: When can a deterministic finite-state-automaton (DFSA) along with its input sequence be said to be a part of another DFSA?
For a Finite State Automaton / Finite State Machine (FSM) $F$, that has an input alphabet, a set of possible states, an initial state, a set of possible final states and a state transition function, let a **finite** input sequence $S$ is given, such that at the end of this sequence the FSM enters a final state and stays in that state.

Can this FSM $F$ along with the input sequence $S$ be considered a separate FSM $F'$?

Analogous to this, can a Turing machine $T$ along with a finite tape $P$ be considered a separate Turing machine $T'$?

**What are the conditions, if any, for this to be true assuming it is true?**

Note: I expect a formal proof, or a reference/outline to a formal proof that proves that either of this can or cannot be done. Some theory related to this is also welcome.

**My research:**

### Closely related topic:

R. T. G. TAN (1979) Hardware and software equivalence, International Journal of Electronics, 47:6, 621-622, DOI: 10.1080/00207217908938690

I am aware of the principle of hardware and software equivalence, which states that a given task can be performed using hardware or software, i.e. **digital hardware and software are equivalent models of computation**. But I think my question is different from this one.

### Motivation:

* From this question ( Is there code below microcode? ) I think we can consider an FSM with its input sequence (microcode) to be a part of another FSM (the digital computer), but of course much more circuitry like Arithmetic and Logical Unit (ALU) and datapath is needed to make a computer. Microcode is used only for the control circuit.
* This answer *claims* the data in the RAM of a computer along with the CPU can be considered to be a part of a bigger circuit.

To quote:

> The circuit is fixed (it is the gates in the processor) and part of its input is data that depends upon the program you are executing (which is stored in the RAM of the computer). However, you could consider this a larger circuit where part of it is hardcoded (i.e., the program part of the input is hardcoded); then you can view a computer running a program as a big circuit with part that is universal and identical for all programs (the gates of the processor) and part that depends on the program (the hardcoded input), and this immediately gives a mapping from programs to circuits. The mapping is implemented by a compiler.

# Answer
It's not clear to me how to interpret "can be considered", so I'm going to identify one technical question that can be answered.

Given a FSM $F$ and an input sequence $S$, it is possible to build another FSM $F'$ so that the execution of $F'$ on the empty input is in one-to-one correspondence with the execution of $F$ on $S$ (and in particular, both end at the same end state(s); e.g., either $F$ accepts on $S$ and $F'$ accepts on the empty input; or $F$ rejects on $S$ and $F'$ rejects on the empty input).

The proof is a straightforward application of the product construction: we construct one FSM $F\_0$ that outputs the fixed sequence $S$, and then compute the parallel composition of $F\_0$ with $F$.

The following is also true: given a Turing machine $T$ and a fixed input $P$ (i.e., initial state of the tape $P$), then it is possible to construct another Turing machine $T'$ such that execution of $T$ on input $P$ has the same result as execution of $T'$ on any input.

Formal proofs with Turing machines are often tedious and uninformative, so it's easier to see how this is true by considering a real-world program. For instance, suppose we have Python code that defines some function `t()`:

```
def t(x):
    ...

```

and we have some fixed string `p`. Consider the following Python function `t'`:

```
def t(x):
    ...
def t'(x):
    return t(p)

```

Then it is easy to see that the behavior of `t'` on any input is equivalent to the behavior of `t` on input `p`. (Here we have hard-coded a lexical constant string in the place indicated with `p` above.) You can do the same thing with Turing machines, where the machine first writes $P$ on the tape, and then starts executing $T$, to define a Turing machine $T'$ that proves the claim above.
> 1 votes

---
Tags: turing-machines, finite-automata, computer-architecture
---


# Question
Title: Sorting algorithm for ranking hundreds of Images based on pairwise comparison
I am facing the task of designing an algorithm to rank some hundred of images (around 300). The ranking is to be based on pairwise comparison judged by human (done through Amazon mechanical Turk). I have read many papers on ranking inference based on a subset of all possible pairwise comparisons (e.g. Jamieson and Nowak 2011). But I think because I don't have many images, exact ranking should be achievable with properly designed pairwise comparison sequences using some sorting algorithm.

Nonetheless this is different from the standard array sorting in the sense that, comparison result is not known with certainty prior to arranging the pair for comparison and letting the human judge decide. Thus there is a bit of adaptive selection involved. Moreover since it is based on the perception of one human judge, no parallel processing is possible to expedite the sorting. What is worse, transitivity is not guaranteed. Therefore some standard sorting algorithms may not be applicable.

Would somebody please recommend some sorting algorithm for my task?

Many thanks!

# Answer
If you're actually using humans (e.g., MTurk) and there is any subjectivity at all, I expect that standard sorting algorithms may perform poorly. Standard sorting algorithms expect that there will be zero errors or mistakes in any of the comparisons. If a single comparison returns a faulty value, the sorting algorithm might fail badly. However, in practice, humans make mistakes; and if the rating task is subjective, humans don't always agree on all rating decisions. Consequently, I expect standard algorithms are likely to be a poor match.

If transitivity is not guaranteed, standard sorting algorithms are definitely not suitable.

There are better approaches that can tolerate some errors and mistakes and disagreements. For instance, you might be interested in the Bradley-Terry-Luce model; see https://cs.stackexchange.com/a/134416/755. It helps you infer an overall ordering, based on individual pairwise comparisons. That model does not support nontransitivity, though.

We could also consider how to choose which pairwise comparisons to make (i.e., the experiment design question, instead of the inference question). I don't know if there is literature on that; but Peer grading design - choosing a graph, to get accurate rankings/ratings might be of interest, and it might be worth checking Stats.SE or asking there about this aspect of the problem.
> 4 votes

---
Tags: algorithms, sorting
---


# Question
Title: SVMs - Fat (Margin) Boundary: Why is $\max\frac1{||\theta||}=\min \frac{ ||\theta||^2}{2}$?
I am trying to understand SVMs in depth watching lectures from MIT.

The professor to reduces the classification problem into an optimization problem. To do that, he first defines the decision and margin boundaries as following:

Note that $\frac1{||\theta||}$ is the distance between the margin boundaries and the decision boundary ($\gamma\_i$ is just the **signed** distance, but we don't care for this question).

We then proceeds to note that our goal is:

* To maximize $\frac1{||\theta||}$
* while minimizing the Hinge Loss

Now, it is apparent that these two terms will co-exist in the objective function we are trying to form $(1)$.

**The Objective Function** $$\text{minimize } J(\theta,\theta\_0) = \frac1n \sum\_1^n \text{HingeLoss}(\theta,\theta\_0) + \frac{\lambda}{2} ||\theta||^2 \quad (1) $$

Given the fact that he wants to create a minimization problem he describes the maximization of the distance to be equal to the minimization of it's inverse squared divided by 2, i.e: $$\max\frac1{||\theta||}=\min \frac{ ||\theta||^2}{2}$$

This does not make sense, as far as I can understand. In my mind this is the correct way of doing it:

$$\max\frac1{||\theta||}=\min||\theta||$$

Why did he insert a square and a division into the equation?

# Answer
> 1 votes
Minimizing $\\|\theta\\|$ is equivalent to minimizing $\\|\theta\\|^2/2$, in the sense that the minimum is achieved for the same value of $\theta$. Since our goal is primarily to find $\theta$, this substitution is not unreasonable.

Why was the substitution done? I don't know. Perhaps because it makes the resulting optimization easier; or just because it seemed simpler. Note that while $\\|\theta\\|$ might look "simpler", in some sense it is an uglier function, as it involves a square root, which can be messy to deal with. The way to figure out would be to understand the basic derivation using $\\|\theta\\|^2/2$, and then try replacing with $\\|\theta\\|$ and see if the same logic goes through or if there is a barrier.

---
Tags: optimization, classification, program-optimization, svm, quadratic-programming
---


# Question
Title: Assign few binary variables to make all polynomials identically zero
I have 50 polynomials $f\_i$ over binary variables $(x\_1,\ldots,x\_{100})$. Also $f\_i(0,0,\ldots,0)=0$ for any $i \in \[1,50\]$. I want to assign few variables so that all $f\_i$ will be identically zero. I want to assign number of variables as small as possible. Here assign means we will fix some variable either 0 or 1. Other will be binary variables. All are binary polynomial ring. If we fix all are zero, all polynomials will be zero identically. I want to reduce number of such assignment. Is there any way for this like using SMT etc? Kindly give your idea.

# Answer
I'll propose two algorithms.

# SAT

Every binary multivariate polynomial $f$ can be represented in the form

$$f(x) = \sum\_{S \in \mathcal{F}} \prod\_{i \in S} x\_i,$$

where $\mathcal{F}$ has one set per monomial of $f$, representing the variables included in that monomial. A multivariate function is identically zero iff all monomials have coefficient 0. So, we can express your problem as follows.

Let us represent the partial assignment by sets $M$, where $M$ indicates the set of variables that are are assigned and $v$ their values, and $\overline{M} = \\{1,2,\dots,100\\}\setminus M$ the complement of $M$. Then the condition is that after we make the partial assignment and simplify by collecting monomials, all monomials must have coefficient zero. This can be represented as

$$\Phi(M,v) = \bigwedge\_{R \subseteq \overline{M}} \bigg\[ \sum\_{\substack{S \in F,\\S\cap \overline{M}=R}} \prod\_{i \in S \cap M} v\_i = 0 \bigg\].$$

That's a huge logical formula, but it can be equivalently expressed with fewer clauses as

$$\Phi(M,v) = \bigwedge\_{S \in \mathcal{F}} \bigg\[ \sum\_{\substack{T \in \mathcal{F},\\S\cap \overline{M}=T \cap \overline{M}}} \prod\_{i \in S \cap M} v\_i = 0 \bigg\].$$

If $f$ has $n$ monomials, $\Psi(M,v)$ can thus be expressed as a sum of $n^2$ products of subsets of $v$. This can be expressed as a SAT formula of size $O(n^2)$, by introducing boolean variables to represent $M,v$ and applying the Tseitin transform.

Now your problem can be expressed as checking whether there exist $M,v$ such that

$$\Phi\_1(M,v) \land \dots \land \Phi\_{100}(M,v) \land |M| \le k,$$

where $\Phi\_i(M,v)$ is the formula corresponding to requiring $f\_i$ be identically zero. This can be checked with a SAT solver, and you can use binary search over $k$ to find the smallest $k$ for which this is satisfiable.

Unfortunately, if each $f\_i$ has $n$ monomials, I suspect this will lead to a SAT instance with a small constant times $5000n^2$ CNF clauses, which sounds awfully large for existing SAT solvers to handle.

There are some optimizations that might make this more practical:

* If we know that we are looking for an assignment to $k$ variables, the size of the formula for $\Phi(M,v)$ can be further reduced by additionally adding the constraint $|S \triangle T|\le k$ to the $T$'s we sum over, where $\triangle$ denotes the symmetric difference of sets.)
* It might be helpful to use CryptoMiniSAT or some other SAT solver with built-in support for XOR (as each sum is a large XOR of boolean variables).

I'm not sure whether this will be enough to make your problem practically solvable in this way, though.

# 2QBF

We can formulate your problem as an instance of 2QBF as

$$\exists m, v . \text{wt}(m) \le k \land \forall w . f\_1(m \\;?\\; v : w)=0 \land \dots \land f\_{50}(m \\;?\\; v : w)=0,$$

where $m,v,w$ range over $\\{0,1\\}^{100}$, $k$ is a parameter, $\text{wt}(m)$ represents the Hamming weight of $m$ (the number of 1's in it), $m$ is a mask indicating which variables are assigned, $v$ indicates the values of the assigned variables, $w$ represents an assignment to the other variables, and

$$(m \\;?\\; v : w)\_i = \begin{cases}v\_i &\text{if }m\_i=1\\ w\_i &\text{if }m\_i=0,\end{cases}$$

i.e., $m \\;?\\; v : w = (m \land v) \lor (\neg m \land w)$. If you can test satisfiability of this kind of 2QBF formula, you can use binary search over $k$ to find the minimum number of variables to assign to.

So, you could try applying standard algorithms for 2QBF to your problem. See https://cstheory.stackexchange.com/q/11022/5038. I don't know whether to expect that to be successful -- the problem size might be a bit large for this to work.

2QBF is harder than SAT and unlikely to be solvable with multiple queries to a SAT solver (see Is 2QBF in P^NP?).
> 0 votes

---
Tags: algorithms, binary, smt-solvers
---


# Question
Title: How can a machine with fixed output for all inputs be considered a Turing machine?
From this answer, and the comments that follow:

> To clarify, this machine T′ with the fixed output for all inputs is a Turing machine? – Shashank V M

> @ShashankVM, Yes, T′ is a Turing machine. – D.W.♦ (When can a deterministic finite-state-automata (DFSA) along with its input sequence be said to be a part of another DFSA?)

From what I understand, a machine with fixed output for all inputs is a Turing machine.

**Consider this thought experiment**, I have a "machine" which is a wall with a slit through which I can pass a tape in. The "output" of this machine is on the wall, i.e. it is painted on the wall as a fixed string $S$, which for the purpose of this experiment is "Hello". So no matter what is written on the tape, the output of this "machine" is "Hello". From what I understand this "machine" is a Turing machine.

Is my understanding correct or am I missing something?

Because I find it hard to believe that this wall with a slit can be considered a Turing machine, when a supercomputer is considered a Deterministic Finite State Automaton.

Also I cannot see how this "machine" can emulate any another Turing machine or do any **useful computation**.

# Answer
> 3 votes
There are many different Turing machines. Each one runs a fixed, hardwired program. Most Turing machines do nothing useful; many of them just halt immediately.

Some are universal, meaning that they can emulate any other Turing machine given a description of its hardwired program as part of their input, but most aren't. The machine that always prints "Hello" obviously isn't universal, but it is a Turing machine.

# Answer
> 3 votes
There's no notion of "can be considered to be a Turing machine". Something either is a Turing machine, or it isn't. There's a formal mathematical definition of what a Turing machine is: https://en.wikipedia.org/wiki/Turing\_machine#Formal\_definition

I never claimed that just because some process always produces the same output, that process must be a Turing machine.

There might be some confusion about Turing machines vs DFAs. A computer could be modelled as a DFA (if we treat its memory size as fixed), or it could be modelled as a Turing machine (if we imagine that it's possible to gain more memory; or we just don't care to make use of the fact that memory size is fixed). These two different ways to think about a computer have different advantages and disadvantages. I suggest reading Is a PDA as powerful as a CPU? and How many gates until Turing Complete and How does an automaton model a computer or something else? and How does an automaton actually "compute"?, as I suspect they get at the core issue you are struggling with.

---
Tags: turing-machines
---


# Question
Title: What is the correct algorithm to see whether N points lie on the same side of a line?
What I tried first was to find the equation of the line and then compare its y-intercepts with the y-intercepts of each point. I just need the proper approach to this algorithm.

# Answer
A quick theorem, in general:

> A hyperplane in $\mathbb{R}^d$ can be defined by a vector $\mathbf{v}$ and scalar $b$ as the set of points $\mathbf{x}$ such that $\mathbf{v}^T\mathbf{x} = b$. It splits the space $\mathbb{R}^d$ up into two half-spaces, one where $\mathbf{v}^T\mathbf{x} \geq b$ and one where $\mathbf{v}^T\mathbf{x} \< b$.

So in 2D, if your line is defined by $\mathbf{v}, b$, all you have to do is check whether either $\mathbf{v}^T\mathbf{x} \geq b$ or $\mathbf{v}^T\mathbf{x} \< b$ holds for all your points $\mathbf{x}$.

---

You are probably used to a line being defined as $y = ax + b$. Note that we have $\mathbf{x} = \begin{bmatrix}x\\y\end{bmatrix}$ (beware of the bold $\mathbf{x}$ as opposed to $x$).

Thus we can rewrite to a matrix equation:

$$y = ax + b$$ $$-ax + y = b$$ $$\begin{bmatrix}-a, 1\end{bmatrix}\begin{bmatrix}x\\y\end{bmatrix} = b$$ $$\mathbf{v}^T\mathbf{x} = b$$

and we recover the above form, where $\mathbf{v} = \begin{bmatrix}-a\\1\end{bmatrix}$.

Thus all we have to do to check is if your points are a list of $(x, y)$ pairs is if either $-ax + y \geq b$ or $-ax + y \< b$ for all of them.
> 1 votes

---
Tags: algorithms, c
---


# Question
Title: Which grows asymptotically faster, $\log \sqrt{n}$ or $4 \log n$?
I have been looking at the question as to which grows faster asymptotically; $\log \sqrt n$ or $4 \log n$. I have applied L'Hopitals rule and ended up with 1/8. This would imply that they grow at same rate.

Graphically $4 \log n$ is always above $\log \sqrt n$. Also from a perspective that $4 \log n$ is $\log n^4$ would imply intuitively that growth of $4 \log n$ is faster asymptotically

There appear to be contradictions.

# Answer
> 2 votes
The asymptotic growth of $4 \log n$ is referred to as $\Theta(\log n)$. You will have to look at the definition of asymptotic growth to see why that is the case, but *intuitively*, it is the growth of a function when we discard constant factors and only look at the function "in the limit".

You have found out that the difference between the two functions "is 1/8", which makes sense, and which would put these two functions in the same "growth class".

When it comes to $\Theta\left(\log ( \sqrt n ) \right)$, it is, as you likely have found out $$\Theta\left(\log ( n^{1/2} ) \right) = \Theta\left( \frac{1}{2}\log n \right) = \Theta\left(\log n \right).$$

---
Tags: asymptotics
---


title: Compiler Design Question

text:
# Question
Title: Compiler Design Question
$\text{Consider the following ANSI C code:}$

```
int main(){
 Integer x;
 return 0;
}

```

$\text{What will be the type of error?}$

$\text{a) Lexical}$,

$\text{b) Syntax}$,

$\text{c) Semantic}$,

$\text{d) None}$ $\tag {GATE-CS 2021}$

According to me, Syntax Analysis phase should detect the error as there is no grammar in C which produces `Integer x` or in tokenized form `id id`. Any help is appreciated. :)

# Answer
Your statement `Integer x;` is syntactically `identifier identifier;` which is a perfectly fine variable declaration. Semantically, the first identifier must be defined as a type, and the second identifier must not be defined as a variable in the same scope. The first condition fails, therefore ...

And you might want to download a copy of the C Standard to check if `int main()` is acceptable, or whether it must be `int main(void)`, which is preferable and might be required.
> 4 votes

# Answer
In *ANSI C* syntax, as you say, there is no such construct as `Integer`, but only `int`. So your compiler should highlight a Syntax Error.

The grammar would be something as:

```
keyword = int | void | return | ...
expression = keyword id

```

Since `expression` won't match any `keyword`, the compiler stops at syntactic level.
> 1 votes

# Answer
But unless we make sure that it is not a primitive data type, how can an error be detected? A syntax analyzer cannot differentiate between keyword and identifier right? only Semantic analyzer can do that once it realizes and reduces the statement into starting symbol, which is when we try to make sense of the program i.e. in semantic analysis phase?

The answer to this is most likely **SEMANTIC ANALYSIS**.
> 0 votes

---
Tags: compilers, gate-cs
---


# Question
Title: Is discrete math enough for computer science ? Or there other Math topics that I should also learn With it?
I want to learn computer science, SO is discrete math enough for computer science ? Or there other Math topics that I should also learn With it ?

I don’t have specific topic that I care more about than others (like cryptography) ,Just CS.

# Answer
Discrete mathematics, linear algebra, calculus, and probability are all used pretty much everywhere in computer science. Basically, discrete maths is the basis of everything, while linear algebra and calculus are used in specific areas of computer science, and there are various places you will see probability.

Probability is usually used to describe randomness in your algorithms, and therefore is used quite a lot. Basic knowledge of probability and expected value of random variables is usually enough.

Calculus is used mainly in optimization and machine learning problems (but you can still see it elsewhere).

Linear algebra, and specifically matrices from it are especially useful. You might not need the entire course for every application of it in computer science, but it will be very useful in machine learning.

I know there are other mathematical topics that *can* be useful for computer science, like group theory, but I don't have experience with them to tell you what they are used for.

Also, there is no need to learn everything at once! You will start the math topics appear only in more advanced courses.
> 8 votes

# Answer
In addition to the basic math knowledge, a solid grounding in Logic is necessary for tackling topics such as

While one could argue that Logic isn't math per se, the overall approach and formalism are almost the same. You may hear relatively less about these topics on the Internet, but they form the backbone of any respectable undergraduate CS study plan. Logic will also be invaluable in gaining an insight into how mathematical proofs work.

You may find some of these topics hard to learn on your own if you do not follow an appropriate study plan, so in the end it may make sense to enroll at a CS school.
> 6 votes

---
Tags: combinatorics, discrete-mathematics, mathematical-foundations
---


# Question
Title: What would happen in the variant of the Josephus problem in which people in odd-numbered positions are killed in each round?
What would happen in the variant of the Josephus problem in which people in odd-numbered positions are killed in each round?

For example, with $N=10$ people: $$ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 \to 2, 4, 6, 8, 10 \to 4 ,8 \to 8. $$

As you can see in the above example the killing starts from position $1$.

I was just curious to find out what would be the solution to this variant. I tried out different values of $n$ but could not find a proper algorithm.

# Answer
> 2 votes
Position $2^{\lfloor \log\_2 N \rfloor}$ is always safe since it is the position that maximizes the number of trailing zeros in its binary representation.

Claim: The person originally sitting in position $n$ is killed in the $i$-th round iff the binary representation of $n$ has exactly $i-1$ trailing zeroes.

Proof: By strong induction on $i$. If $i=1$ the claim is trivially true since $n$ has $0$ trailing zeroes iff $n$ is odd. If $i \> 1$, by induction hypothesis we have that all remaining people were originally sitting in positions whose binary representation has $i$ or more trailing zeros, i.e, those positions are exactly the integers in $S = \\{1, \dots, N\\}$ that are multiples of $2^i$. If $n=2^i k$ then there are exactly $k$ positions in $S$ smaller than or equal to $n$, i.e., $n$ is killed iff $k$ is odd.

---
Tags: algorithms
---


# Question
Title: Pumping Lemma Proof (Type of wcw language)
I have the language $L = \\{ dkd\space \mid d \in \\{a,b\\}^\*, k \in \\{a,b\\} \\}$ and i have to show that it's non-regular using the pumping lemma.

The structure of the language i think can be explained as (based on definition above) $\\{a^{n}b^{n}ca^{n}b^{n} \mid c \in \\{a,b\\}\\}$

Based on pumping lemma, it must have this 3 properties:

1. $\lvert y \rvert \gt 0$
2. $\lvert xy \rvert \le p$
3. $xy^iz\in L$ for all $i \ge 0$.

Based on that, i have $a^{p}b^{p}ca^{p}b^{p}$ and $ 4p+1 \ge p $ Based on 2nd property there must be 9 scenarios (i guessed that from the theory):

One of them should be this one:

1. x = $\\{a^{i}$} $\space $ y = $a^{p-i}$ $\space$ z= $b^{p}ca^{p}b^{p}$

Based on the 3rd property i can use $xy^{2}z$ = $a^{i}$$a^{p-i}$$a^{p-i}$$b^{p}ca^{p}b^{p}$ eventually giving me $a^{p}$$a^{p-i}$$b^{p}ca^{p}b^{p}$, the explaination is: it fails since $a$'s of the start arent the same (in number) with the $a$'s of the end.

If the above is correct how i find the other 8 scenarios and it does make any difference that my $c$ is ($a$ or $b$) instead of a single constant character?

# Answer
> 0 votes
> The structure of the language i think can be explained as (based on definition above) $\\{a^n b^n ~c~ a^n b^n |c \in \\{a,b\\} \\}$

As explained in the comments, this is a wrong inference. If

$$ L = \left \\{ d k d ~|~ d \in \\{ a, b \\}^{\*}, k \in \\{a, b\\} \right \\} $$

then $d$ can be any finite sequence (of any length) of $a$ or $b$ terminals. Recall that, for an alphabet $\Sigma$, Kleene star is defined inductively as

\begin{align} \Sigma^0 & = \\{ \epsilon \\} \\ \Sigma^n & = \\{ \omega a ~|~ \omega \in \Sigma^{n - 1}, a \in \Sigma \\} \\ \Sigma^{\*} & = \bigcup\_{n \ge 0}{\Sigma^n} \end{align}

So for example

$$ \\{ \epsilon, a, b, ab, ba, abab, abbb, baba \\} \subset \\{ a, b \\} ^{\*} $$

while instead

## $$ \\{ a^n b^n | n \ge 0 \\} = \\{ \epsilon, ab, aabb, aaabbb, \ldots \\} $$

To tackle your problem, I can recommend negating the Pumping lemma and then

* Fix an arbitrary $N \> 0$
* Take $\omega = a^N b a^N$ with $d = a^N$ and $k = b$
* Equate $\omega = xyz$ and note that it must be $|xy| \le N$ and $|y| \> 0$

Can you conclude your proof?

> We just chose our $\omega \in L$. We must show that, whatever our decomposition, $\exists k \ge 0. ~ x y^k z \not \in L$. Let $x, y, z$ be such that \begin{cases} \omega & = xyz \\ |xy| & \le N \\ |y| & \> 0 \end{cases} then, whatever $y$, for $k = 0$ you always have \begin{equation} x y^0 z = a^M b a^N \end{equation} with $M \neq N$. Thanks @plop for strenghening the proof.

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


title: Is $(^{1/2}) = \Omega(^{\sin(n)})$?

text:
# Question
Title: Is $(^{1/2}) = \Omega(^{\sin(n)})$?
As $-1 \<\sin(n) \< 1$, So $n^{\sin(n)}$ is bounded, but square root of $n$ tends to infinity. Is my logic correct? But from the other perspective, $1/n \leq n^{\sin(n)} \leq n$. I am confused.

# Answer
> 2 votes
First, let's unpack this. We say that $O(\sqrt{n}) = \Omega(n^{\sin n})$ if any function $f(n)$ which satisfies $f(n) = O(\sqrt{n})$ also satisfies $f(n) = \Omega(n^{\sin n})$. In particular, if $O(\sqrt{n}) = \Omega(n^{\sin n})$ then $\sqrt{n} = \Omega(n^{\sin n})$. If $\sqrt{n} = \Omega(n^{\sin n})$ then according to the definition, there exist $C,N\>0$ such that $\sqrt{n} \geq Cn^{\sin n}$ for all $n \geq N$. Let us assume that this is the case.

In what follows, I assume that the argument in $\sin n$ is measured in radians.

Since $2\pi$ is irrational, the sequence $n \bmod 2\pi$ is equidistributed in $\[0,2\pi)$. In particular, there are infinitely many $n$ such that $n \bmod 2\pi \in (0.4\pi,0.6\pi)$, and so $\sin n \geq 0.95$. For each such $n \geq N$, we have $$ \sqrt{n} \geq Cn^{\sin n} \geq Cn^{0.95} \Longrightarrow n \leq C^{1/0.45}.$$ Since there are infinitely many $n$ such that $\sin n \geq 0.95$, we can find one such $n$ which exceeds both $N$ and $C^{1/0.45}$, and so reach a contradiction. This shows that $\sqrt{n}$ is not $\Omega(n^{\sin n})$.

---
Tags: algorithms, time-complexity, asymptotics
---


title: Kohonen, 1 dimension, SOM, puzzle

text:
# Question
Title: Kohonen, 1 dimension, SOM, puzzle
We consider training one-dimensional open map of Kohonen with neurons in one-dimensional input space. We assume it is completed the phase of the device and the weights $w\_i$, $i = 1,2, \dots, N$, are placed in ascending order. (As we know, this provision will not change in rest of the training.) At each step of the training algorithm, to which one corresponds educational model x, we define the intervals Vi as its regions entrance area with the following property: if x belongs to the interval $V\_i$, then the neuron i emerges the winner. We denote by Vi the length of the interval $V\_i$.

• What is the length $V\_i$, $1 \<i \<N$, before the update?

During the update the rule $w\_i ’= w\_i + η (x - w\_i)$ applies, where $η \<1$. We denote by $c$ the winning neuron. What will be the length $V\_c$ after the update, in the following cases of neighborhood definition? The length $V\_c$ decreases or increases by the update?

1. Only the winner $c$, $1\<c\<N$ is updated.
2. The winner $c$, $1\<c\<N$, and the neighbor of $c-1$ are updated.
3. The winner $c$, $1\<c\<N$, and the neighbors of $c-1$ and $c + 1$ are updated

The lengths $V$ will be calculated as a function of the values of the weights $w$ and$ n$, $x$, as appropriate.As it turns out, the puzzle refers to nodes that have neighbors. The end nodes $1$ and $N$ are not considered.

KOHONEN MAP

# Answer
> 0 votes
"$If\ x \in Vi,\space then\space\space i = winner\space neuron$"

$V\_i = \frac {w\_{i+1} - w\_i}{2} + \frac {w\_i - w\_{i-1}}{2} \Rightarrow$

$V\_i = \frac{w\_{i+1} - w\_{i-1}}{2} \space\space\space (1)$

The update equation is:

$W\_{i(new)} = W\_{i(old)} + η(x-W\_{i(old)}) $$\space\space\space(2)$ , where $η$ = learning rate

From now on I will put a ' instead of "new" keyword

$\space\space\space\mathbf1.$ If only the winner's weights are updated then:

The length of $V\_c$ remains the same

$\space\space\space\mathbf2.$ The winner $c$, $1\<c\<N$, and the neighbor of $c-1$ are updated:

$V\_c' = \frac{w\_{i+1}' - w\_{i-1}'}{2} \Rightarrow$ $V\_c' = \frac{(w\_{i+1} +η(x-w\_{i+1}) - w\_{i-1})}{2}$, because of (2)

We know that $x\<w\_i+1$ because $x$ is closer to $w\_i$, as $i$ is the winner neuron. So the length $V\_c$ is getting smaller

$\space\space\space\mathbf3.$ The winner $c$, $1\<c\<N$, and the neighbors of $c-1$ and $c + 1$ are updated:

Similar to the previous case, we will use relation (1) combined with (2):

$V\_c' = \frac{w\_{i+1}' - w\_{i-1}'}{2} \Rightarrow$

$V\_c' = \frac {W\_{i+1} + η(x-W\_{i+1}) - W\_{i-1} - η(x-W\_{i-1})}{2}$

We know:

$w\_{i-1} \< x \< w\_{i+1}$ so

$\bullet w\_{i-1}' \> w\_{i-1} $ and $\bullet w\_{i+1}' \> w\_{i+1}$ $ \Rightarrow $

$w\_{i+1}' - w\_{i-1}' \< w\_{i+1} - w\_{i-1}$

Thus, length $V\_c$ is getting smaller

---
Tags: algorithms, machine-learning, neural-networks
---


# Question
Title: Probability of Attaining the/a Global Optimum
Suppose for a given optimization problem, $A$, the size of the search space $S$ is |$S$|.

If the fitness landscape defined by $A$ is unimodal, then there is clearly only one global optimum. Given that $G$ is the event "reach the global optimum", can we then infer that $P(G) = \frac{1}{|S|}$, where $P(G)$ denotes the probability of reaching the/a global optimum?

For $N$ ($N \< |S|$) such global optima (in the case of a multimodal landscape), the probability increases to $P(G) = \frac{N}{|S|}$

**Is this a valid argument or can we not conclude anything regarding the probability of attaining the/a global optimum on the basis of the number of optima and the size of the search space?**

I realize that often one cannot know in advance the number of global optima, but say, if the problem was to maximize a simple continuous function over some domain, then the function of interest could easily be plotted and the number of (local) optima examined.

# Answer
No, you can't infer that. You seem to be assuming that the optimization process tries one element of the search space, chosen uniformly at random, and hopes that it got lucky. But that's not how real optimization algorithms work. They try multiple solutions, and they're not chosen uniformly at random; they're typically chosen in some way that we hope is more likely to hit a good solution.

In general, you cannot conclude anything about the probability of hitting the optimum after some amount of optimization, without further information. The probability might be much larger than $N/|S|$ (e.g., if the optimization problem is easy or the optimization algorithm is effective on this kind of problem).

In the kinds of optimization problems we typically use a computer to solve, often you can't just "plot it out" as often we're working with a multidimensional search space.
> 0 votes

---
Tags: algorithms, optimization
---


# Question
Title: Polynomial-time linear-reduction from Directed Hamiltonian Path Problem to 3SAT
Is there a polynomial-time reduction from Directed Hamiltonian Path Problem to 3SAT which is linear in the number of vertices? That is, it reduces every directed graph $G$ with $n$ vertices to a formula $\varphi$ with at most $O(n)$ clauses within time at most $p(n)$ for some polynomial $p(n)$?

Since Cook Levin Theorem shows a reduction that proves 3SAT is NPC, almost all of the literature deals only with reductions **from** 3SAT, and only rarely one can find in the literature reductions **to** 3SAT.

After searching the web I found this and other cites that have *the other direction* of reduction (from 3SAT to dHamPath).

Referring to some source would be highly appreciated.

# Answer
> 1 votes
I don't know of a reference, but there's a standard reduction from Hamiltonian paths/cycles to SAT which is fairly well-known. The reduction from SAT to 3SAT is then done by introducing additional variables to break up clauses, e.g.:

$$v\_1 \vee \neg v\_2 \vee v\_3 \vee \neg v\_4 \Rightarrow \left( v\_1 \vee \neg v\_2 \vee X\right) \wedge \left( v\_3 \vee \neg v\_4 \vee \neg X\right)$$

Let $n$ be the number of nodes in the graph. Then define variables $x\_{i,j}$ where $i,j \in \left\\{1 \ldots n\right\\}$, where $x\_{i,j}$ is true if node $i$ appears in position $j$ in the Hamiltonian path.

Every node must appear somewhere on the path:

$$\bigwedge\_{i} \left( \bigvee\_{j} x\_{i,j}\right)$$

Every position in the path must be occupied:

$$\bigwedge\_{i} \left( \bigvee\_{j} x\_{j,i}\right)$$

No node appears on the path more than once:

$$\bigwedge\_{i} \bigwedge\_{j \ne k} \left( \neg x\_{i,j} \vee \neg x\_{i,k} \right)$$

No two distinct nodes occupy the same position:

$$\bigwedge\_{i} \bigwedge\_{j \ne k} \left( \neg x\_{j,i} \vee \neg x\_{k,i} \right)$$

Nonadjacent nodes cannot be adjacent on the path. If $E \subseteq N \times N$ is the set of edges:

$$\bigwedge\_{k \ne \left|N\right|}\bigwedge\_{(i,j) \not\in E} \left( \neg x\_{k,i} \vee \neg x\_{k+1,j}\right)$$

You can modify this in the obvious way if you're trying to find a Hamiltonian cycle.

On that, as a practical matter, if you are trying to find a Hamiltonian cycle and you intend to feed this to a SAT solver, you would normally assert a start node as another clause, e.g. $x\_{1,1}$, to reduce the search space. Obviously for Hamiltonian paths, you don't do that.

# Answer
> 1 votes
This paper: Linearly-growing Reductions of Karp's 21 NP-complete Problems does not show any linear reductions, but references my quasi-linear reduction of Hamiltonian Cycle to SAT, and SAT to 3-SAT has a linear reduction.

My reduction reduces a Hamiltonian Cycle problem (HCP) with n vertices and m directed edges to a Boolean Satisfiability problem (SAT) problem with approximately n.log2(m) variables and 2m.(log2(n)+1) clauses. It uses vertex numbering using a linear feedback shift register (LFSR) sequence together with variables identifying active edges, and simple algebraic constraints between a vertex number and its successors' vertex number based on active edges. The reductions from Hamiltonian path to undirected Hamiltonian cycle and from undirected Hamiltonian cycle to directed Hamiltonian cycle are linear.

Some other techniques are discussed here: In Pursuit of an Efficient SAT Encoding for the Hamiltonian Cycle Problem including using a binary adder sequence numbering.

Filar, J., Haythorpe, M., & Taylor, R. (2018). Linearly-growing reductions of Karp's 21 NP-complete problems. Numerical Algebra, Control and Optimization, 8(1), 1-16

A. Johnson. Quasi-Linear Reduction of Hamiltonian Cycle Problem (HCP) to Satisfiability Problem (SAT), IP.com, Disclosure Number: IPCOM000237123D, 2014

Zhou, N. F. (2020, September). In Pursuit of an Efficient SAT Encoding for the Hamiltonian Cycle Problem. In International Conference on Principles and Practice of Constraint Programming (pp. 585-602). Springer, Cham.

---
Tags: complexity-theory, time-complexity, np-complete, reductions, satisfiability
---


# Question
Title: Myhill–Nerode equivalence classes of $\{0^n1^n \mid n \in \mathbb{N}\}$
I am told to find the equivalence classes of the Myhill–Nerode relation of the language $\\{0^n1^n \mid n \in \mathbb{N}\\}$. For one, I know it has an infinite number of equivalence classes given that it's a non-regular language. Im not sure how to find all the equivalence classes and show how I got those equivalence classes.

# Answer
> 3 votes
Here is how to think of this question. The equivalence relation is determined by which extensions of the current word belong to the language. There are three cases:

* The current word is not a prefix of any word in the language. This happens if either the word is not in $0^\*1^\*$ at all, or if it is of the form $0^n1^m$ but $m \> n$.
* There is a unique extension of the current word which is in the language. This happens if the word is of the form $0^n1^m$ with $m \neq 0$ (and, to exclude the case above, $m \leq n$).
* There are multiple extensions of the current word which are in the language. This happens for words in $0^\*$.

Let us now get into more detail:

* If $w = 0^n$, then we can extend $w$ to a word in the language by adding $0^m 1^{n+m}$ for arbitrary $m \in \mathbb{N}$. Note that this set of extensions is different for every $n$.
* If $w = 0^n1^m$ where $0 \< m \leq n$ then there is a unique way to extend $w$ to a word in the language, namely by adding $1^{n-m}$.
* Otherwise, $w$ cannot be extended to a word in the language.

Accordingly, the equivalence classes are:

* $\\{0^n\\}$ for every $n \in \mathbb{N}$.
* $\\{0^{n+m} 1^m : m \in \mathbb{N}\\}$ for every $n \in \mathbb{N}$.
* Everything else.

---
Tags: finite-automata
---


# Question
Title: Why do we use DAG rather than trees to represent search space of a search problem?
I saw people use DAGs to represent the search space of a search problems like the travelling salesman problem. Why is this better than the tree representation? Is the reason to save memory space on the computer or can it reduce the computation time in some way?

I googled but I didn't find an answer, it would be great to have a simple explanation and a reference I can read as I would like to have a good understanding about why DAG approach is a better option.

# Answer
> 4 votes
A search algorithm is a recursive procedure which accepts an instance and a partial solution and attempts to extend it to a complete solution bit by bit. For example, consider a search algorithm trying to solve the eight queens puzzle. The search is initiated with an empty board. On any given position, the search algorithm attempts to place one more queen, in all possible ways. The search halts when a solution is reached.

We can describe the working of the algorithm as a tree. The root is "empty board". An internal node corresponds to a position with several non-attacking queens, and its children are positions with one more queen added. Leaves are solutions to the puzzle.

Consider a node at depth 2, consisting of queens at positions $x$ and $y$. This position can be reached in two ways: adding $x$ then $y$, or adding $y$ then $x$. This means that there are actually two identical subtrees at depth 2 describing the same board position. The second time we reach this position, there is no need to explore it any more. This can be implemented using *memoization*, a technique in which we remember that we have already explored this position, and now what the outcome is (memoization can be used more generally to compute functions). This corresponds to folding the search tree into a DAG by identifying nodes corresponding to identical positions.

Memoization is closely related to *dynamic programming*, which is one way to implement memoization. Roughly speaking, dynamic programming is a way of scanning the DAG in reverse topological order, so that whenever we get to an internal node, all of its children have already been explored.

---
Tags: complexity-theory, graphs, search-algorithms, search-problem, dag
---


# Question
Title: Multiple Variables in Asymptotic Notation
I am trying to understand the multiple variable definition of an asymptotic notation. Particularly the definition in Wikipedia. It's also discussed in Asymptotic Analysis for two variables? but I think the answer is wrong. At least it is just corrected in the comments and and referenced to a lengthy answer. What I look for is just the answer for my confusion of the example given here. Wikipedia says,

> Big $O$ (and little $o$, $\Omega$, etc.) can also be used with multiple variables. To define big $O$ formally for multiple variables, suppose $f$ and $g$ are two functions defined on some subset of $\mathbb{R}^{n}$.
>
> We say $f(\vec{x})$ is $O(g(\vec{x}))$ as $\vec{x} \rightarrow \infty$ if and only if $\exists M \exists C\>0$ such that for all $\vec{x}$ with $x\_{i} \geq M$ $\textbf{for some $i$}$ $|f(\vec{x})| \leq C|g(\vec{x})|$.
>
> ... For example, if $f(n, m)=1$ and $g(n, m)=n$, then $f(n, m)=O(g(n, m))$ if we restrict $f$ and $g$ to $\[1, \infty)^{2}$, but not if they are defined on $\[0, \infty)^{2}$, This is not the only generalization of big o to multivariate functions, and in practice, there is some inconsistency in the choice of definition.

What I don't understand is, if we only look for *some* $i$, why can't we use the domain $\[0, \infty)^{2} $? For example, if I only take the $n$ variable to infinity ($i$ is 0 in this case), then shouldn't it be fine and $f(n,m) \in O(g(n,m))$? Shouldn't the definition be not for *some $i$* bur rather for *all* $i$? Do I understand the notion of *for some* in the wrong way?

# Answer
Suppose that we consider $f(n,m) = 1$ and $g(n,m) = n$ as functions on $\[0,\infty)^2$. Assume, for the sake of contradiction, that $f(n,m) = O(g(n,m))$. According to the definition, there exist $M,C\>0$ such that $|f(n,m)| \leq C|g(n,m)|$ whenever $\max(n,m) \geq M$. In particular, this should hold for $(n,m)=(0,M)$, yet in this case $|f(n,m)| \> 1 \> 0 = C|g(n,m)|$.

The problem disappears if the domain is $\[1,\infty)^2$. Indeed, in this case we can take $M=C=1$, since $g(n,m) = n \geq 1 = f(n,m)$ for all $n,m \in \[1,\infty)^2$.

Perhaps the problem is with unpacking the definition. According to the Wikipedia definition, $f(\vec{x}) = O(g(\vec{x}))$ if there exist $M,C\>0$ such that the following holds:

> If $x\_i \geq M$ for some $i$, then $|f(\vec{x})| \leq C|g(\vec{x})|$.

Equivalently,

> If $\max(\vec{x}) \geq M$, then $|f(\vec{x})| \leq C|g(\vec{x})|$.

It should be noted that this definition is not standard, and one could think of other definitions. Two particularly natural alternatives are (i) requiring *all* entries of $\vec{x}$ to be large, and (ii) requiring the inequality $|f(\vec{x})| \leq C|g(\vec{x})|$ to hold for *all* $\vec{x}$.

(The second option is related to the fact that for functions $f,g\colon \mathbb{N} \to \mathbb{N}\_{\>0}$, the usual definition of $f=O(g)$, which is a special of the definition above, is *equivalent* to a definition which holds for *all* $n \in \mathbb{N}$.)
> 1 votes

---
Tags: asymptotics
---


# Question
Title: Are there any established methods for generating random graphs/networks that are both planar and meshlike?
There are well-defined methods for generating random graphs / networks that satisfy certain properties, including small-world graphs, scale-free networks, and totally random non-planar graphs. I am looking for methods to generate random graphs that (1) are planar, and (2) have the quality that they are arranged in a lattice-like or mesh-like pattern, such that all connections are "nearby" connections only, and local loops are ubiquitous.

I suppose one could start with an actual 2-dimensional rectangular lattice, and then start randomly moving or adding edges in ways that preserve the planarity.

Thanks in advance for any thoughts, or references to known methods!

# Answer
> 0 votes
You could take the Delaunay triangulation of a random set of points (or, if you want almost lattices, a perturbation of something regularly defined) and remove some edges if you want.

This won't give you a small-world graph, but no lattice-like thing would. If you want something like this, you'll have to have some fractal properties anyway (if the connections are "nearby", then you'll need a lot of connections to go far).

If you want something scale-free, you can generate a Delaunay triangulation hierarchy instead -- which is a beautiful and useful tool of computationnal geometry so you'll find lots of references. The idea is to have a Delaunay triangulation on a small number of point, and then a Delaunay triangulation inside each triangle, and again, etc.

---
Tags: graphs, randomness, planar-graphs
---


# Question
Title: Asymptotic complexity of $-\log(c^{1/n} - 1)$
What is the asymptotic complexity of

$$f(n) = -\log(c^{1/n} - 1)$$

for some constant $c \> 1$? I conjectured $O(\log n)$ and checking WolframAlpha does give $$\lim\_{n\to\infty}\frac{f(n)}{\log(n)} = 1,$$ but I haven't found a proof yet.

# Answer
For $c \gt 1$ we have $c^{1/n} - 1 \sim \frac{1}{n}\ln c$, which gives $$\lim\limits\_{n\to\infty}\frac{\log(c^{1/n} - 1)}{-\log(n)} = \lim\limits\_{n\to\infty}\frac{\log\ln c - \log(n)}{-\log(n)}=1$$

For proof brought approximation we can consider limit $$\lim\limits\_{x \to 0}\frac{e^x-1}{x} = \lim\limits\_{x \to 0}e^x=1$$ based on L'Hôpital, Taylor expansion etc. De facto it's derivative of exponent in point $0$.
> 3 votes

---
Tags: asymptotics
---


title: Power of adjacency matrix

text:
# Question
Title: Power of adjacency matrix
Let $G$ be a weighted graph with a weight function $w \longrightarrow \mathbb{R}^{+}$. Let $G'$ denotes the weighted matrix with adjacency matrix

$$A\_{G'} = \sum\_{i=0}^{k} (xA)^{i}$$

where $k$ is integer and $x$ is a variable.

I am not getting what is $A\_{G'}$ matrix? Is it contains all walks of length $k$ or is it something else?

# Answer
> 2 votes
As you probably know, $A^i\_{st}$ is the total weight of walks of length $i$ from $s$ to $t$. Since $$ \sum\_{i=0}^k (xA)^i = \sum\_{i=0}^k A^i x^i, $$ the $s,t$ coefficient of $A\_{G'}$ is $$ \sum\_{i=0}^k A^i\_{st} x^i. $$ This is a polynomial in which for $0 \leq i \leq k$, the coefficient of $x^i$ is the total weight of walks of length $i$ from $s$ to $t$.

---
Tags: graphs
---


# Question
Title: What does $\text{dom}(\Gamma)$ mean in the context of an inference rule?
In the wikipedia page on pure type systems, it gives the following inference rule:

> $\frac{\Gamma \vdash A : s \quad x \notin \text{dom}(\Gamma)}{\Gamma, x : A \vdash x : A }\quad \text{(start)}$

What does $\text{dom}(\Gamma)$ mean here? These are string rewriting systems, so $\Gamma$ is supposed to be a string of symbols, a purely syntactic object. I'm not sure what a "domain of a string" is.

# Answer
There are various ways to define contexts in type theories. In this style, we assume there is some infinite set of variable names $V$ and define the context $\Gamma : V \rightharpoonup S$ as a partial function from the set of variable names to the set of types. $\mathrm{dom}(\Gamma)$ is then the subset of $V$ on which $\Gamma$ is defined, i.e. the variables in the context $\Gamma$. To require that $x \notin \mathrm{dom}(\Gamma)$ is asking for $x$ to be a fresh variable for the context $\Gamma$.
> 3 votes

---
Tags: type-theory, term-rewriting
---


# Question
Title: Finding the minimum value of all subsets in a 2D array
Imagine a *N* by *M* 2D array of random positive integers and two coordinates (i1,j1), (i2,j2), which represent the upper-left bound and bottom-right bound of a subarray, respectively. Is there a efficient algorithm to calculate all the minimum values of each subarray?

```
[[4, 10, 9, 7],
 [9, 8,  1, 2],
 [1, 21, 3, 1]]

```

In this example of a 3 by 4 grid, if the two coordinates were (0,1) and (2,2), the minimum in this case would be 1, out of the values 10,9,8,1,21,3.

Other than the naive solution of finding all subsets and calculating the minimum in this subarray, which would be well beyond O(n^4), I have also considered using a method similar to prefix sum by creating a separate 2D array and storing the minimum from (0,0) to (i,j) at the value (i,j), but this issue here is you can't account for the overlap like you do in prefix sums.

Is there a way to account for overlap or another, more efficient algorithm?

Thank you!

# Answer
> 1 votes
In one dimension, looking for the maximum sum, this is solved by Kadane's algorithm. The referenced page does discuss some of the history and gives pointers to efficient solutions for the two-dimensional problem.

Bentley in his seventh "Programming Pearls" column (see e.g. here) discusses the one-dimensional problem in depth, devising ever more efficient algorithms for it's solution. Bentley's columns (and much more) are collected in his book "Programming Pearls" (Addison-Wesley, 2nd edition 1999).

---
Tags: algorithms
---


# Question
Title: Using Myhill Nerode to prove that a language is not regular
Prove that the language $A$ on $\\{0,1\\}$ containing all words for which the number of $0$s is equal to the number of $1$s is not regular.

I know one way to do it would be to show that the cardinality of $A / \mathbin \equiv$ is infinite. But how would I find the different equivalence classes and then show it has an infinite number of equivalence classes?

# Answer
> 1 votes
Let $L$ be your language and let $\equiv$ be the equivalence relation defined by $x \equiv y$ iff $x \in \Sigma^\*$ and $y \in \Sigma^\*$ have no distinguishing extension (a distinguishing extension is a word $z \in \Sigma^\*$ such that exactly one of $xz$ and $yz$ belongs to $L$).

Given $i,j \in \mathbb{N}$ with $i \< j$, $0^i$ and $0^j$ cannot belong the same equivalence class since $1^i$ is a distinguishing extension for them: $0^i 1^i \in L$ but $0^j 1^i \not\in L$.

This shows that $L/\mathbin\equiv$ is not finite, and hence $L$ is not regular.

---
Tags: finite-automata
---