# Question
Title: Regular expression (ab U a)* to NFA with two states (Sipser)?
In the 3rd edition of Sipser's *Introduction to the Theory of Computation* (example 1.56, p.68), there is a step-by-step procedure to transform (ab U a)\* into a NFA. And then the text ends with: *"In this example, the procedure gives an NFA with eight states, but the smallest equivalent NFA **has only two states**. Can you find it?"* Nope. I can't. After a good deal of head scratching, I've convinced myself that it's not doable. But being a novice, I'm probably wrong. Can anyone help? Thanks!

# Answer
Mouse-over the yellow box to see an NFA that accepts the language.

>
> 6 votes

# Answer
One way to approach this problem is to use Chang's method. This method produces NFAs with the following properties:

* The number of states is equal to the number of terminal symbols in the input regular expression.
* There are no lambda/epsilon transitions.

It's also simple enough that you can do it by hand for modest regular expressions.

Now you may have noticed that there are in fact three terminal symbols in your regular expression $(ab \cup a)^\*$; two $a$'s and a $b$. However, if you allow the "optional" operator $?$, you can easily get it down to two:

$$(ab?)^\*$$

Chang's method is a great substitute for Thompson's method (which is what you probably know) most of the time. About the only thing it can't handle cleanly is the lex trailing context operator (which is a hack anyway).

---

C.H. Chang, *From Regular Expressions to DFAs using Compressed NFAs* (1992). http://ftp.cs.nyu.edu/web/Research/Theses/chang\_chia-hsiang.pdf
> 2 votes

# Answer
This question is a special instance of the following question. Given a finite sequence of words $u\_1, ..., u\_k$, find an NFA for the language $L = \\{u\_1, ..., u\_k\\}^\*$. The so-called *flower automaton* gives a simple construction. Just draw a flower with $k$ petals with the initial state and unique final state in the center. Now spell the words on the petals (one word per petal) just like in Rick Decker's example. This gives you a NFA with $|u\_1| + |u\_2| + \dotsm + |u\_k| - k + 1$ states. In your case, $u\_1 = ab$, $u\_2 = a$, so $|u\_1| + |u\_2| - 2 + 1 = 2$.

This construction is interesting when $\\{u\_1, ..., u\_k\\}$ is a *length-variable code*, which means that $\\{u\_1, ..., u\_k\\}^\*$ is a free monoid. In this case, the NFA is not a DFA, but it is unambiguous: every accepted word has only one accepting path.

EDITED. Just changed "David's example" to "Rick Decker's example". In any case, I mean the NFA in the yellow box.
> 2 votes

# Answer
Hint: the language is (almost) the set of all strings in $\\{a,b\\}^\*$ that don't have two consecutive $b$'s. So all you need to remember is whether or not the last character you saw was a $b$.
> 1 votes

# Answer
Ask yourself the following questions:

1. Do I know any way to systematically transform regular expressions into finite automata?

*Yes:* Do so, go to 2.
*No:* Look into the textbook and go to step 1, or be creative (see other answers)¹.
2. Is the automaton small enough?

*Yes:* Cool, done!
*No:* Go to 3.
3. Do I know a way to make finite automata smaller?

*Yes:* Apply it and go to step 2.
*No:* Look into the textbook and go to step 3.

Follow-up question: do you see why there is an infinite loop in this algorithm if and only if the problem is ill-posed, that is there is no such automaton?

*Yes:* Congrats, you have understood why the class of regular languages (and similar ones) are oh so nice.
*No:* Off to the textbook you go!

---

1. While being creative is nice, note that if you don't use algorithms proven to be correct, it's *you* who have to prove that your automaton is correct.
> 1 votes

# Answer
I think the following NFA would be correct:

```
N = ({q1, q2}, Sigma, delta, q1, {q1, q2})
Sigma = {a,b}
delta(q1, a) = {q1, q2}
delta(q1, b) = {}
delta(q2, a) = {q1}
delta(q2, b) = {q1}

```

But I'm not sure if q2 can be an accept state or not. In Rick's answer q2 is not an accept state, but I don't see why it can't be an accept state, because the only way to get to q2 is to have at least 1 a in your string, and if you have 2 consecutive b's then you'd get nowhere, so I don't see why q2 can't be an accept state.
> 0 votes

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


# Question
Title: Show that the language of words with even sum of positions of a letter is regular
Let $\Sigma=\\{a,b\\}$, and let $S(a)$ be sum of the positions of $a$ of string $S$. I want to prove $$L=\\{S\in \Sigma^{\*} \mid S(a)=0(\bmod 2)\\}$$ is regular.

What I was thinking is to do somehow keep track of sum of positions of $a (\bmod 2)$ For that I was thinking to do like take set of states as $\\{0,1\\}\times \\{0,1\\} \times \\{0,1\\}$. And starting state $\\{0,0,0\\}$. My aim to is to keep track sum of positions of $a$ at first component. So starting from initial state, if it read consecutive $x,b$s then it will go to $(0,0,x(\bmod 2))$ then after reading $y,a$s it goes to $(xy+y(y+1)/2(\bmod 2),y(\bmod 2),x(\bmod 2)$ after reading $z,b$s it goes to $(xy+y(y+1)/2 \bmod 2),y(\bmod 2),(x+y)z+(x+y)(x+y)/2(\bmod 2)$ ... and so on. And set accepting state ${0}\times {0,1}\times {0,1}$. I believe its working but I don't understand how to define on each state.

# Answer
If the sum of positions at which $a$s occur is even, that just means that there are an even number of $a$s in odd positions. It's straightforward to design an automaton to accept this criterion: it's a minor variant of requiring an odd number of $a$s.
> 2 votes

# Answer
You could do this with 4 states, interpreted as

1. Currently at an even position in the string and the sum so far is even
2. Currently at an even position in the string and the sum so far is odd
3. Currently at an odd position in the string and the sum so far is even
4. Currently at an odd position in the string and the sum so far is odd

Now it's easy enough to fill in the transitions. For example, if we're currently at an even position and the sum so far is even (i.e., in state 1), then after reading an $a$ at the position we'll find ourselves still with an even sum and will have advanced to an odd position. Formally, we have the transition $\delta(q\_1, a) = q\_3$. The same reasoning gives $\delta(q\_1, b) = q\_3$ as well. It's not hard to fill in the rest of the transitions and to determine the final states and the start state (which will depend on whether you start numbering positions at zero or one).

Cute problem, by the way.
> 1 votes

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


# Question
Title: Linear-time algorithm for solving a set of inequalites
We have a set $A$ of $n$ distinct numbers. We want to determine for all $x,y,z \in A$ whether the following relations hold.

$$ x+y\>z\qquad x+z\>y\qquad y+z\>x $$

Anyone could describe $O(n)$ Algorithm?

# Answer
for this algorithm it's enough to check sum of two smallest element is bigger than the maximum element.

We find Min1, Min2, Max.

if Min1 + Min2 \< Max there is no. O(n) else all of them is true.
> 3 votes

---
Tags: algorithms
---


title: Converting generalized NFAs to NFAs

text:
# Question
Title: Converting generalized NFAs to NFAs
I came across generalized nondeterministic finite automata (GNFAs) in Sipser's *Introduction to the Theory of Computation*. These are automata where transitions are labelled with regular expressions, rather than single symbols from the alphabet. I thought he would explain why GNFAs are allowed. I mean, an appropriate explanation would be that GNFAs are equivalent to NFAs, or GNFAs are equivalent to DFAs or some such argument. But I couldn't find any such explanation in the book.

Online, I read in this article that you can convert a GNFA to an NFA as follows:

> For each transition arrow in the GNFA, we insert the complete automaton accepting the language generated by the transition arrow’s label as a “subautomaton;” this way, we can replace each regular expression by a set of states and character transitions

How is the automaton inserted?

Let's say we have a GNFA with an arrow going from state A to state B labelled with a regular expression R. To convert this GNFA to an NFA, do we get rid of that arrow, instead, take NFA N that recognizes L(R), and create an arrow from A to the start state of N labelled with the epsilon symbol, then create arrows from the accept states of N to B, each also labelled with the epsilon symbol?

Of course the accept states of N would no longer be accept states in the new machine, would they?

I know that GNFAs are equivalent to NFAs but I need a convincing proof, not just a short paragraph mentioning their equivalence.

# Answer
> 3 votes
You are correct in your understanding of the construction: For every transition arrow, say from state $A$ to state $B$ in the GNFA labeled by a regular expression $R$, you replace that transition by the NFA, $N$, for $R$, with an $\epsilon$-transition from $A$ to the start state of $N$ and $\epsilon$-transitions from the final states of $N$ (which you then "un-finalize") to state $B$. Do this for every transition in the GNFA and you'll wind up with an ordinary NFA.

To show that the two accept the same language, it's enough to rely on the previous result (Lemma 1.55 in Sipser) that any regular expression denotes a language that is recognized by a NFA.

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


# Question
Title: Probabilistic hardness of approximation or solution of NP-hard optimization problems under a probabilistic generative model for input data
So in biology (DNA sequences), sequence alignment is a generalization of longest common subsequence where an alignment of two sequences is scored typically with a linear function of how many spaces are inserted into each sequence and how many times each possible pair of aligned characters appears in the alignment. Just like longest common subsequence, finding the optimal alignment of two strings under an arbitrary linear scoring scheme can be solved in quadratic time using dynamic programming. (Needleman-Wunsch algorithm). The longest subsequence problem and variants that use linear scoring schemes and ask for the optimal multiple sequence alignment are NP-hard when the number of input strings is not fixed.

However, in biology, there is a probabilistic generative model that generates related DNA sequences. Starting with an unknown root ancestor DNA sequence, bifurcations occur that create two daughter sequences (species) that are independently derived from the ancestral sequence by potentially adding some characters in random locations, deleting some characters, and changing some characters. Then the bifurcations continue with additional changes at each level until the modern day DNA sequences of extant species are obtained. Then we want to align the modern day species' sequences (e.g. find the longest common subsequence in the simplest case) without knowing the exact ancestral sequences. In this case, fossil records can help identify the bifurcation events and estimate the sequence mutation rates after each bifurcation. So a reasonable estimate of the generative model that generated the related modern day DNA sequences can sometimes be obtained.

Now, my question is, for such an NP-hard optimization problem with a well-defined probabilistic generative model that generates input data, has anyone studied the hardness of finding either an optimal or nearly optimal solution, where either the worst-case or expected running time depends on the parameters for the model that generates the input data? For example, if DNA mutation and insertion/deletion rates are very low for a particular group of species, then it should be fairly easy to get at least a nearly optimal alignment of all the DNA sequences using partial alignments and pruning and heuristics, without resorting to a full-blown exponential time solution.

# Answer
> 3 votes
Here is a similar recent example due to Mossel et al. There are $n$ vertices which are partitioned randomly into two classes. Two vertices of the same type are connected with probability $p$, and two of opposite types with probability $q$. For what values of $p, q$ can we recover the partition with high probability (with respect to $n$)? It turns out that if $p$ and $q$ are too close then it is statistically impossible, and otherwise a simple algorithm succeeds with high probability.

The question you are asking is very specific, and the answer likely depends on the exact model and its parameters. It seems likely that for a low mutation rate, some iterative algorithm should work, perhaps even provably (with high probability).

One way to formulate this question more concretely is to come up with constraints on the relations between the sequences, constraints that hold with high probability. It could be that for an appropriate choice of constraints, the problem becomes feasible.

---
Tags: complexity-theory, reference-request, np-hard, approximation, average-case
---


# Question
Title: How to find degree of polynomial represented as a circuit?
I know very little about arithmetic circuits, so maybe it is something well-known.

Given a small circuit consisted of $\\{1,x,-,+,\*\\}$ defining one variable polynomial. Let be additionally known that degree of this polynomial does not exceed $d$ and all the coefficients are small. I wonder if exists a fast way to find actual degree of this polynomial? Using FFT and some small field, one can do it in $O(d)$ time (regardless $polylog$ factors), but this time is sufficiently to reconstruct the the entire polynomial, so I hope computing degree only can be done more efficient.

# Answer
If the coefficients are small, then for large $x$ the polynomial is roughly equal to $Cx^d$. If you plug in both $x$ and, say, $2x$, then the ratio should be roughly $2^d$. Given bounds on the coefficients and the degree, this method can be made rigorous.

Another idea uses difference sequences. For a polynomial $P(x) $, the polynomial $P(x+1) - P(x)$ has degree smaller by one, the polynomial $P(x+2)-2P(x+1)+P(x) $ has degree smaller by two, and so on (in general, the coefficients are binomial coefficients with alternating signs). Using polynomial identity testing you can find the degree by binary search. This seems less efficient than your approach.
> 2 votes

---
Tags: algorithms, circuits, polynomials
---


# Question
Title: Check whether it is possible to turn one BST into another using only right-rotations
Given two binary search trees T1 and T2, if it is possible to obtain T2 from T1 using only right-rotation, we say that T1 can be right-converted to T2. For example, given three binary search tree T1, T2 and T3:

For example, given three binary search tree T1, T2 and T3:

```
 Tree 1                Tree 2              Tree 3
    a                    b                   a
   /                    / \                 /
  b                    d   a               d
 / \                      /                 \
d   c                    c                   b
                                              \
                                               c

```

T2 can be right-converted from T1, T3 can be right-converted from T1. But T3 cannot be right-converted from T2, T2 cannot be right-converted from T3.

Given two arbitrary BST, how to determine whether they are right-convertible with respect to each other?

# Answer
> 6 votes
If $T\_1$ and $T\_2$ don't encode the same sequence, they are not right-convertible into each other (obviously). This can be tested in linear time by inorder traversal of both trees.

The following procedure tests, if $T\_1$ can be right-converted into $T\_2$:

* If both trees are empty, $T\_1$ is right-convertible into $T\_2$.
* Right rotations move the root of the left subtree to the root of the complete tree. Thus, only nodes on the left flank of the tree can be rotated to the root. If the root node of $T\_2$ is not on the left flank of $T\_1$, $T\_1$ is not right-convertible into $T\_2$.
* If the root $r\_2$ of $T\_2$ is on the left flank of $T\_1$, obtain $T\_1'$, by rotating $r\_2$ up one level repeatedly, until $r\_2$ is the root. Now $T\_1$ is right-convertible into $T\_2$, if and only if the left and right subtree of $T\_1'$ are right-convertible into the left and right subtree of $T\_2$, respectively.

## Runtime:

Since each node will be rotaded up only once and by at most as many steps as the height of the tree, we need at most $O(n^2)$ rotations. If in $T\_1$ all nodes are on the left flank and in $T\_2$ all nodes are on the right flank, we will need $\frac {n(n-1)}2$ rotations, so the worst case runtime is in $\Theta(n^2)$.

## Correctness:

If the algorithm finds a sequence of rotations, there obviously is one. To see the other direction, note the following:

* If we rotate $r\_2$ off the left flank, we immediately destroy right-convertability. So such rotations can never be necessary.
* Any rotation not involving $r\_2$ will affect a subtree, that is not changed by moving $r\_2$ to the root. (It may be moved around as a whole, but this is independent of rotations within the subtree.) So if this rotation is necessary, we can still do it at a later time.

From these points correctness follows by structural induction.

---
Tags: algorithms, trees, binary-trees
---


# Question
Title: Deciding if a finite automata accepts strings of any length
Question is you're given a DFA. Give an algorithm which tells you whether strings of all lengths $n\in \mathbb{N}$ are acceptable or not.

What I doing was, I have algorithm to count the number of all strings of some fixed length $n$. Now let there are $k$ states. Suppose we got a positive result (i.e the number of strings is $\> 0$) for all $n$ up to $k$. Then check $k+1$: if it gives a positive result then we can say, at least one state is visited twice by that path of length $k+1$. That means we'll get $x$ such that all of $k+1+nx$ for all $n\geq 0$ will get accepted if $x=1$ then done. If not then check again $k+2$ again we'll get a $y$ like that. So for all $n\>k$ we're getting APs of lengths which are acceptable but then can we say after some finite state we can say all numbers are accepted ?

# Answer
> 6 votes
Let $L$ the language accepted by your DFA. The question amounts to ask whether $\\{ |u| \mid u \in L \\} = \mathbb{N}$. To check this, just identify all letters to a single letter, say $a$, in your DFA. You will get a NFA on the alphabet $\\{a\\}$. It now remains to check whether this NFA accepts $a^\*$.

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


# Question
Title: What is the notation for bounding running time in worst case with concrete example resulting in that worst case running time
I know that Big O is used to bound worst case running time. So an algorithm with running time $O(n^5)$ means its running time in worse case is less than $n^5$ asymptotically.

Similarly, one can say that for example merge sort's running time is $O(n^2)$ which is correct. But we know that there is a better bound for it: $O(n\log n)$. Technically speaking, one can say that every polytime algorithm has running time $O(2^n)$. This is correct, but not useful.

So my question is: what is the notation used for the case of worst case running time such that there exists an input in which the worst case running time happens.

In the merge sort example, one cannot construct an input example so that merge sort would take $n^2$ comparisons, but one can construct an example that requires the number of comparisons being about $n\log n$.

# Answer
See "big 0" or Landau notation in wikipedia. What you are looking for is the section on Bachmann-Landau notations.

* $f(n)\in O(g(n))$ means $f$ is bounded above by $g$ up to a constant.
* $f(n)\in \Omega(g(n))$ means $f$ is bounded below by $g$ up to a constant.
* $f(n)\in \Theta(g(n))$ means $f(n)\in O(g(n)) \wedge f(n)\in \Omega(g(n))$

**Further remarks** (since the scope of the question is being implicitely extended)

These definitions can be used for worst case as well for a best case analysis of complexity, starting from an analysis of respectively the greatest or least costs over all inputs of size $n$.

Then, for algorithm $A$, let $A\_{min}(n)$ and $A\_{max}(n)$ be respectively the best case and worst case complexity of $A$.

Then, omitting intentionally "worst case" or "best case". so as to cover all cases, you can say that:

* the complexity of $A$ is $O(g(n)$ iff $A\_{max}(n)\in O(g(n)$
* the complexity of $A$ is $\Omega(g(n)$ iff $A\_{min}(n)\in \Omega(g(n)$

Now using the $\Theta$-notation is not necessarily meaningful for this "overall" complexity of $A$. It is meaningful iff $O(A\_{max}(n))=O(A\_{min}(n))$

To be complete, many people also use average case analysis.

Also, people often mean worst case when they omit qualification of the complexity.
> 5 votes

# Answer
In words, such a bound is called a *tight* bound. In the specific case of Landau notation, $\Theta$ can be used to indicate a tight bound. You have to be somewhat careful about your wording, though:

* "The runtime of quicksort is in $O(n^2)$," is a correct statement (but somewhat imprecise).
* "The runtime of quicksort is in $O(n^2)$, and this bound is tight," is correct and expresses, what you want to express.
* "The worst-case runtime of quicksort is in $\Theta(n^2)$," is equivalent to the previous statement.
* But "The runtime of quicksort is in $\Theta(n^2)$," is not correct, since this statement implies that quicksort takes quadratic time on every input.
> 6 votes

# Answer
Use the notation that expresses the strongest property you know to be true.

Suppose you have an algorithm.

* If you have a class of inputs on which the algorithm runs in time $O(f(n))$, this actually tells you nothing about the worst-case running time: the worst case is worse than something that's better than $f(n)$, which could be literally anything.
* If you have a class of inputs on which the algorithm runs in time $\Omega(f(n))$ or $\Theta(f(n))$, then you know that the worst case running time is at least as bad as this class, so the worst case is $\Omega(f(n))$.
* If you have a class of inputs which you know to be the worst case, and the algorithm runs in time $O(f(n))$, $\Omega(f(n))$ or $\Theta(f(n))$, they you know that the worst-case running time is $O(f(n))$, $\Omega(f(n))$ or $\Theta(f(n))$, respectively.

> In the merge sort example, one cannot construct an input example so that merge sort would take $n^2$ comparisons, but one can construct an example that requires the number of comparisons being about $n\log n$.

This falls into the third bullet: you have a class of inputs which you know to be the worst case, and the algorithm takes time $\Theta(n\log n)$ on those inputs. So the worst-case running time is exactly that: $\Theta(n\log n)$.
> 2 votes

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


title: Can coq express its own metatheory?

text:
# Question
Title: Can coq express its own metatheory?
I'm learning about language metatheory and type systems, and am using coq to formalize my study. One of the things I'd like to do is examine type systems that include dependent types, which I understand is very involved: being able to rely on coq would be invaluable.

Since this type system feature (and other, simpler ones) brings the expressive power of my studied system closer to coq's own, I worry that I might run into a bootstrapping problem that might not reveal itself until much later. Perhaps someone here can address my fears before I set out.

Can coq express its own metatheory? If not, can it still express simpler systems that include common forms of dependent typing?

# Answer
> 3 votes
It is possible to formalize Coq's logic within Coq but only subsets of the logic have been formalized yet. Relevant contributions are CoqInCoq, PTS, PTSATR, and PTSF.

---
Tags: type-theory, dependent-types, coq
---


title: Difference between weak and strong AI

text:
# Question
Title: Difference between weak and strong AI
I'm trying to understand the difference between weak and strong AI. For an example, let's say we would pass the turing test - would it show strong AI or weak AI then?

I don't believe that this is standard terminology, but more philosophical. It was mentioned by John Searle in his "Chinese room argument". As I understand, strong AI is about computers really being intelligent such as having a mind and thus a conciousness, and weak AI refers more to computers being able to simulate the behaviour of human intelligence on only specific problems (think chess, etc.)

Now, the question is - if we would be able to pass the turing test, would it be called weak or strong AI then? Could it be strong AI due to the fact that the turing test is not limited to a certain area or a specific problem?

I came across it on wikipedia: http://en.wikipedia.org/wiki/Chinese\_room

# Answer
The usual distinction is that strong AI, also known as artificial *general* intelligence, refers to systems that can perform arbitrary tasks requiring intellect, whereas a weak AI is only able to perform specific intellectual tasks. So, for example, a computer chess program or a system that was able to compose interesting music would be a weak AI, since it only does one thing.

Passing the Turing test would indicate something close a strong AI. Although one could argue that it only requires performing a specific intellectual task (i.e., conversation), that conversation could range over just about anything that humans can intellectualize about. Indeed, the Wikipedia page I linked above mentions the ability to pass the Turing test as a component of an operational definition of strong AI.
> 4 votes

# Answer
it is worth mentioning some of the historical/ philosophical debates behind AI that have persisted for over a half century. AI as a field has absolutely/ unequivocally made major progress and evolution in sophistication over many decades. however it has succumbed to early hype and optimism about its achievements. so in some ways it has not been an "even" advance.

there is a so-called moving the goalposts problem in AI. not sure who first originated this observation but it can be found in many papers. it is mainly levelled by AI proponents in favor of AI research and they have stated that critics argue that no matter what is achieved by AI technology, it is not human. there is clearly some validity to this observation. so there is some psychological component to attempting to measure AI progress that tends to normalize/ minimize significant advances.

so in short "weak" and "strong" AI are informal notions mainly used in philosophical/ meta analysis of AI. the problem with AI is that there are no hard-quantitative ways to measure it. even the Turing test with its dressings of impartiality (of so called "judges") involves a large amount of human subjectivity. unfortunately Turing did not seem to reference this subjectivity much in his original statement and its in some ways "haunted" the field ever since.

if any hard-quantitative way of measuring AI were formulated, it would probably fail as far as anyone can tell. there are quantitative ways of measuring the performance of AI related applications, eg say chess scores. and computers did very poorly at chess originally, and those scores improved to become superior to humans. in earlier philosophical writing, some AI critics did accept that chess or game playing was a sign of intelligence, but that concept melted away after computers successfully played chess and there seemed to be no "human like" aspect to their operation or play. on the other hand some chess experts felt that in the legendary Kasparov/ Deep Blue game, the computer seemed to exhibit a kind of "creativity".

as a particular case study, the "moving the goalposts" phenomenon happened on both sides of this match. Deep Blue became more powerful with software and hardware advances, and Kasparov increasingly complained that the match rules were unfair. Kasparov had long said that a computer would never beat him. when it did, he asserted it was through cheating. so similar caveats apply to the study of "weak" and "strong" AI.
> 0 votes

# Answer
I believe in order to really answer your question; it will take many more years of research in neuroscience, computer science, psychology, and chemistry. Even within this thread itself, how can you be so sure that there are intelligent beings parsing the thread who know english. One would have to clearly define what it truly means to **know** something. Well, we philosophically understand knowledge as something we have personally experienced empirically, which is known as a posteriori knowledge, or a priori knowledge , that is knowledge that is not from direct personal experience. But who can really deny that there is such a mechanism for a computer to experience things in their own way of experiencing, that which is to be experienced.

The true crux of the problem is that we can't experience another conscience empirically except that of our own, that is, with today's current technology, which is also to say a priori. And yet even our own consciences is mysterious to us, because it does not directly present itself to you as you would normally perceive an entity. When you do perceive an entity, you are using your very conscience, and so, how do you begin to perceive that which gives you the ability to perceive in the first place.

What is essential to remember that just because one has not experienced something yet, does not imply that it will not be experienced. Who is to say that there are not even greater forms of AI, then that of our own Intelligence? What would be so inherently special about our species, that we would experience the "greatest" kind of "intelligence" that we have, that could not somehow be emulated outside of the constructs of nature.

I recommend reading the following philosophical book, that I myself have currently started reading. Sein Und Zeit von Martin Heidegger, that is "Being And Time", and there is an english translation for it.
> -1 votes

---
Tags: terminology, artificial-intelligence
---


# Question
Title: Separability of the nearest power of two function
I have a function $f$ given by

$f(x)=nearest\ upper\ power\ of\ two\ of\ x$

For example, $f(5)=8$ and $f(2)=2$.

Are $f(x \wedge y)$ and $f(x+y\mod{N})$ separable over some operator. For example, could we do:

$f(x\wedge y)=g(x)g(y)$

or

$f(x+y\mod{N})=g(x)\ op\ g(y)$

where $op$ is some arbitrary operator.

In other words, what can be done algebraically with the nearest power of two function?

In Warren's Hacker's delight, we have that the nearest power of two function is given by:

$ f(x)=1\<\<(32-nlz(x-1)-1) $

on a 32 bit register and with $nlz$ being the number of leading zeros. Maybe this is of use?

# Answer
No, $f(x+y)$ is not separable.

Consider: $f(3+5)=8$. Also $f(3)=4$ and $f(5)=8$.

At the same time, $f(4+5)=16$. Also $f(4)=4$ and $f(5)=8$.

It follows that $f(x+y)$ is not determined by $f(x)$ and $f(y)$ (consider $y=5$, $x\_1=3$, $x\_2=4$), so there is no function $h$ such that $f(x+y)=h(f(x),f(y))$.
> 2 votes

---
Tags: arithmetic
---


# Question
Title: Are there ways to automatically (no human testing) measure a $9 \times 9$ Sudoku puzzle's average hardness for a human to solve?
So most resources providing Sudoku puzzles assign a difficulty category to each puzzle, even some I've seen with 15 or more difficulty categories. But what is a good way to assign these difficulty categories? If enough human puzzle solvers were used, the average time for a human to complete a puzzle and the percentage of people who successfully solved the puzzle could be computed for the human sample, and difficulty categories assigned accordingly. But it seems like there should be predictable scenarios that keep appearing as various puzzles are being solved that affect the average human difficulty, which could be automatically detected as a computer solves the puzzle and then these patterns could be assembled into a predicted average difficulty for humans. Are there / what are good techniques to do this? Maybe machine learning with enough training data of human performance on sample puzzles?

# Answer
> 8 votes
There are have been many such attempts. Most of them try to derive deduction rules which humans seem to use to solve Sudoku puzzles.

My money is on this approach:

Mária Ercsey-Ravasz & Zoltán Toroczkai (2012), *The Chaos within Sudoku*, Scientific Reports 2:75, Nature.

The idea is based around the notion of transient chaos in a dynamical system.

In dynamical systems, when you change the state, there is often a period of time where a transient signal dominates, before the system manages to get itself into a steady state solution. If the dynamical system is nonlinear, the transient may be chaotic.

This is different from a chaotic attractor (e.g. the Lorentz attractor), in that the steady state that the system is eventually drawn to isn't chaotic, just the transients.

The time that the system takes for the transients to die down is called the *escape rate*. What the authors found is that if you turn the puzzle into a SAT problem, and then turn that into an equivalent dynamical system (where the attractor of the dynamical system is the solution to the SAT problem), the escape rate of the system correlates quite well with how Sudoku puzzles are rated for hardness.

The interesting thing about this approach is that it's independent of Sudoku. Any puzzle which can be turned into a SAT problem fairly directly (the SAT problem and the puzzle can't diverge too far) can be analysed in the same way.

# Answer
> 2 votes
If you want to measure the hardness of a puzzle "for a human", a typical approach is the inference techniques needed to complete the puzzle. For instance, you can categorize inference strategies as basic, intermediate, and expert.

These methods can all be implemented on a computer. If the computer can solve the puzzle with just basic methods, the puzzle is easy. If intermediate techniques are needed, the puzzle is medium. Otherwise, the computer needs expert strategies, and the puzzle is hard. I have seen a program that classifies puzzles based on this approach, but can't seem to recall the exact reference.

All the puzzles that can be solved with just inference (no guessing needed), will be easy for a computer. If you are interested in puzzles hard for a computer, one basic rule is that they need to resort to guessing at some point. Generation of hard Sudoku puzzles (for a computer) have been investigated too, and you can easily find relevant papers.

---
Tags: algorithms, machine-learning, board-games, sudoku
---


title: Strange TM Language on Definition

text:
# Question
Title: Strange TM Language on Definition
i prepare for Autotmata Course Final Exam.

in one of lecture, our professor draw this Turing Machine, and wrote DELTA is Neutral element of TM.

it'w wrote:

Language of this TM is: {$W \in (a+b)^\* : w=w^R$}

but i think x is in alphabet and the language is {$W \in (a+b+x)^\* : n\_a(w)=n\_b(w)$}

$n\_a$ is number of a's in w.

anyone could add some detail or hint for this note and which of them is correct?

# Answer
> 1 votes
Look at the instructions like $a/x,R$ in the diagram. They are used to "mark" the letters that have been compared (for every $a$ marked, we also mark a $b$). The TM repeatedly marks a pair of different symbols, and then restarts at the left side of the tape.

The machine works as follows. It starts at the leftmost symbol of a tape. It skips all $x$'s (in $q0$ moving right) and looks for the first $a$ or $b$, moving to $q1$ and $q2$ respectively (to distinguish cases). In that state it looks for the other symbol skipping $x$'s, and $a$'s or $b$'s depending on the letter we found first. At that point (in $q3$) it returns to the left of the tape (moving left until a blank $\Delta$ is found) and repeats. Acceptance if in $q0$ we only find $x$'s and reach the blank $\Delta$ to the right of the tape.

This indicates that $x$ is a special symbol from the tape alphabet, but not the input alphabet, and is used for administration during the computation. The original language is correct: $\\{ w\in \\{a,b\\}^\* \mid n\_a(x) = n\_b(x) \\}$.

Technically it could be the case that $x$ is also in the input alphabet. However what your professor stated is consistent with the diagram. A language over $\\{a,b\\}$, and an extra tape symbol $x$ to mark symbols that have been accounted for.

# Answer
> 0 votes
You are right in that the machine verifies that the input word contains as many $a$ as $b$.

If $x$ is an allowed input symbol or not depends on the definition of the input alphabet, which can not be deduced from the image.

---
Tags: turing-machines, automata
---


# Question
Title: Why the alphabet of the digital information is composed of 2 elements?
*please don't offer an answer about "it's an electronic thing" or something like that, just keep reading.*

I don't understand why we use a dictionary, a lexicon, with just 2 elements to express the entire digital world.

My point is about the fact that information is entropy, things that are predictable or just don't vary over time don't carry any information, so if you want information you want entropy, and if you want entropy why you stick with just 2 elements for your alphabet ? It's like the minimum before making the thing completely "flat" and meaningless like an array full of 0 or Z, an array of 0 and 1 it's just the next step after that .

But the main reason why I don't accept the answers with "electronics in them" is that this kind of studies were based on math and theoretical stuff, Boole wasn't even a regular student, He was a self taught mathematician, and chances are that he was trying to solve or study a practical problem without even caring about electronic devices given the times he was in .

If you also consider the information as a bingo where you can call numbers from 1 to 100, and you can call 1 number for each session, you have 1% of probability to call any number in the range, and this probability doesn't change between sessions . But this doesn't grant you any entropy, it's just probability .

For example if you consider a single char a number in the Bingo and the fact that every char is contributing to a word with its positional value, the fact that the *hello* word is composed over time by

```
h
he
hel
hell
hello

```

with each char having the same probability this consideration, on its own, doesn't give you any entropy.

Things change when you introduce a dictionary of a given language and you associate it with the pool of chars you are fishing from. If you have that dictionary the word *hello* becomes predictable, and thus with less entropy and more order, by the time you write *hel* or *h* or *he* depending on the context and semantics .

So I guess the answer is that we use binary because no one speaks binary and there is no dictionary of words in binary and the binary is not sensitive to the context and thus retains more entropy ? Because the context plays a big role in lowering the entropy and let things appear more ordered then what they really are, and entropy can be also taught as just something "random" with less order because you don't know what to expect because there is no semantic. And I don't think that the positional value can be considered as a giveaway for semantic, you have the same probability of picking either 0 or 1 in your next cell of information, positional value doesn't change anything.

I'm probably terribly confused and confusing, but why we use binary ?

# Answer
> 4 votes
You are really asking three different questions:

1. Why are computers based on binary?
2. Why did Boole use a binary system?
3. What does all of this have to do with entropy?

The answer to the first question, as you suspect, relies on implementation details; see for example this question. In other circumstances, such as wired or wireless communication, information is transmitted in larger chunks, what is known as *modulation*.

The answer to the second question is simpler: Boole was formulating the laws of thought, that is logic, in which each statement is either true or false. That's your binary distinction.

Finally, I can't really follow your third question. According to Shannon's source coding theorem, you can optimally compress information using any channel. Text is usually stored as text since it's easier to process that way, but we can compress it to reduce its size to roughly the entropy. In some sense, text is stored using an alphabet of size roughly 64, including lower and uppercase letters, digits and punctuation marks. Other data is stored in bytes, which is an alphabet of size 256. All of this has nothing to do with entropy, rather it's ease of processing. These are just some thoughts, since I can't really understand this question.

---
Tags: information-theory
---


# Question
Title: Propositional logic --- syntactical completeness
Lets consider propositional logic. We say a proof system for propositional logic is syntactically (negation) complete if for every $\alpha$, either $\alpha$ or $\neg \alpha$ are provable within the system, i.e., $\Sigma \vdash \alpha$ or $\Sigma \vdash \neg \alpha$. (I assume standard definitions for $\Sigma$ and $\vdash$).

It seems to be me that no sound proof system for propositional logic could prove $p$ or $\neg p$ from empty set of sentences, where $p$ is a propositional atom. So, propositional logic is not syntactically complete.

Now, it is to my understanding that this is kind of completeness Godel was considering in his Incompleteness Theorem for FOL. Since FOL (with abuse of terminology) subsumes propositional logic, it trivially holds that FOL is not syntactically complete either. This seems to simple, so I am wondering what am I doing wrong? Or his proof focused on Peano arithmetic specifically?

Related: link

# Answer
You are not doing anything "wrong", you just missed the point of the incompleteness theorem, a bit.

What you claim (correctly) is that a proof system with no axioms is incomplete. You also say that this is not very impressive...

What Godel showed is something much stronger: consider the theory of Peano arithmetic, then there *does not exist* a complete axiomatization for it.

How does this relate to your post? Well, in your suggestion, even when you consider an empty set of axioms, there are still some true sentences (the tautologies), and there are axiom systems that capture exactly those sentences.
> 5 votes

---
Tags: logic, proof-techniques, first-order-logic, propositional-logic
---


# Question
Title: Minimum distance between start and end by going through must visit points in a maze
So, suppose i have a maze, which has a start point and an end point, marked with Orange and red respectively and my goal is to find the minimum distance between them. The blocked path is represented by black colour and the open path is represented by white colour . However there are two modification done in this.

1. There are some cells which are must visit, marked in grey colour.
2. Any cell can be visited any number of times(even the start, finish and must visit points)

```
for ex-
  █=Black, ░=white, G=grey, R=Red, O=orange

         ██████                 █████
         ██G███                 █░GG█
MAZE1 => █O░GR█     MAZE2  =>   █O███
         ██G███                 █░░R█
         ██████                 █████

```

Here in this case ans will be

```
MAZE1 => M[2][1] => [2][2] => [1][2] => [2][2] => [3][2] => [2][2] => [2][3] => [2][4]  = 7
MAZE2 => M[1][1] => [1][2] => [2][2] => [3][2] => [3][3] => [3][2] => [2][2]            = 6

```

As you can see, the nodes appear multiple times

First i thought of using recursion technique (backtracking) but couldn't come to an algorithm. and

So i thought of using this way.

1. I will keep track of all the coordinates of must visit points, start and end points
2. Find the distance between each node(like in selection sort we compare each and every term, just like that, we get the minimum distance between each node (using BFS))
3. Then apply some minimum distance algorithm. I thought of TSP but it says nodes must be visited exactly once.Here it can be multiple times. I found chinese postman problem, but don't know if it can be applied here. Floyd warshall algorithm is there but it doesn't include every point

How should i proceed, any idea?

# Answer
Most real mazes are trees and there is a polynomial time algorithm for this problem on trees. For ease of description, orient all edges of the tree to point away from the start vertex. Now, for each vertex, delete any child if the subtree rooted at that child contains no vertices that must be visited (i.e., contains no grey or red vertices). The result is a tree where every leaf is grey or red (there may be grey and red vertices in the interior of the tree, too). Now perform a depth-first traversal of the tree, investigating the children of each node in arbitrary order, except that, if one of the children is on the path from the start to the red (end) node, that child is investigated last. If the red node was a leaf, you are done; if not, take the unique path from the leaf you finished at to the red node. The total distance is twice the number of edges in the reduced tree, minus the number of edges on the shortest path from the start to the red vertex.

For general graphs, the problem is **NP**-hard. Consider the special case where the "maze" actually has no black squares. What we have is, essentially, a so-called rectlinear TSP, where the start, end and grey squares are the "cities". Rectilinear TSP is metric TSP using the Manhattan distance as the metric. The input is a set of points with 2D integer co-ordinates. Observe that metric TSP doesn't care whether you revisit cities or not because it obeys the triangle inequality: if the shortest route from A to B is via C, and the salesman has already visited C, he'll just drive straight past; in the maze world, we don't care whether he stops or not, since he's allowed to stop in a city as many times as he wants. Rectilinear TSP is **NP**-hard: see Garey, Graham and Johnson, *Some NP-Complete Problems* (Proc. 8th STOC, pp. 10–22, 1976; ACM DL).

To prove **NP**-hardness of the maze problem, we need to demonstrate a reduction from rectilinear TSP. This isn't quite trivial because the maze problem has specified and distinct start and end squares but I'm reducing from rectilinear TSP, in which the salesman starts at any city he chooses and returns to that city at the end. But observe that it doesn't matter what the start city is, since the tours ABCDA and CDABC have exactly the same length: forcing the tour to start at a particular city doesn't actually change the answer. So, if I'm allowed to cheat once more and put the red and orange squares in the same place, I'll do that. But you probably mean that squares have a unique colour, so here's the full reduction:

> Take the northern-most of the cities and make it be the start square (if there are multiple cities equally far north, choose any one of them. Make every other city a grey square. Place the end square one square to the north of the start square and colour black the squares north, east and west of the end square. Make every other square white.

Because of the black walls, any route from the start square to the end square must revisit the start square immediately before going to the end. The end square and its black walls are outside the convex hull of the original cities, so no optimal tour of the original cities would have gone through those squares. Therefore, a shortest route from the start square to the end square consists of a solution to the rectilinear TSP problem (a shortest tour from the start city, through all the other cities and back to the start city), followed by the one-square move from the start square to the end square. This completes the reduction.
> 8 votes

---
Tags: algorithms, shortest-path, traveling-salesman
---


# Question
Title: Why does the solution of an NP problem have to be polynomial size?
I've read in "Introduction to Algorithms" (CLRS) that formal language $L$ is NP-language if and only if there is a polynomial verification algorithm $A(x, y)$ and a constant $c$ such that $$L=\\{x\in\\{0,1\\}\mid \exists y \text{ with } |y| \leq |x|^c\text{ and } A(x, y)=1 \\}\\,.$$

What is the purpose of the constraint: $|y| \leq(|x|^c)$?

# Answer
First, let's refresh the proof that the definition given is indeed equivalent to the standard definition of **NP**, i.e., the class of languages accepted by polynomial-time nondeterministic Turing machines.

Suppose $L$ is accepted by a polynomial-time Turing machine $M$. There is some $c$ such that $M$ runs in time $|x|^c$ for all inputs $x$. The verification algorithm is as follows: given $x$ and $y$, interpret $y$ as being a sequence of states of $M$ (expressed in some appropriate alphabet), and accept the pair $(x,y)$ if, and only if, $y$ describes an accepting path of $M$ on input $x$. Now, for any string $x\in L$, $M$ has an accepting path of length at most $|x|^c$, there exists a $y$, also of length at most $|x|^c$, such that $A$ accepts $(x,y)$. If $M$ rejects $x$, then there is no accepting path, so no string $y$ can describe an accepting path, so $A$ rejects $(x,y)$ for any string $y$.

Conversely, suppose that a polynomial-time algorithm $A$ exists with the properties stated in the question. We can construct a nondeterministic polynomial-time algorithm for $L$ as follows. Given input $x$, nondeterministitically "guess" (generate) a string $y$ of length at most $|x|^c$ and see if $A$ accepts $(x,y)$. If $x\in L$, then there is a string $y$ of length at most $|x|^c$ such that $A$ accepts $(x,y)$, so our machine accepts; if $x\notin L$, then no string $y$ has the desired property, so our machine rejects. This is a nondeterministic polynomial time algorithm because it does a polynomial about of guessing and a polynomial amount of simulation of $A$.

So, what goes wrong with this if we remove the condition that there exists some $y$ specifically with length at most $|x|^c$? Well, the first half of the proof still works: if $L$ is in **NP** then $A$ exists and, hey, it still happens to have the property that $|y|\leq |x^c|$, even though that wasn't required. However, the other half of the proof breaks. We no longer have the guarantee that it's enough to guess $|x|^c$ bits. In fact, we have no guarantee at all. We'd have to keep guessing longer and longer strings to test with $A$ and, actually, the procedure would never terminate for $x\notin L$: there's no way to tell if there really is no $y$ for which $A$ accepts $(x,y)$ or if there is such a $y$ but it's just so long that you've not seen it yet (undecidability of the halting problem).

So, without the polynomial bound on $|y|$, every **NP** langauge can still be expressed in this way but, unfortunately, so can all recursively enumerable languages. The polynomial bound is required to restrict the class of languages described to just **NP**.
> 13 votes

---
Tags: complexity-theory, np
---


# Question
Title: Number of nonnegative solutions of linear Diophantine inequality
Given inequality $Ax + By \le C$, where $A, B, C$ are integers, $A$ and $B$ are coprime and $C \< AB$. I need to find number of non-negative integer solutions of it.

Is there exists algorithm which run in polynomial time? For example if $A \le 10^{10}, B \le 10^{10}$ it should work less than a second. Thanks in advance.

# Answer
> 1 votes
I've found a paper for you (however it's about more general case).

Welcome to the site!

---
Tags: number-theory
---


# Question
Title: Calculating speedup for a two-way superscalar cpu
I've been coming across a problem in one of my assignments requiring the calculation of the speedup of a two-way superscalar cpu. The problem is as follows:

There is a two-way superscalar CPU with 2 pipelines U & V. The instruction pipeline U processes the complex instructions, while the instruction pipeline V processes the simple instructions. The ratio of the processing times in the phases of pipelines U and V is 3:1. I'm required to calculate the processing time for 1000 instructions in GPSS (General Purpose Simulation System) - Student Version, for the following cases:

```
50% complex and 50% simple instructions
25% complex and 75% simple instructions
75% complex and 25% simple instructions
Probability of 50% complex and 50% simple instructions
Probability of 25% complex and 75% simple instructions
Probability of 75% complex and 25% simple instructions

```

I have the simulation files and i can deduce the execution time for each case T(Supuperscalar).

However I'm stuck with the requirement of finding the speedup for each case.

I'm aware that the speed up can be calculated as Speedup = T(Sequential)/T(superscalar) = k\*n/k+(n-1) where k is the number of stages and n is instruction number, however I'm having a hard time figuring out how to calculate the sequential time for the above cases.

I would really appreciate if somebody can give me a hint here.

# Answer
> 1 votes
The speedup is the ratio of the time when using your superscalar CPU, divided by the time if you used a simple sequential CPU. For the sequential CPU, imagine that at each step you can execute *either* pipeline U or pipeline V, but not both at the same time. Simulate the workload on that kind of sequential CPU, and see what the execution time would be.

# Answer
> 0 votes
The quick answer to your question is that you should simulate the program with 1k instructions you have. In the case of non-super-scalar, make sure that you can process either one complex or one simple instruction at a time. Not both, exactly as D.W mentioned above. Then you will compute the ratio of the number of cycles taken to complete 1k instructions in each scenario.

Nevertheless, I think I need to note the followings in your question:

* Having a factor of 2 super-scalar, but allowing each of the 2 differs in cycle to complete an instruction will make things very hard to manage.
* Saying that your architecture has 2 pipelines U and V to process instructions are very strange. If your CPU can simultaneously process 2 instructions and complete 2 instructions in the same cycle, then it has a superscalar factor of 2.
* The number of pipelines is used to describe the number of stages that your machine instruction has. You can imagine that each stage is completed by a different circuitry area (pipeline) in the CPU, so the number of stages is actually the number of pipelines you have. Not as you asked.
* You can't really have the speedup formula with n and k and superscalar factor because this depends on the instructions that you feed into the CPU. You have to actually simulate to know what the speedup ratio is.

---
Tags: computer-architecture, cpu-pipelines
---


# Question
Title: Quick Sort Algorithm When Partition is Constant Time
I ran into a question about Quick Sort Algorithm.

Suppose in Quick Sort, Partition procedure take C times, (need constant time). if we use random data as input, what is the order (time complexity) of Randomized-Quick Sort?

any hint or solution highly appreciated.

# Answer
Hint: Since the runtime for each recursive call is dominated by the runtime of partition, the runtime of your modified algorithm will be $C$ times the total number of recursive calls. The latter number is independent of the input and relatively easy to determine, by looking at the elements that are not taken into the recursive calls. (Trying to solve this via a recurrence relation is significantly harder.)
> 0 votes

---
Tags: algorithms, algorithm-analysis, runtime-analysis, quicksort
---


# Question
Title: Create a random graph based on the Degree Distribution and Clustering Coefficient Distribution
I am currently working with a very large Social Network and I want to recreate this graph with a smaller dimension, using the original Degree Distribution and Clustering Coefficient Distribution.

The degree distribution is the relative frequency of vertexes in the original graph that have a certain degree.

The clustering coefficient distribution is the relative frequency for each vertex degree of two neighbours (of a vertex with that degree) to have a link between them.

Does anybody know any literature and algorithm to do this? The stuff I have found was always very theoretical..

Thanks!

# Answer
> 3 votes
You may want to have a look at the block two-level Erdos-Renyi model (BTER). The usual preferential attachment mechanism for generating scale-free networks doesn't capture the clustering coefficient right, and small-world networks aren't scale-free; the BTER model can capture both scale-free and clustering behavior. I think they have some way to make it work for an arbitrary degree distribution (not just scale-free). The link I gave above has code for generating BTER graphs too.

# Answer
> 2 votes
As far as I know, clustering coefficient determines the degree to which nodes in the graph tend to cluster together, and the degree shows how individuals behave for choosing their neighbors.

I usually use GTgraph to generate random graphs. You may use Erdos-Reyni graphs if the degree distribution matters or use SSCA graphs if you are looking for cliques and the nodes that are densely connected to each other.

# Answer
> 2 votes
Simulating random graphs with tunable clustering is non-trivial.

One method is that described by Newman. As you say there are various (conflicting) definitions of 'clustering coefficient'. Check the paper and see if it corresponds to yours. In any case you will need to compute an appropriate 'triangle corner' distribution.

Then to simulate the graph with $n$ vertices (which we label from $1$ to $n$):

1. Generate a sequence of independent random variables $D\_1, \dots, D\_n$ according to your target degree distribution. If the sum of the $D\_i$ is odd then add $1$ to $D\_1$, say. Now attach $D\_i$ 'half-edges', or 'stubs' to vertex $i$. Pair up the half-edges/stubs uniformly.
2. Generate a sequence of independent random variables $T\_1, \dots, T\_n$ according to the triangle distribution. Adjust $T\_1$ appropriately so that the $T\_i$ sum to a multiple of $3$. Attach $T\_i$ 'triangle corners' to vertex $i$, and repeatedly join $3$ corners together at random, till there are none remaining.
3. You have now generated a 'multigraph'– possibly there are multiple edges and loops. Keep repeating (1)–(2) until you obtain a genuine graph.

This is fairly greedy. It generates a random graph which matches your degree distributions and clustering coefficients. However, it may or may not be a good model for your data.

Edit: the above method is also discussed by Wang along with an alternative.

---
Tags: algorithms, graphs, social-networks
---


# Question
Title: What is the definition of a $\Pi_1$-sentence?
What is meant when somebody says that a problem can be expressed as a $\Pi\_1$-sentence? I know that for the arithmetical hierarchy, a $\Pi^0\_1$-sentence is a sentence of the form $\forall n\_1\forall n\_2\dots\forall n\_k \psi$ where $\psi$ is a formula in the language of Peano arithmetic with only bounded quantifiers. And for the analytical hierarchy, a $\Pi\_1^1$-sentence is a sentence of the form $\forall X\_1\forall X\_2\dots\forall X\_k \psi$ where $\psi$ is a formula in the language of second-order arithmetic with no set quantifiers.

I found the following definition for this notation in section "5 Proving Independence" of an article on the possibility of undecidability:

> Let’s define a $\Pi\_1$-sentence to be any sentence of the form, “For all $x$, $P (x)$,” where $P$ is function that can be proven to be recursive in Peano Arithmetic, PA.

People talking about $\Pi\_1$- and $\Pi\_2$-sentences sometimes refer to Shoenfield's absoluteness theorem, which seems to talk about $\Pi^1\_2$-sentences, i.e. refers to the analytical hierarchy. Can I deduce from this that people talking about $\Pi\_1$-sentences use $\Pi\_1$ as a shorthand for $\Pi^1\_1$ (because $x^1=x$...)? But the quoted definition looks much more like the condition from the arithmetical hierarchy to me, even so I'm not sure whether it is really equivalent to it.

# Answer
> 3 votes
Since Peano arithmetic is a first-order theory, all quantifiers are first-order, so it's a $\Pi\_1^0$ sentence. The article probably contains examples supporting this interpretation.

# Answer
> 2 votes
> What is meant when somebody says that a problem can be expressed as a $Π\_1$-sentence?

It's a $\Pi^0\_1$ sentence, just like Yuval Filmus said. Instead of proving that the cited definition is indeed equivalent to the condition of a $\Pi^0\_1$ sentence (which should be possible), let me provide further evidence of actual usage:

In each of the cited cases, some people talk about $\Pi\_1$ sentences and some people talk about $\Pi^0\_1$ sentences, and both sides agree that they are talking about the same thing.

---
Tags: terminology, logic
---


# Question
Title: Detection of redundant boolean constraints
I'm trying to solve a constraint programming problem using a SAT solver. I have set of constraints in the form of propositional logic statements, which are converted to CNF using Tseitin transformation. From the nature of my problem I know that there are redundant constraints. For example, I have a rule: $$AND\\:(OR\\: (x1,x2),\\: OR\\: (x3,x4)) \\,\\,\\,\\,\\,\\,(1)$$

and another: $$AND\\:(OR\\: (x1,x2),\\: OR\\: (x3,x4), \\:OR\\:(x5,x6))\\,\\,\\,\\,\\,\\, (2)$$ where $x\_i$ are inputs. Both constraints have in common subnodes, for example $OR (x1,x2)$. Due to this I know that there is no point in having both constraints - if the first one becomes FALSE, then the second equals FALSE too. So the second one is redundant. This example is the easiest. One more, closer to what might be found in my formula: $$AND\\:(x1,\\:x2,\\: OR \\:(AND \\:(x3,x4), \\:AND\\:(x5,x6)))\\,\\,\\,\\,\\,\\,(3)$$ and the second one: $$AND\\:(x3,x4)\\,\\,\\,\\,\\,\\,(4)$$ In this case, I can simplify the first one to the form of: $$AND\\:(x1,\\:x2,\\:AND\\:(x5,x6))\\,\\,\\,\\,\\,\\,(5)$$ due to (4).

I prefer to have a lot of small rules (by a lot I mean $10^3$ or $10^4$, which in CNF become $10^5-10^6$ of clauses). The rules are not complicated - 10 ANDs and ORs and 20-30 inputs per rule at most, but they are usually much simpler.

Is there an efficient way to remove such redundancy from a formula? Is it possible with CNF formulation or I should use some other representation of the formula (BDD, for example)? Any help and directions will be useful.

# Answer
The simplification you're describing is called subsumption. It's a standard technique and some SAT solvers (e.g. minisat) will apply it along with other simplification techniques as a preprocessing step before attacking the SAT problem itself. In particular, subsumption and equivalent variable substitution together, applied to the generated CNF formula, are enough to do the common subformula elimination you described in the question. That's because each circuit transformation yields an output variable, and output variables derived from the same circuit can be efficiently identified and reduced to references to a single variable. After that normal subsumption rules applied to clauses will eliminate the common subformulas.

If you're using a solver that doesn't do this preprocessing, then you can do the rough equivalent of it during conversion to CNF. First you'll need to apply duplicate circuit suppression while you're doing the Tseitin tranformation. As you're doing the transformation to CNF, memoize each circuit you've converted. If you encounter the circuit again, skip the circuit conversion and use the same output variable that you used for the memoized circuit. Once you've converted everything to clauses, do normal clause subsumption, i.e. check each clause A against every other longer B clause to see if A's literals are a subset of B's. If so, then A subsumes B and clause B can be discarded from the formula.
> 3 votes

# Answer
I finally found an appropriate solution.

My CNF minimization problem actually consists from 2 different tasks and requires 2 different techniques, which are described in these 2 papers:

1. Hyper-binary resolution, HBR (link)

This technique allows to perform something like 'structural hashing'. Consider two logic gates $AND1(a,b)$ and $AND2(a,b)$. It is obvious, that they are the same, but in CNF form it is not so clear:$$(and1|-a|-b)(-and1|a)(-and1|b)(and2|-a|-b)(-and2|a)(-and2|b).$$ Using 'tail' clauses like $(-and1|a)(-and1|b)$, HBR allows to conclude that $and1==and2$. This technique only appends additional clauses to CNF.
2. Hidden tautology elimination, HTE (link)

Consider following CNF: $$(a|b|c)(a|d)(d|-c).$$ In case of binary clauses, we can 'glue' them together, if clauses have some literals in common: $$(a|b|c),(a|d)\rightarrow(a|b|c|d)$$ $$(a|b|c|d),(d|-c)\rightarrow (a|b|c|d|-c).$$ Resulting clause always will be true due to $(c|-c)$, so these clauses must be removed or considered in some other way.

In conclusion, in our case, memory consumption has been reduced by x3-x10. Runtime in some cases have been improved by x2, sometimes it have been degraded. We use some additional problem specific optimizations, but there is no point to discuss them. Main goal have been successfully achieved.
> 1 votes

# Answer
there are basically 3 fundamental techniques that can be found in various algorithms for solving SAT, and there is a lot of research on this topic in SAT solver minimization/ simplification heuristics, often integrated into leading solvers. in other words a lot of this logic is already built into good SAT solvers and it is often treated as an optimizing "black box" by practitioners.

* KJ mentions subsumption in his answer.
* Davis-Putnam algorithm & DPLL use subsumption & another technique called "unit propagation". this applies to formulas where there are some single-literal clauses. the truth value can be "propagated" to other clauses in a sort of chain-reaction that also can trigger other new simplifications such as subsumption.
* a more general technique can be seen in the Quine-Mccluskey method of generating/ enumerating minterms and new more efficient "minterm covers". this can lead to exponential blowup but find simplifications that are not available from unit propagation or subsumption.

another more general/ emerging technique is to look at clause-variable graphs (eg Decomposing SAT problems by Herwig) which can reveal the overall structure of the SAT instance and "dependent vs independent variables" also known as "backbone" related elements (active area of research).
> -1 votes

---
Tags: satisfiability, sat-solvers
---


# Question
Title: baz_num_elts exercise from Software Foundations
I'm at the following exercise in Software Foundations:

```
(** **** Exercise: 2 stars (baz_num_elts) *)
(** Consider the following inductive definition: *)

Inductive baz : Type :=
   | x : baz -> baz
   | y : baz -> bool -> baz.

(** How _many_ elements does the type [baz] have?
(* FILL IN HERE *)
[] *)

```

All of the answers I've seen on the Internet say that the answer is 2, and that the elements are x and y. If that's the case, then it's not clear to me what is meant by *elements*. There are certainly two constructors, but it's impossible to actually create a value of type *baz*.

It's impossible to create a value of type `baz` because `x` has type `baz -> baz`. `y` has type `baz -> bool -> baz`. In order to get a value of type `baz` we need to pass a value of type `baz` to either `x` or `y`. We can't get a value of type `baz` without already having a value of type `baz`.

So far I've been interpreting *elements* to mean *values*. So `(cons nat 1 nil)` and `(cons nat 1 (cons nat 2 nil))` would both be elements of type `list nat` and there would be an infinite number of elements of type `list nat`. There would be two elements of type `bool`, which are `true` and `false`. Under this interpretation, I would argue that there are zero elements of type `baz`.

Am I correct, or can someone explain what I'm misunderstanding?

# Answer
> 10 votes
I agree with you. There's a bijection between `baz` and `False`.

```
Definition injective : forall {t1 t2}, (t1 -> t2) -> Prop := fun t1 t2 f1 => forall x1 x2, f1 x1 = f1 x2 -> x1 = x2.

Definition surjective : forall {t1 t2}, (t1 -> t2) -> Prop := fun t1 t2 f1 => forall x1, exists x2, f1 x2 = x1.

Definition bijective : forall {t1 t2}, (t1 -> t2) -> Prop := fun t1 t2 f1 => injective f1 /\ surjective f1.

Inductive baz : Type :=
   | x : baz -> baz
   | y : baz -> bool -> baz.

Theorem baz_False : baz -> False. Proof. induction 1; firstorder. Qed.

Goal exists f1 : baz -> False, bijective f1.
Proof.
exists baz_False. unfold bijective, injective, surjective. firstorder.
assert (H2 := baz_False x1). firstorder.
assert (H2 := x1). firstorder.
Qed.

```

---
Tags: coq
---


# Question
Title: Are context free grammars the only ones that have parsing trees?
As I understand, the generation process of a string in a context free language according to its context free grammar can be represented as a tree.

For a formal language which can have a formal grammar, can the generation process of a string also be represented as a tree?

What kind of trees can identify context-free grammars then? I.e. a formal grammar is context free, if and only if the generation of each string according to the grammar can be represented as what kind of trees?

# Answer
If you look at the Chomsky Hierarchy and the corresponding definitions of grammars for each of the four types you can make the following remarks:

* there does not seem to be any natural concept of derivation (generation) tree for type 0 grammars, the unrestricted kind, that would apply to all.
* for context-sensitive (type 1) grammars, at least in the form given in the wikipedia article, one could associate a tree structure to the derivation of the string, but this tree, even annotated with the grammar rule applied at each node, would not be sufficient to recover simply the order of application of the rules. You would have to actually associate some partial order with the tree nodes. I do not know whether this was ever used.
* The context-free case (type 2) is well known.
* The regular case (type 3) is well known too. It may be seen as a special case of CF. But regular grammars, and associated tree structures are not interesting since they are trivial. They do not really provide useful generative information, nor do they impart structure on the generated string. Note however that CF grammars with interesting tree structures could well generate regular languages.

However, this is not the end of the story. There are many kinds of grammars, between the regular family and the full context sensitive (CS) family, i.e. around the CF realm. Many can associate a derivation tree with the generation process, and they can also associate a derived tree with the generated string, thus giving it a structure.

These two trees are the same in the case of CF grammars, but, as I indicated in my answer to another of your questions, they may also differ, notably in grammars involving multi-parts constituents. such as Tree Adjoining Grammars (sometimes called mildly context sensitives) or more generally Linear Context-Free Rewriting Systems (LCFRS). These grammars depart somewhat from the basic model of Chomsky hierarchy, as do many others, such as indexed grammars.

For all these formalisms, the languages defined are usually in the context sensitive realm, and cannot be generated by a CF grammar. The derived trees associated with the strings are thus also beyond what can be done with CF grammars. However, many of the formalisms considered in the literature have sets of derivation trees that are the same as those of Context-Free languages.

The set of parse trees (meaning here both derivation and derived trees) for context-free language is a tree language. The family of parse-tree languages associated with CF grammar is precisely what is called regular sets of trees. They can be defined by Regular Tree Grammars (that may look suspiciously like string CF grammars). They can be recognized by finite state tree automata.

What distinguishes CF Grammars is that their derived trees are regular sets of trees, which is not the case for the other formalisms. However, many of these formalisms have regular sets of derivation trees, the same as CF languages.
> 2 votes

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


# Question
Title: Do NFAs with ϵ-transitions accept languages that no PDA can?
Is it correct to say that there are languages that a NFA with epsilon recognizes but a PDA is not? I think that it is wrong but I cannot find a suitable explanation.

# Answer
> 3 votes
This follows immediately from the definitions and the basic characterizations of the different kinds of automata. Every NFA, with or without $\epsilon$-transitions, recognizes a regular language. Every regular language is context-free. Every context-free language is recognized by a PDA.

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


title: Optimal way for grouping events

text:
# Question
Title: Optimal way for grouping events
I am creating an event notification system.

Each event has a user and a subject, such that, *'user did event to the subject'*. Now while presenting these the events need to be grouped.

All the events in the same group must either refer to the same user or the same subject and each event must be in exactly one group. Subject to those constraints, a group can contain any number of events, including just one. I want to calculate the grouping that uses the least possible number of groups.

Note that forming one group for each user, or forming one group for each subject does not, in general, give the smallest possible number of groups. Also, the events cannot, in general, all be placed in the same group, as that usually gives a group containing multiple users and multiple subjects, which is forbidden.

If I start from the first event and start putting it in the group with most possible events *(acting all greedy)*, I will end up with a sub-optimal solution.

I could check all possible groupings but that will blow up exponentially *($2^n$ possible groupings for just n events)*.

**How can I go about optimally grouping these events such that most of the events get grouped one way or the other, minimising the total number of groups?**

**Sample data -**

```
event1    user1    subject1
event2    user2    subject1
event3    user3    subject1
event4    user2    subject2
event5    user3    subject2
event6    user1    subject3
event7    user2    subject4
event8    user2    subject5
event9    user3    subject5
event10   user1    subject5
event11   user4    subject1
event12   user4    subject2
...

```

# Answer
> 4 votes
Represent the events as a bipartite graphs: the vertices are the users and subjects and the edges are events (so there's an edge from user $x$ to subject $y$ if there's an event involving that user and subject). What you're looking for is essentially a minimal vertex cover. A vertex cover is a set $C$ of vertices such that every edge includes at least one vertex from $C$. A minimal vertex cover is one that includes the smallest possible number of vertices.

**Example.** If the events are "John likes pizza", "John likes candy" and "Jane likes candy", the graph has vertices John, Jane, pizza and candy and the edges are John–pizza, John–candy and Jane–candy. A minimal vertex cover would be John and candy (in this case, there are several other minimal vertex covers).

For general graphs, finding minimal vertex covers is **NP**-hard but, for bipartite graphs, there is a polynomial-time algorithm because of König's theorem, which says that finding minimal vertex covers of bipartite graphs is equivalent to finding maximum matchings (i.e., a biggest-possible set of edges such that no pair of edges in the set shares an endpoint), which can be done by the Hopcroft–Karp algorithm. The algorithm for finding a minimum vertex cover from a maximum matching is described in the "Proof" section of the Wikipedia König's theorem page.

Let $C$ be the minimum vertex cover that you just computed, and let the vertices in it be $c\_1, \dots, c\_k$ (so each $c\_i$ is either a user or a subject). The groups are $g\_1, \dots, g\_k$, where $g\_1$ is all the events that involve the user or subject $c\_1$and, for $i\>1$, $g\_i$ is the set of all events that involve the user or subject $c\_i$ that haven't already been included in one of $g\_1, \dots, g\_{i-1}$.

---
Tags: algorithms, optimization, cluster
---


title: Base conversion puzzle

text:
# Question
Title: Base conversion puzzle
Here's an old puzzle: Let $s$ be a string of decimal digits ($s\[i\] \in \\{0,\dotsc, 9\\}$). Define a function $f(s)$ as follows:

* Interpret $s$ as a decimal number, $n\_{10}$, and convert $n$ to its octal equivalent, $m\_8$.
* Now treat $m$ as a decimal number, $m\_{10}$ and convert it to its hexadecimal equivalent, $h\_{16}$, and return its hex representation as a string.

For example, if $s= \langle245\rangle$ we would have $245\_{10} = 365\_8$ and $365\_{10} = 163\_{16}$ so in this case, $f(\langle245\rangle) = \langle163\rangle$. Similarly, $f(\langle155\rangle)=\langle \mathrm{E}9\rangle$

What are the fixed points of $f$? In other words, for which digit strings $s$ is $f(s)=s$?

I have a few questions about this puzzle:

1. It's not hard to show that $\\{0,\dotsc, 7, 64,\dotsc, 69\\}$ are all fixed points. Are these the only ones? I have a proof that they are, but it's inelegant, basically showing that after a certain point, $p(s) \< s$, or $p(s)$ isn't a decimal string. Does anyone have a nicer proof, for some value of "nicer"?
2. I've spent more time than I should in a so-far futile search for a reference to this problem. Does anyone have one? All I know is that it's decades old.

# Answer
> 6 votes
Define $f(s)=h(g(s))$, where $g(\cdot)$ is the conversion to octal and then interpreting the result as a decimal string, and $h(\cdot)$ is the conversion to hexidecimal and then interpreting the result as a decimal string (if possible). For instance, $g(245)=365$, and $h(365)=163$.

Asymptotically, it is easy to see that $g(x) \sim x^\alpha$, where $\alpha = \log\_8 10 = 1.1073\dots$. In other words, once $x$ is large enough, $g(x)$ is asymptotically proportional to $x^{\alpha}$. (Why? Consider $x=8^k$, or $x=a \cdot 8^k$ where $a \in \\{1,2,\dots,7\\}$. Once $x$ is large enough, the lower-order terms in the base-8 representation of $x$ become negligible, asymptotically.) Similarly, asymptotically we have $h(y) \sim y^\beta$, where $\beta = \log\_{16} 10 = 0.83048\dots$.

It follows that asymptotically

$$f(s) \sim s^{\alpha \beta}.$$

Notice that $\alpha \beta = 0.9196\dots$, and in particular $\alpha \beta \< 1$. Therefore, asymptotically, $f(s)$ grows more slowly than $s$.

It follows that there is a constant $c$ such that, for all $s\>c$, we have $f(s)\<s$. From this it is easy to see that we only need to check finitely many possible values of $s$: the values $s=1,2,\dots,c$.

All that remains is to determine the constant $c$ explicitly. This can be done with a bit of algebra; it gets a bit messy, and I don't know of any elegant way to derive it. But hopefully the above is a relatively clean way to show why your approach has to work, and isolates the messy part to a well-contained calculation. To me, this is much nicer, because it provides some pretty simple intuition about why there can be only finitely many fixed points.

In other words, this all follows as a consequence of the fact that

$$(\log\_8 10) \times (\log\_{16} 10) \< 1.$$

---
Tags: reference-request, base-conversion
---


# Question
Title: Find a regular language that becomes non-regular if you cut away the middle third of all words
Let $A$ be a regular language, let $A'=\\{xz\\}$ such that for some $y,|x|=|y|=|z|$ and $xyz\in A$. Show that $A'$ is not necessarily regular language.

This is an excercise of Sipser, I've no idea how to construct $A,A'$ please help someone

# Answer
Hint: Let $A = a^+ b^+ c^+$ and consider $A' \cap a^+c^+$.
> 3 votes

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


# Question
Title: Most time-optimal parallel algorithms to calculate the determinant and inverse of a matrix
I am writing a numeric library to exploit GPU massive parallelism and one of the implemented primitives is a matrix class. Naturally I require a determinant and inverse function for this class and I am having trouble finding algorithms which perform well on a massively parallel architecture where there is no shared memory between CPU and GPU.

However, on the wikipedia page for the $\mathsf{NC}$ complexity class states that the determinant (and inverse) of matrices lies within this class, which makes me believe that there do exist algorithms which perform well on massively parallel architecture.

Can anyone provide me with a reference to such an algorithm, or is it just proved that the determinant and inverse of a matrix lies within $\mathsf{NC}$ without a current algorithm having been developed.

# Answer
> 1 votes
The class **NC** is the class of **decision** problems decidable in polylogarithmic time on a parallel computer with a polynomial number of processors. Is your problem to decide - or actually compute the Determinant of a Matrix? Chistov's algorithm solves for the determinant in the class **NC** with $(log$ $n)^2$ processors, and is the best(?) so far for the class **NC**(Reference: Fast parallel calculation of the rank of matrices over a field of arbitrary characteristic. A. L. Chistov ). As an aside, the question whether the class **P** is equivalent to **NC** is still open.

# Answer
> 0 votes
try this algorithm, it is close to what you are asking for ie optimized parallezed algorithm for the discriminant that may also deal with ill-conditioned matrices. complexity analysis sec4.2 p10 and in the appendix:

> Therefore we opted to parallelising the algorithm for an MPI cluster. Here we observed linear gain in performance as evidenced by Table 3. This is consistent with the fact that the dominating term in the overall complexity of the algorithm $O(N^3)$ is due to computations, and the complexity of data transfers $O(N^2 \log T)$ is comparatively small.

A Parallel Algorithm for Calculation of Large Determinants with High Accuracy for GPUs and MPI clusters Beliakov, Matiyasevich

> We present a parallel algorithm for calculating very large determinants with arbitrary precision on computer clusters. This algorithm minimises data movements between the nodes and computes not only the determinant but also all minors corresponding to a particular row or column at a little extra cost, and also the determinants and minors of all submatrices in the top left corner at no extra cost. We implemented the algorithm in arbitrary precision arithmetic, suitable for very ill conditioned matrices, and empirically estimated the loss of precision. The algorithm was applied to studies of Riemann’s zeta function.

# Answer
> 0 votes
The NC algorithm for computing the determinant is Berkowitz's algorithm. See for example this paper by Soltys, which also links to the original paper, or various lecture notes on the subject.

---
Tags: algorithms, reference-request, optimization, parallel-computing, matrices
---


# Question
Title: Does "output" always imply halting in computability?
$L = \\{P : P(n)$ outputs $n^2$ for all $n \in N \\}$

In questions of this nature, are we supposed to assume that "outputs" means "halts and outputs"? In modern programming languages, I can certainly "output" using a print statement and then have the program go into a loop after that.

# Answer
The output of Turing machine is the content of the tape *when it halts*.

This is the standard definition. If a machine has written some string $s$ to its tape but hasn't halted yet, a straightforward reduction from the undecidability of the halting problem means that you have no way of knowing if it will ever write more characters to its tape, so you can't know if $s$ will be the "final" output. That means, for example, that you can't say that, if a non-halting computation never changes the string on the tape after the $t$th step, then the output is that unchanging tape string.

However, see Andrej's answer for a way of getting a well-defined output from a non-halting machine. The key point there is that the output tape is read-only so once a bit of the output has been written, you know that bit will never change.
> 5 votes

# Answer
The *standard* way of treating Turing machines as things that accept intput and produce output is as follows:

* the input is written at the beginning of the tape in such a way we can tell where it ends,
* the rest of the tape is initially "empty", i.e., filled with a blank symbol,
* the output is whatever is on the tape when the machine halts
* if the machine does not halt, the output is *undefined*
* the machine is responsible for creating output from which we can actually tell where it ends (this is done easily with a bit of encoding, or there can be a special end-of-output symbol).

Such machines are sometimes called "type 1" (in order to distinguish them from "type 2" machines described below).

In computable analysis and several other areas we work with infinite representations (think about an infinite stream of digits of a real number). There we have the so called *type 2* machines:

* there is an read-only input tape which contains infinite input
* there are working tapes
* there is an output tape onto which the machine is allowed to write *exclusively* left-to-right once per cell, i.e., the only instruction for the output tape is "write symbol $x$ and move the head to the right"
* there is no halting state -- traditional halting may be indicated by outputing a special symbol on the output tape, but the machine keeps spinning

Type 2 machines never halt. Nevertheless, we can still compose them and observe what they are doing. Of course, in any finite amount of time only a finite amount of input is consumed and a finite amount of output is produced. A type 2 machine may diverge in the sense that it does not fill up the entire output tape.

Type 2 machines are convenient because they can operate on *non-computable* input, for instance, they can compute the square root *any* real number. In constrast, type 1 machines necessarily operate on computable reals, encoded by finite input which describes how to calculate approximations to the real.
> 4 votes

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


# Question
Title: What actually is the concept of transparency? Why not call it Abstraction?
I searched this over Google few times but ended up with articles on transparency rather than an answer. With relation to distributed database study(or distributed OS), what is the concept of transparency? I mean in replication, fragmentation and everywhere I guess the idea is to implement these concepts but not to bother user about them. Correct me if I'm wrong but I think the idea is "User shouldn't know?". Then HOW is this transparency? Isn't it abstraction? Hiding the implementation details?

# Answer
I agree with you. The distinction is pretty weak.

I *think* the rationale is that *transparent* is supposed to mean "invisible", or "you don't even know it's there." *Abstraction* means that you don't see the implementation of something, but you know that it's there.

Example: Consider Linux. There's one command, `cp <srcfile> <destfile>` for copying files on the mounted file system. There's a completely different command, usually `scp <user>@<machine-name>:<srcfile> <destfile>` for copying a file from a remote filesystem that is mounted on a remote machine. `scp` is an *abstraction* in that it hides all the implementation details about contacting the remote machine using the ip protocol, the encryption of the channel, and the mechanics of accessing the disks on the local and remote sides of the transfer. But in no way is the distinction between a local file and a remote file *transparent*. You have to use a different command depending on where the file is.

Worse, you can't edit the remote file in-place. With a local file you just open the file in your text editor. With a remote file you have to `scp` it to your local file system, edit the copy, and then `scp` the modified file back to the original location.
> 3 votes

---
Tags: distributed-systems, databases, database-theory
---


# Question
Title: Algorithm for approximation with sum or difference of 2 unit fractions
Let $U =\\{\frac{1}{n}: n\in \mathbb{N}\\} \cup \\{-\frac{1}{n}: n\in \mathbb{N}\\}$ be the set of positive or negative unit fractions.

Given positive integers $m\<n \in\mathbb{N}$, how do you find $u\_1, u\_2 \in U$ such that $|\frac{m}{n} - (u\_1+u\_2)|$ becomes minimal?

A weaker problem would be the following: Given positive integers $m\<n \in\mathbb{N}$ and a positive integer $k\in\mathbb{N}$ devise an algorithm that outputs "Yes" if there exist $u\_1, u\_2\in U$ such that $|\frac{m}{n} - (u\_1+u\_2)| \< \frac{1}{k}$, and "No" otherwise.

# Answer
Here's a method that gets close. Do a continued fraction expansion of $\frac{m}{n}$:

$$\frac{m}{n} = \frac{1}{a + \frac{1}{b + \epsilon}} \approx \frac{1}{a + \frac{1}{b}} = \frac{1}{a} - \frac{1}{a(1 + ba)}$$

If $\epsilon$ is small, then this is probably very close to optimal if not optimal in most cases.

The method fails when the truncated continued fraction approximation isn't very good. Take $\frac{15403}{26685}$ (a rational approximation to the Euler-Mascheroni constant) as an example. The continued fraction approximation is:

$$\frac{15403}{26685} = \frac{1}{1 + \frac{1}{1 + \epsilon}}$$

Which suggests:

$$\frac{15403}{26685} \approx \frac{1}{1} - \frac{1}{2}$$

But clearly $\frac{1}{2} + \frac{1}{14}$ is closer.

I would wager that the worst case for any method is the conjugate golden ratio $\phi' = \frac{\sqrt{5} - 1}{2}$. This isn't rational (in fact it's the "most" irrational number in a technical sense; find its continued fraction expansion if you're curious), but you can get arbitrarily close by choosing $m$ and $n$ to be consecutive Fibonacci numbers, e.g. $\frac{4181}{6765}$. The best approximation I could find is $\frac{1}{2} + \frac{1}{9}$.
> 1 votes

---
Tags: algorithms, numerical-algorithms
---


# Question
Title: Context Free or Context Sensitive and why
I was given two languages

$$L\_1=\\{0^k1^k0^m\mid k,m \in \mathbb{N}\text{ and }k \< m\\}$$

and

$$L\_2=\\{a^mb^{m+1}\\}$$

and I was asked to prove whether they are context free or sensitive.

For $L\_1$ : I did pumping lemma and I cannot clearly rule out the context free. So I accepted that it is and tried to do a high level description of a pda. I check the first part of the language $0^k1^k$ like this: push A for every 0 you read pop A when you read 1. If the stack is not empty reject. But I have trouble finding how to check the second part, $1^m$ with $m\>k$. So now I do not know if it is indeed a context free.

For $L\_2$ I followed a similar method with $L\_1$ and again I stuck in the $m+1$ part.

Can someone help me? I am not proficient in grammar creation and pdas and lbas were only taught in our class in high level descriptions like the above.

# Answer
> 0 votes
Hint 1: You can write the languages as $0^k1^k0^k0^{m-k}$ and $a^mb^mb$.

Hint 2: If a language looks non-context-free, but the pumping lemma does not show this, you can try Ogden's lemma.

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


# Question
Title: Clarification of Hopcroft's proof that "deciding whether a program halts on all inputs" is not R.E
$DoesNotHaltOn\\\_w=\\{(M, w) : M$ does not halt on input w$\\}$
$AlwaysHalt =\\{ M : M$ halts on all inputs x $\\}$

Hopcroft gives the following proof that $AlwaysHalt$ is not R.E.

1) Given an input x of length n, $M'$ simulates $M$ on w for n steps.
2) If during that time $M$ halts then $M'$ loops and $M'$ does not halt on its own input x.
3) However if $M$ does not halt on w after n steps then $M'$ halts.
4) Thus $M'$ halts if and only if $M$ does not halt on w.
5) Since the problem of telling whether $M$ does not halt on w is not R.E., it follows that whether a given TM halts on all inputs must not be R.E. either.

I don't understand why in (1) the number of steps to simulate needs to be dependent on the length of the input x.

I don't understand how step 3 implies step 4. I don't see how knowing that $M$ does not halt on w after n steps (or less) allows us to conclude that $M$ will not halt on w after more than n steps.

Could someone clarify? Thanks.

# Answer
$M'$ doesn't "need" to do anything. $M'$ is a machine that we construct for purposes of the proof. Hopcroft wrote the theorem, so he can design $M'$ however he wanted -- of course, then it's his obligation to show how his choice of machine helps him prove the theorem. He chose $M'$ cleverly in a way that helps make the proof easy, but that was his choice.

So, it was his choice to make the $M'$ simulate $M$ for only $n$ steps. He could have chosen something else, but this particular choice makes the proof work out nicely. In particular, this property of $M'$ is useful for showing that statement 4 is true. (Exercise: try proving that statement 4 is true, and check where you used the fact that $M'$ will only simulate $M$ for $n$ steps, not more.)
> 1 votes

---
Tags: computability, reductions, undecidability, semi-decidability
---


# Question
Title: Finding a pair of edge disjoint paths in a graph, such that the weight of each of them is bounded
Given an undirected graph $G=(V,E)$, two distinct vertices $s,t\in V$, a weight function $f:E \to \mathbb{N}$, and a constant $M\in \mathbb{N}$, does there exist a pair of edge disjoint paths connecting $s$ and $t$, each of which has weight at most $M$? In other words, we are given an upper bound on the path weights, and we want to know whether there exists two paths from $s$ to $t$ that don't have any edge in common.

Call this problem DPBP (for disjoint pair of bounded paths).

Is DPBP NP-complete?

A variant of this problem can be solved in polynomial time. In particular, Suurballe's algorithm can be used to find a pair of edge-disjoint paths where the *sum* of their weights is minimal; thus, it can be used to decide whether there exists a pair of edge-disjoint paths such that their weights sum to at most $M$. But what about when we require each path to have weight at most $M$, instead of requiring that their two weights sum to at most $M$?

# Answer
DPBP is NP-complete.

I give a reduction from the partition problem. Define $\text{PART}=\left\\{ {x\_1,x\_2,\ldots,x\_n\in \mathbb{N}|\exists I:\sum\_{i\in I}x\_i=\sum\_{i\not\in I}x\_i} \right \\}$.

Given an instance $\left \\{ {x\_1,\ldots ,x\_n} \right \\}$ of PART, we build a graph in the following way. For each $i\in \left \\{{1,\ldots,n} \right \\}$, we have a diamond like component. These components are connected in a row, starting from $s$ and ending at $t$:

The weight of the upper left edge in the $i\text{'th}$ component is $x\_i$ and all other edges have weights $0$. The constant bounding the paths weight is $M=\frac{1}{2}\sum\_{i=1}^n{x\_i}$.

A path in this graph between $s$ and $t$ travels through all components. In order for two edge disjoint paths to fit in, each path should travel threw all components, taking either the upper or lower part of each.

Given a partition $I={i\_1,\ldots ,i\_k}\subset \left\\{ {1,\ldots,n} \right\\}$, let the first path go threw the upper parts of the components with indexes in $I$, and threw the lower parts of the other components. Since traveling threw the upper part of the $i$'th component costs $x\_i$, the weight of this path is exactly $\sum\_{i\in I}x\_i$. In case the given partition is proper, this sum is exactly $\frac{1}{2}\sum\_{i=1}^n x\_i = M$.

The second path will be the complement path, i.e., it will go threw the lower part of each component with an index in $I$, and threw the upper part of each component with an index not in $I$. Therefore, its weight will be $\sum\_{i\not \in I}x\_i=\sum\_{i=1}^n x\_i - \sum\_{i\in I}x\_i=M$ as well.

Thus, the two paths are edge disjoint and bounded by $M$ as required.

Now, assume that we are given a pair of edge disjoint paths between $s$ and $t$, so that the weights of each is at most $M$. By the construction, the weight of each is exactly $M$. Let $I=\left\\{ {i\_1,\ldots,i\_k} \right\\}$ be the components with an upper part traveled by the first path. Obviously, $I$ partitions the $x\_i$'s properly.
> 3 votes

---
Tags: complexity-theory, graphs, np-complete, reductions, shortest-path
---


title: Pushdown Automata Challenge

text:
# Question
Title: Pushdown Automata Challenge
I read one old-midterm exam on Automata. consider:

the language that accepted by above pushdown automata is not generated by which of the following grammar?

1) S-\>aBaa|a$\epsilon$

aB-\>aS|$\epsilon$

2) S-\>aaB

aB-\>aaaB|$\epsilon$

3) S-\>aaB|a

aB-\>aaB|$\epsilon$

4) S-\>aB

B-\>aaB|$\epsilon$

i think (3) is true, but when we try to solve it with my friends, we think 1 and 3 is true? any hint or idea with detail highly appriciated.

my reasoning is:

(1) and (3) and (4) generates a, but (2) couldent generate a. PDA Language is {$a^n$ | n is odd}

thanks to all.

# Answer
You identified the language of the PDA correctly.

However, you misidentified the languages generated by the grammars:

Grammar 1 can generate $aa$ via $S \to aBaa$ and $aB \to \epsilon$.

Grammar 2 can generate $a$ via $S \to aaB$ and $aB\to \epsilon$. Also each application of $aB \to aaaB$ inbetween will add exactly 2 $a$'s. So grammar 2 generates the correct language.

Grammar 3 can generate $aa$ via $S\to aaB$, $aB\to aaB$, and $aB\to \epsilon$.

Grammar 4 is equivalent to grammar 2, except every intermediate sentential form is on $a$ shorter.
> 1 votes

---
Tags: formal-languages, automata, formal-grammars, pushdown-automata
---


title: Binary tree traversals reversed

text:
# Question
Title: Binary tree traversals reversed
Am I correct in saying that

```
traverse(node):
    if node is null, return
    print node
    traverse(node's right subtree)
    traverse(node's left subtree)

```

would produce output that is the reverse of post-order traversal?

```
post-order(node):
    if node is null, return
    post-order(node's left subtree)
    post-order(node's right subtree)
    print node

```

I am mostly interested because if this is true, it greatly simplifies the iterative method for post-order traversal. It "feels" right with a hand-wavey explanation - and with testing on some trees - but how would I prove it?

# Answer
> 2 votes
I would say you are right. If the post order of a tree is "left-recursion, right-recursion, root" then the reverse is "root, reverse-right-recursion, reverse-left-recursion", which is exactly what you propose. Technically the proof would state "by induction on the structure of the tree".

---
Tags: algorithms, trees, binary-trees, graph-traversal
---