title: PDA for this context-free grammar

text:
# Question
Title: PDA for this context-free grammar
I have the following CFG $G$: $$ \begin{align} S &\rightarrow aAbb \mid aaBb \\ A &\rightarrow aAbb \mid \epsilon \\ B &\rightarrow aaBb \mid \epsilon \\ \end{align} $$

I have to create a PDA (pushdown automaton) to recognize this language however I am unsure on how to do it. So far I have this(revised based on feedback from user Hendrik Jan) :

I understand that it should accept the last one ($aaaabb$) however it does not for the current version.

# Answer
> 1 votes
From CFG to PDA is a simple construction. Set axiom $S$ as initial pushdown symbol. If the topmost symbol of the stack is nonterminal replace it according to a production of the grammar. If the topmost symbol is a terminal we are forced to read the same symbol from input tape (and pop the symbol). That is called *expand-match*. See wikipedia. The resulting PDA is single state, acceptance by empty stack.

(added) Your problem is on a special type of grammar, linear context-free. That means in every step of the derivation there is exactly one nonterminal. You can mimic this using a different construction. Basically the nonterminal is the state. All terminal symbols to the left are read, those to the right are pushed, to be read later. For $S\to aaBb$ the PDA goes from state $S$ to state $B$ while reading $aa$ (in usual models that takes two steps) and pushing $b$.

On your construction (it seems of the latter type). Concretely: the grammar generates $a$'s and $b$'s in a two-to-one / one-to-two ratio. In general: in order (for yourself) to see why it doesn't work you have to try to formulate the meaning of the states. How do they relate to things happening in the grammar?

# Answer
> 1 votes
While Hendrik Jan's answer is totally spot-on, it's worth noting that you don't always need to follow the algorithmic construction to get a PDA. If you can decide via analysis what the language is, you can often come up with a machine more easily.

The grammar you give generates $a^nb^{2n} \cup a^{2n}b^n$ where $n \> 0$. In particular, any construction which uses the rule $S \rightarrow aAbb$ will generate a string in $a^nb^{2n}$, and any construction using the rule $S \rightarrow aaBb$ will generate a string in $a^{2n}b^n$.

Therefore, a simple procedure to obtain a correct PDA is the following:

1. Create a PDA $M\_1$ to recognize $a^nb^{2n}$ for $n \> 0$.
2. Create a PDA $M\_2$ to recognize $a^{2n}b^n$ for $n \> 0$.
3. Create a PDA $M$ which recognizes $L(M\_1) \cup L(M\_2)$.

Each of these steps is significantly easier than trying to create a PDA from the original grammar, in my opinion, anyway.

For (1), push two $a$'s onto the stack for each $a$ you read, then pop an $a$ each time you read a $b$. Accept if the stack is empty once the input is gone.

For (2), push an $a$ for every two $a$'s you read, then pop an $a$ for each $b$ you read. Accept if the stack is empty once the input is gone.

For (3), you can create a new initial state and non-deterministically jump to the initial state of either $M\_1$ or $M\_2$ without consuming any input or putting anything on the stack. This will ensure that if your input represents a string accepted by either of the automata, then there will be a path that accepts the input.

---
Tags: context-free, automata, pushdown-automata
---


# Question
Title: Max-Flow: Detect if a given edge is found in some Min-Cut
Given a network $G=(V,E)$ , a max flow f and an edge $e \in E$ , I need to find an efficient algorithm in order to detect whether there is some min cut which contains $e$. Another question is, how do I decide whether if $e$ is the lightest edge of at least one minimal cut?

I've thought about running Ford-Fulkerson algorithm, and then increasing / decreasing the capacity of the given edge and see what happens, but I haven't came up with something that might help me solve the problem.

I'd be grateful if anyone could point me to the solution, thanks in advance.

# Answer
> 4 votes
Here is a solution for the first question: Suppose $w(e)$ is the weight of $e$, calculate min-cut value for $G$, suppose is $C$. Then we remove $e$ from $G$ to make $G'$; again we calculate the min-cut value for $G'$, suppose is $C'$, if $C-C'\ge w(e)$, then this concludes that $e$, participating in at least one min-cut (that you already know it), otherwise $e$ does not belong to any min-cut.

Link to SO answer.

# Answer
> 2 votes
If you only have rational capacities, multiply¹ them to become integral and then decrease the capacity of $e$ by e.g. $0.5$¹. Then every two cuts differ only by integers (before you decrease) and a cut that contains $e$ can't get minimal if it wasn't before. On the other hand a minimal cut that contains $e$ has now strictly smaller capacity than before and thus it has a smaller capacity than all cuts that do not contain $e$ (they weren't decreased).

Now you compute a maximal flow and if its value decreased, any minimal cut (like the one that separates vertices reachable from the source in the residual network from the rest) contains $e$, if it didn't decrease, $e$ is not contained in any minimal cut.

¹ If you don't like the multiplication, you can also compute the smallest common denominator $d$ of all weights and use $\frac{d}{2}$ instead of $0.5$.

---
Tags: algorithms, graphs
---


title: Convex polygon formulation

text:
# Question
Title: Convex polygon formulation
We have a sorted list of side lengths that can be used to form a polygon. There are $n$ such values ($n \le 1000$).

Now we need to find if we can use any 10 of these values to form a non-degenerate convex polygon.

How do we approach this? Anything up to the order of $O(n^2 \log n)$ is acceptable. Better if possible. I need the general idea on how to proceed, the properties of convex polygons which can be exploited here, etc.

# Answer
> **Theorem 1.** For every polygon with edge length sequence $a\_1,\ldots,a\_m$, there exist a convex polygon with same edge length sequence.

*Proof.* Here.

> **Definition.** $a\_1,\ldots,a\_n$ be $n$ non-negative reals. It satisfies *(strict) $n$-gon inequality* if $2a\_j \< \sum\_{i=1}^n a\_i$ for all $j$.
>
> **Theorem 2.** The sequence $a\_1,\ldots,a\_n$ is a sequence of edge length for a polygon iff it satisfies $n$-gon inequality.

*Proof.* Here. (note the proof here requires advanced math and also proves Theorem 1)

The problem reduce to:

> Given a sequence of $n$ non-negative reals, find a $k$ element subsequence that satisfies $k$-gon inequality.

An simple algorithm: Check if $a\_i,\ldots,a\_{i+k-1}$ is a solution for every $1 \leq i\leq n-k+1$. If none of them work, then there is no solution.

*Proof.* If we have any solution $a\_{i\_1},\ldots,a\_{i\_k}$, find the largest $j$, such that $a\_{i\_{j+1}}-a\_{i\_j}\>1$, (i.e. there is a gap). If there is no such gap then we are done. If there is one, then $a\_{i\_2},\ldots,a\_{i\_{j}},a\_{i\_{j+1}-1},a\_{i\_{j+1}},\ldots,a\_{i\_k}$ is also a solution. (intuitively, we used the largest element in the gap and removed the smallest element). We can repeat this step (at most $k-1$ times) and fill in all the gaps. Eventually we produced a solution of the form $a\_{i\_k}-k+1,a\_{i\_k}-k,\ldots,a\_{i\_k}-1,a\_{i\_k}$ for some $i$.

The algorithm can be done naively in $O(kn)$ time. Maybe there is a smarter way to do it.

A interesting follow up question:

> Given a sequence of $n$ non-negative reals, find the longest subsequence $S$, such that every $k$ element subsequence of $S$ satisfies *$k$-gon inequality*.
> 6 votes

---
Tags: algorithms, computational-geometry
---


# Question
Title: General question about how CPUs send and receive data/bytes to hardware?
Realize I didn't mention x86 or any more details to make this non-specific to any platform, but to just get a general idea of how this is done(this is also a long question with a lot of details).

I know most PC motherboards for desktop (if not all) computers have two sections; north and south bridge, and a chipset connects them together between the CPU's implementation and the buses carrying data around the board.

The x86 CPU has a register, I think, called the accumulator, which has eight bit AL, sixteen bit AX, and thirty-two bit EAX. Data for these registers are typically used for arithmetic operations, general purpose machine instruction, etc.

Also, supposedly for I/O access, such as with Port I/O. There is Port I/O and MMIO (memory-mapped input/output), which are two methods of accessing data outside the CPU.

I have inspected memory maps, but I'm still unclear on whether or not it's part of an instruction fetched from memory (i.e., MOV AL, 0FF) or from some other instruction to actually access hardware.

My basic question is, what specific instructions are used to write and read data from hardware, from a bare machine perspective; no device drivers, no operating system, and no firmware interrupts. This is the very essence of how system software must be made, and there's little complete coverage on how this works from the CPU's register to the hardware itself. I have seen BIOS interrupts, but that abstracts away details. Also, the developer had no idea what happens beyond INT 13.

So, despite my broad question, is there some specific way this is accomplished, either by instruction, correct value set in a register, etc.?

Example: Say I want to make a few beep noises. The sound hardware is responsible for making any noise at all, so I would, from a bare machine perspective, once again, have to directly access the hardware and its components, circuitry, or otherwise internal hardware registers or such to make noise. Is there a complimentary way of doing this that is specifically outlined or guidelined per-platform, or does it vary based on every specific piece of hardware and CPU?

If so, what would help me unravel that mystery to program for it this way? Would the card be, let's say, mapped a special address you write to? Then I would just set a register and the CPU will just send it there with whatever value it contains?

I am confused, and nothing makes clarity of this, because abstractions exist even at the low-level that create a barrier of the unknown.

# Answer
> 1 votes
The Wikipedia article on memory-mapped i/o is pretty good.

Yes, the registers that control the sound card are mapped to specific memory addresses. Reads and writes (loads and stores) to those memory addresses are recognized by the north-bridge as not belonging to the DRAM and are sent to the south-bridge. Based on the address the south-bridge reads and writes the appropriate registers on the sound card.

There are a lot of details that are specific to the processor in question. On x86 some i/o devices are memory mapped and some are *port mapped*. The port mapped interface uses two special instructions `in` and `out` that are like byte loads and stores, but only work with ports. The registers that control the internal speaker (the old-fashioned one that goes "beep", not a modern sound card) is mapped to port address 61h (hexadecimal). And the speaker frequency is controlled by the 8253 timer, the control registers for which are mapped to port addresses 42h and 43h. Here is an example: http://courses.engr.illinois.edu/ece390/books/labmanual/io-devices-speaker.html.

Other i/o devices on an x86 might be memory mapped. For example: the data buffers for the hard-disk controller will almost certainly be memory mapped and not port-mapped.

---
Tags: operating-systems, memory-hardware
---


# Question
Title: Minimal positive difference of a mulitset of real numbers
Motivated by Max-Flow: Detect if a given edge is found in some Min-Cut, I'd like to ask the following questions:

1. Given a multiset of real numbers $B$, how hard is it to compute the minimal positive difference $\delta\_\min$ $$\delta(B\_1,B\_2)=\left|\sum\_{b\in B\_1}b-\sum\_{b\in B\_2}b\right|$$ taken over all partitions $B\_1\cup B\_2=B$ of $B$ **such that $\bf\delta(B\_1,B\_2)\>0$**?
2. How hard is it to find a lower bound $\delta\_- \>0$ for $\delta\_\min$?

Observe that (2) is easy for rational numbers, as you can compute the least common denominator $d$ and every positive difference is a multiple of $\frac{1}{d}$.

Assume that all $b\in B$ are from some subset (closed under addition and symmetric difference) of $\mathbb{R}$ for which we do have a representation by finite strings and all basic operations are performable in at most polynomial time.

# Answer
### Original formulation

(Originally, the OP was interested in the minimum absolute difference rather than the minimum non-zero absolute difference.)

You are asking two different questions. For the first, consider the restricted version in which all numbers are rational, and the decision variant in which the problem is to decide whether your expression is at most some $\delta$. This problem is NP-complete by reduction from PARTITION. (Wlog all numbers are integers, and you can ask whether the difference is at most $1/2$.)

Your other question concerns the decision variant in which the problem is to decide whether your expression is at least some $\delta$. This problem is coNP-complete, and so unless NP=coNP, no nice lower bounds exist (that is, there are no polysize witnesses that the minimal difference is at least $\delta$ which can verified in polytime).

### Revision 1

(The question has been changed, and now we are looking for the minimum non-zero absolute difference.)

The problem is NP-complete by reduction from PARTITION. This time assume all numbers are integers, and add to them the additional number $1/3$. Deciding whether the minimal non-zero absolute difference is at most $1/3$ is tantamount to solving PARTITION, and so is NP-complete.
> 3 votes

---
Tags: complexity-theory, real-numbers
---


# Question
Title: Multiple-Choice Questions about decidability
I'm working on old MC-Questions about decidability und don't have the answers to the following ones:

1.) $L\_1$ and $L\_2$ are not decidable $\Rightarrow$ No superset of $L\_1 \cup L\_2$ is decidable

2.) For Turing-acceptable languages L is "L = $\emptyset$" a non-trivial property.

3.) There are context-free languages $L\_1$ and $L\_2$ so that $L\_1 \cap L\_2$ is not decidable.

4.) $L$ is decidable $\Leftrightarrow$ $L \le \\{0\\}^\* \cdot \\{1\\}^\*$

I think 1.) is false, because $\Sigma^\*$ as a superset of many undecidable languages for example is decidable and 2.) is true, because there are Turing-acceptable languages with (exactly one) and without the property. I have no idea at 3.) and 4.).

# Answer
Regarding 1 - $\Sigma^\*$ is a superset of *every* language, not just "many". This is a very general and important point: the measure of how "complicated" a language is, is not in a direct correlation with how "big" the language is.

In 2 - you are correct.

For 3 - the answer is no - if $L\_1$ and $L\_2$ are CFL, then $L\_1\cap L\_2$ is decidable. Indeed - decidable languages are closed under intersection, and every CFL is decidable.

As for 4 (assuming that by $\le$ you mean "mapping-reducible") - observe that $0^\*1^\*$ is a regular language, and in particular - decidable. Thus, if $L\le\_m 0^\*1^\*$, then surely $L$ is decidable.

Conversely, assume that $L$ is decidable, then there exists a mapping reduction from $L$ to every non-trivial language. Indeed, you can decide $L$ within the reduction, and just output a fixed string. So the answer is yes.
> 1 votes

---
Tags: turing-machines, context-free, reductions, undecidability
---


# Question
Title: Quasigroups, congruences and recognizable subsets
My question refers to the draft of Mathematical Foundations of Automata Theory, IV.2.1 (pages 89ff in the pdf). I will repeat everything necessary nevertheless:

Let $M,N$ be monoids and $\varphi: M \rightarrow N $ a monoid morphism. We say that a subset $L$ of $M$ is recognizable by $\varphi$ if there is a subset $P$ of $N$ such that $L = \varphi^{-1}(P)$. As is known, the rational languages are precisely the recognizable subsets of $\Sigma^\ast$.

Furthermore, we define an equivalence relation $R\_\varphi$ by $u R\_\varphi v :\Leftrightarrow \varphi(u)=\varphi(v)$. This relation is a congruence relation, that is $\forall s,t,u,v \in M:s R\_\varphi t \Rightarrow usv~R\_\varphi~utv$.

We say that a congruence relation $R$ *saturates* $L$ if for all $u \in L$, $uRv$ implies $v \in L$. Then in the above document, the following proposition (IV.2.2, page 90) is stated:

Let $\varphi : M \rightarrow N$ be a monoid morphism and let $L$ be a subset of $M$. The following conditions are equivalent:

(1) $L$ is recognised by $\varphi$

(2) $L$ is saturated by $R\_\varphi$

(3) $\varphi^{-1}(\varphi(L))=L$

Proof. (1) implies (2). If $L$ is recognised by $\varphi$, then $L=\varphi^{-1}(P)$ for some subset $P$ of $N$. Thus if $x \in L$ and $x R\_\varphi y$, one has $\varphi(x) \in P$ and since $\varphi(x)=\varphi(y), y \in \varphi^{-1}(P)=L$.

(2) implies (3). If $x \in \varphi^{-1}(\varphi(L))$, there is $y \in L$ such that $\varphi(x) = \varphi(y)$, that is $x R\_\varphi y$. Thus, $x \in L$, and $\varphi^{-1}(\varphi(L)) \subseteq L$ follows. "$\supseteq$" is trivial.

(3) implies (1). Let $P:=\varphi(L)$, then $\varphi^{-1}(P)=L$.

I want to weaken the assumptions made in the proposition. Namely, assume tgat the $N$ in the above definitions is a proper groupoid (in fact, I need to deal with loops), that is, associativity and identity are lost. Further, $\varphi$ need not be a morphism (the relation $R\_\varphi$, defined in the same way as above, a priori need not be a congruence anymore) and we restate (1) accordingly (as formally, the notion of a "recognable subset" is not defined for groupoids). Then my questions are

> (1) Is $R\_\varphi$ still a congruence if we demand $\varphi$ to be a morphism of groupoids (loops)?
>
> (2) Does the proposition still hold? Does it if we assume that $R\_\varphi$ is *not* a congruence?
>
> (3) What other sources (preferably monographs) are there that you recommend as comprehensive introductions to algebraic automata theory, esp. concerned with the role of monoids, semigroups (and maybe more general structures as groupoids) and their connection with automata and languages?

Personally, I think they are both true, as for (2), neither the morphism properties, nor associativity nor congruences seem to be used in the proof. And for (1), I don't see where one would need associativity to prove it. But it may well be that I overlooked something (which is why I ask...).

# Answer
(1) for any function $\varphi:E\to F$, the relation $R\_\varphi$ as you define it is always an equivalence relation on elements of $E$. But the notion of congruence depends of the laws you have on your sets, and $R\_\varphi$ will be a congruence for the operations that are preserved by $\varphi$. Notice that your formulation with $usv$ is not anymore well-defined without associativity: you have to state it separately for $us$ and $sv$.

(2) Let us weaken even more the hypotheseses. Let $\varphi:E\to F$ be any function, without any structure assumed on $E$ and $F$. Then if we take the definitions you wrote for "recognised" and "saturated", the 3 propositions are still equivalent, as your proofs still work.

The thing you will lose by considering arbitrary sets (or groupoids or loops) is that you won't carry out the nice monoid structure of $\Sigma^\*$, so you lose almost all the tools of regular languages theory, like Myhill-Nerode equivalence, Green relations, and so on...

For (3), I think Jean-Eric Pin's webpage (including the document you mention) contains good surveys of this field.
> 2 votes

---
Tags: formal-languages, reference-request, check-my-proof
---


title: How to design this synchronous circuit?

text:
# Question
Title: How to design this synchronous circuit?
I have seen this model question on synchronous circuit , but i could not understand the logic, can anyone please help me?

"Develop the state diagram for a synchronous sequential circuit which will recognize the bit sequence 1101 (ie, every time the sequence 1101 is detected in the input bit stream, the circuit has to output a 1 and otherwise a 0)."

What is the question here?? do we have consider all possible combinations ( 2^4 - 16 ) to do this ? if so , according to the question , do we have only one occasion where we get the output 1??

please explain it. -Regards

# Answer
> 1 votes
The question asks for a circuit which is given a sequence of bits, one in each round, and is supposed to output $1$ each time that the last $4$ bits form the subsequence $1101$; otherwise $0$ should be output. For example, if the input is $110110101$ then the output should be $000100100$. Naturally, the circuit will have to retain some memory.

# Answer
> 1 votes
You will only need to remember the state you are in. There are 4 possible states you can be in when matching "1101":

* State 1: Initial state, and after seeing an unexpected zero.
* State 2: After matching "1".
* State 3: After matching "11"
* State 4: After matching "110"

The transitions are as follows:

```
State   Input   Output  Next
S1      0       0       S1
S1      1       0       S2
S2      0       0       S1
S2      1       0       S3
S3      0       0       S4
S3      1       0       S3
S4      0       0       S1
S4      1       1       S2

```

The output of 1, is only done when in the last state ("110") and another one is detected.

To translate this into sequential circuits, you can encode the state either as four distinct memory-elements, or as a combination of two (00, 01, 10 or 11).

---
Tags: logic, circuits
---


title: Halting problem

text:
# Question
Title: Halting problem
I have some concerns about the Halting problem. This is the proof I know:

Let $h(M, i)$ be a function, $M$ being Turing machine and $i$ input for the Turing machine. Let $h(M, i)$ output true whenever $M(i)$ halts. Let $h(M,i)$ output false if $M(i)$ does not halt.

Then define $p(M)$ on Turing machine $M$. $p(M)$ will halt whenever $h(M, M)$ equals false and $p(M)$ will not halt whenever $h(M, M)$ is true.

What will $p(p)$ do? Now, suppose $p(p)$ halts not. Then $h(p, p)$ is true so $p(p)$ will halt. Suppose $p(p)$ halts. Then $h(p, p)$ is false so $p(p)$ will not halt.

So $p(p)$ will either halt and halt not.

But, I think it will loop endlessly. $h(M, i)$ calls $M(i)$ and $p(M)$ will call $h(M, M)$. This is not a problem. But evaluating $p(p)$ results in calling $h(p, p)$ - which will check the value of $p(p)$. But therefor, $p(p)$ is called again, so there was a cycle and the program will continue in an infinite loop.

What am I thinking wrong?

# Answer
> 5 votes
First of all, you cannot "think wrong" :)

As for the proof - you make the wrong assumption that $h$ decides the halting problem by simply running $M$ on $i$. This is not necessarily the case (in fact, it is definitely not the case).

Observe that the naive "implementation" of $h$ is not a decider - if $M$ does not halt on $i$ then $h$ never halts. Therefore, $h$ is clearly not this naive machine.

We assume by way of contradiction that there exists *some* (cleverer) implementation $h$ that does manage to decide the halting problem. Then, when $h$ is given $(p,p)$, it does whatever it does to decide, but that yields the contradiction.

To resolve the issue you brought up in the comment:

Consider the machine $h$, think of it as java code, if that's more comfortable. You then modify the code of $h$ to construct the code of $p$. Now, you send to $p$ the code of itself - just like you would send any other input. It just so happens that $p$ causes $h$ to run on some code which is partially the code of $h$ itself, but that shouldn't be any problem for $h$, it just reads it like any other input, and does whatever it does to decide.

---
Tags: turing-machines, halting-problem
---


# Question
Title: Why NP is not closed under Turing reduction
The notion of polynomial time Turing reductions (Cook reductions) is an abstraction of a very intuitive concept: efficiently solving a problem by using another algorithm as a subroutine.

For example, by stating "$A$ is polynomial time Turing reduced to $B$", we indicate that we can solve the problem $A$ in a polynomial number of steps by making use of an algorithm which can solve the problem $B$.

Then if $B$ is in $\mathsf{NP}$, why not $A$?

# Answer
The reason that $A$ is not defined as in NP is that we use a finer notion for NP-completeness, which is mapping (Karp) reductions.

Intuitively, in a Karp reduction, we not only want the problem $A$ to be solvable using an oracle for $B$, but we also require that this oracle is only used once, and only as the very last operation.

Why this notion and not Turing reductions? First - it works well, and it provides a finer distinction in complexity classes (more on that in a bit). Second, it captures the intuition that if you could solve $B$, then given input for $A$ you can convert it to input for $B$, rather than just use $B$ in some complex and clever manner. So in a way, it makes "very little use" of $B$. This is all philosophical, of course.

In practice, the main benefit of Karp reduction is that it differentiates $coNP$ from $NP$. Indeed, you can show a Turing reduction from $SAT$ to $\overline{SAT}$ (just call the oracle and flip the answer). So you cannot have the notion of coNP-complete v.s. NP-complete if you use Turing reductions.

You can read the discussion here for a more elaborate answer.
> 10 votes

# Answer
An oracle question "$x\in L?$" always answers "$x\notin L?$" as well. So if we choose $A=\overline{B}$ and the closure property you propose holds, $\overline{B}\in \mathsf{NP}$ would follow. This holds for all $B\in\mathsf{NP}$ and thus $\mathsf{NP}=$ co-$\mathsf{NP}$.

On the other hand, if $\mathsf{NP}=$ co-$\mathsf{NP}$, the closure of $\mathsf{NP}$ under Cook reductions ($P^{\mathsf{NP}}$) would be equal to $\mathsf{NP}$: $P^{\mathsf{NP}}=\mathsf{NP}\cup\text{co-}\mathsf{NP}=\mathsf{NP}$.

So your question is equivalent to: "Why is $\mathsf{NP}\neq\text{co-}\mathsf{NP}$?", thereby assuming a fact, we don't know.
> 4 votes

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


# Question
Title: Which areas in CS will be (or have been) most affected by fully homomorphic cryptography?
I'm in the middle of planning a 5000ish word essay on fully homomorphic cryptography, the current practical implementations and their limitations.

Which areas of CS as a subject have been (or will be) most affected or will utilise fully homomorphic cryptography the most in the coming years and developments?

PS. I did several searches and couldn't find a repeated iteration of this question, hope the fact this isn't a specific theory questions gets me in hot water!

# Answer
> 2 votes
Before turning to your actual question, let me mention that there aren't any practical implementations of fully homomorphic encryption. There are some implementations that are far from being practical, and it's hard to guess whether that will change in the foreseeable future.

Fully homomorphic encryption is a goal in itself, as it enables outsourcing computation resources without sacrificing privacy. As such, its applications are mainly outside computer science, in the same way that the word processor Microsoft Word doesn't have any applications inside computer science (other than writing papers; though you should do that in LaTeX).

That said, fully homomorphic encryption could be used as a building block for other cryptographic applications. Vaikuntanathan's technical survey article contains some pointers in Section 6.4: verifiably outsourcing computation; and constructing short non-interactive zero-knowledge proofs. The latter has other applications and is not an end in itself, see Groth's technical survey article.

---
Tags: cryptography
---


title: Permuting natural numbers

text:
# Question
Title: Permuting natural numbers
We have two integers $z, k$

We form a sequence now of first z natural numbers. i.e. $1, 2, 3, 4, \ldots z$.

Now we have to find total number of permutations of this sequence such that the sum of any two adjacent numbers is $ \le k$

( $z \leq 10^6$, $\\;\\;z \< k \< 2\*z$ )

Here is what I have been able to think untill now. If `k=2*z-1,` the answer is `z!`

Now if we reduce the value of `k to 2*z-2`, then we take the highest pair as a group and permute with rest of the elements, we subtract this value from the previous case of `k=2*z-1`

i.e. `dp(z,k)= z!` for `k=2*z-1`. and `dp(z,k-1)=dp(z,k)-(z-1)!*2` for `k=2*z-2`.

I want to know if I am going in the right direction. Any help on the closed form would be good.

# Answer
> 2 votes
Let $D(z,k,l)$ be the number of permutations $p\_1,\ldots,p\_z$ of $1,\ldots,z$ in which the condition $p\_i + p\_{i+1} \leq k$ is violated exactly $l$ times. Then $D(z,k,l)$ is given by the following recurrence relation, which is valid whenever $z \geq 2$ and $z+1 \leq k \leq 2z-1$: $$ D(z,k,l) = \begin{cases} (z-l) D(z-1,z,z-2-l) + (l+1) D(z-1,z,z-3-l), & k = z+1, \\ (z-l) D(z-1,k-2,l) + (l+1) D(z-1,k-2,l+1), & k \neq z+1. \end{cases} $$ I leave the proof of correctness to you.

<sup>(Here is a hint for the first case: show that $D(z,z+1,l) = D(z,z,z-1-l)$ and that $D(z,z,l) = (z-l) D(z-1, z, l-2) + (l+1) D(z-1, z, l-1)$.)</sup>

The following Python program implements this recurrence:

```
def D(z, k, l):
    if z < 2 or k < z+1 or k >= 2*z:
        raise "Error"
    if z == 2:
        return 2 * int(l == 0)
    if k == z+1:
        return (z-l) * D(z-1, z, z-2-l) + (l+1) * D(z-1, z, z-3-l)
    return (z-l) * D(z-1, k-2, l) + (l+1) * D(z-1, k-2, l+1)

```

A more efficient implementation will use dynamic programming, I leave that also to you. One thing to notice is that case II preserves the quantity $2z-k$ while case I always has $k = z+1$, so the algorithm is quadratic rather than cubic.

For concreteness, here is a Python implementation of the dynamic programming method:

```
def DP(z, k):
    if not (z >= 2 and z+1 <= k <= 2*z-1):
        raise "Error"
    z_crit = 2*z-k+1
    L = [2, 0]
    for w in range(3, z_crit+1):
        L = [(w-l) * L[w-2-l] + (l+1) * L[w-3-l] for l in range(w-2)] + [2 * L[0], 0]
    for w in range(z_crit+1, z+1):
        L = [(w-l) * L[l] + (l+1) * L[l+1] for l in range(w-2)] + [2 * L[w-2], 0]
    return L[0]

```

---
Tags: algorithms, permutations, mathematical-programming
---


# Question
Title: Retrieving data from hash table ordered by insertion time
By default, a hash table is unordered. I have a simple question on the retrieval of elements in a hash table

> Can we retrieve elements from a hash table in the same order as they are put inside?

# Answer
> 4 votes
Once you've put an element in any kind of container data structure like map or set, ordered or unordered, the data structure no longer remembers the order in which you called `insert()`. (The "ordered/unordered" distinction is whether the data structure keeps the elements in order by their key with respect to the less-than operator.)

If you want to know the order in which some events happened you will need to keep another container data structure, or some auxiliary information in the objects you are storing. For example if you want to be able to iterate through in the order in which you inserted: keep both an `unordered_map` *and* a `vector` of references to the objects you inserted. Every time you do an insertion you also `push_back` a reference to what you just inserted. (But be careful, if you are doing this in C++, that you aren't also removing objects from the unordered map, because then the references in the vector will become invalid.)

If you want a number associated with each element stored in the map ("this was the 42nd inserted"), then you should augment your `map` datatype with, (a) a global counter and (b) a way to store both an object and a number (e.g., store `struct {T the_object; int insert_order;}` instead of objects of type `T`), and (c) wrap the `insert` operators so that they increment the counter and insert the new number along with the new object.

---
Tags: algorithms, data-structures, hash, hash-tables
---


# Question
Title: How can I decide manually whether two CTL formulae are equivalent?
Assume I have two formulae $\Phi$ and $\Psi$ (over the same set of atomic propositions $AP$) in CTL. We have that $\Phi \equiv \Psi$ iff $Sat\_{TS}(\Phi) = Sat\_{TS}(\Psi)$ for all transition systems $TS$ over $AP$.

Given that there are infinitely many transition systems, it's impossible to check them all. I thought about using PNF (Positive Normal Form, allowing negation only next to literals) because judging from its name it should give me the same formula for $\Phi$ as for $\Psi$ iff they are equivalent, but I'm not convinced this works in all cases (you could say, I'm not convinced PNF is actually a normal form).

For example, take $\forall \mathrm{O} \forall \lozenge \Phi\_0 \stackrel{?}{\equiv} \forall \lozenge \forall \mathrm{O} \Phi\_0$ (where $\mathrm{O}$ is the `next` operator and $\lozenge$ is the `eventually` operator). I'm looking for a way do do this by hand.

# Answer
It seems to me that "$\Phi≡\Psi$" is equivalent to "Neither $(\Phi ∧ ¬\Psi)$ nor $(\Psi ∧ ¬\Phi)$ is satisfiable".

Therefore deciding equivalence is as difficult as deciding satisfiability, since "$\Phi$ satisfiable" is equivalent to "not ($¬\Phi≡\top$)".

In this article there is a mention of a an exponential procedure to decide satisfiability in CTL, so it should be enough to run the algorithm on the two formulas I wrote above.

*PS: I am not at all an expert in this field, so please check what I wrote. If this makes sense, I will remove the various "seems" and "should".*
> 6 votes

# Answer
If you want to prove the identities by hand, I do not know if there are absolutely general techniques. You can start with the axioms and well known identities for CTL and work from there.

If you want the answer and worry about having a human readable proof separately, you can use a CTL satisfiability checker like MLSolver.
> 3 votes

# Answer
Your example is not equivalence assume a transition system by two state which all of them are initial, and there is a loop in state which satisfy \phi. To prove equivalence of two CTL formula you should use definition of semantics.
> 0 votes

# Answer
Could you express this in the fixpoint characterization for CTL formulas? That might help you prove their equivalence. http://www-2.cs.cmu.edu/~modelcheck/ed-papers/VTfFSCS.pdf
> -1 votes

---
Tags: logic, model-checking, computation-tree-logic
---


title: Hierarchical Paging

text:
# Question
Title: Hierarchical Paging
Suppose I have a system with 32-bit logical and 16-bit physical address spaces, and the page size is 512 bytes. For simplicity, ignore the valid/invalid bits in the page table.

How many sections will the logical address be divided and how many bits will each section have? The logical address will be divided into three sections, one section for the outer page, one for the inner page, and one for the offset. The outer page section contains 13 bits. The inner page contains 10 bits. The offset section will contain 9 bits. Is this right?

Will the structure of the page table have 2 levels? How would I convert a logical address into a physical address?

# Answer
I think you need more than 2 page table levels. Here's what the page tables on AMD-64 (x86\_64) look like. (This picture is from an article by Frank van der Linden about porting NetBSD to AMD-64.)

Each page is 4K-byte and the system is byte-addressable so you need the bottom 12 bits of the virtual (logical) address to index into the physical page. The number of bits needed for each level above that is calculated as follows:

The size of the pages is 4K-byte, and the page table entries are 8 bytes on AMD-64, so you can fit 512 page-table entries per page, so you need 9 bits of logical address for each level of the table.

Walking the tree works like this. There is a register with a pointer to the top of the PML4 page. At each level you take the pointer to the top of the page, take 9 bits of logical address, multiply by 8, and use that as the byte offset into the page. You read out the 8-byte page table entry, which gives you the pointer to the top of the page 4K-byte page table at the next level deep in the tree.

In your case, each page table entry (p.t.e.) needs to have space to store a physical pointer to a 512-byte aligned page. Your physical addresses are 16 bits and you know that the bottom 9 bits are 0s (because your pages are 512-byte aligned), so each page table entry needs to be at least 7 bits, even leaving a bit for valid/invalid. And the problem even told you to not worry about control bits. So I think you can get away with a 512-byte page table containing 512-entries. It might be more realistic to assume that you would need room for expansion (either to increase the number of control bits or to increase the size of the physical address space) so you might want each p.t.e. to be 2 bytes, and then each page table could contain only 256 entries.

*It is the number of p.t.e.s per page that determines the number of logical address bits you will use to access the inner pages.* So 9 bits from the calculation we just did. (If you are assuming that each page table entry requires 2 bytes instead of 1 byte, then you could only fit 256 entries in a page table, and you would take 8 bits of logical address.)

So in your case you have 9 bits of offset at the bottom, and then multiple levels with 9 (or 8 depending on your choices) bits each. So 2 levels of table (+ the offset) only covers 27 (or 25) bits of your logical address. I think you need one more level. The top level page will not be full because you only have 5 (or 7) bits left at the top of the logical address.
> 5 votes

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


# Question
Title: Proving that CFLs are closed under even-ness using grammars
This is a question from a 2007 exam paper for a course I'm studying, question 2 on page 2.

> Theorem: Let $L$ be a context-free language. Let $L\_{even}$ be the subset of $L$ consisting of all the strings in $L$ that have even length. Then $L\_{even}$ is context-free.

The question is to prove this theorem using two of three different methods: using grammars, PDAs, or a theorem about language intersections.

I can very easily find a proof using PDAs (maintain your current odd/even status using the stack), and intersections (intersect with $\Sigma^\*\_{even}$, which is regular) - but I can't think of how to do it using properties of grammars. I suspect either Chomsky or Greibach Normal Forms comes in handy here but I'm not sure how.

# Answer
> 2 votes
The proof using grammars basically mimics the proof using automata. It is not very complicated, using a trick with derivation trees that have a computation of the finite state automaton on the leaves of the derivation tree, which is (bottom up) taken to the root.

Start with a grammar $G$ in Chomsky normal form. The grammar for the intersection (of a CFL $L(G)$ and a regular language $L({\cal A})$) has nonterminals $A\_{pq}$ where $A$ is a nonterminal of $G$ and $p,q$ are states of $\cal A$. It means the set of all strings derived from $A$ in $G$ while having a path from $p$ to $q$ in $\cal A$.

Then the productions are

* $S\to S\_{if}$ where $S$ is the axiom in $G$ and $i$ and $f$ are initial and final states in $\cal A$.
* $A\_{pq} \to B\_{pr}C\_{rq}$ if $A\to BC$ in $G$, and $p,q,r$ states in $\cal A$
* $A\_{pq} \to a$ if $A\to a$ in $G$ and transition $(p,a,q)$ for $\cal A$.

(added) That is the general construction for the intersection of context-free and regular languages. In your specific example the regular restriction is on the length of the strings. Now we need only two copies $A\_e, A\_o$ of each nonterminal $A$, denoting the parity of the length of the strings generated.

* axiom $S\_e$
* $A\_e \to B\_eC\_e \mid B\_oC\_o$, $A\_o \to B\_eC\_o \mid B\_oC\_e$, for $A \to BC$ in $G$
* $A\_o\to a$ for $A\to a$ in $G$.

That qualifies as a "push-down free" proof? Definitely no knowledge about the PDA-CFG equivalence is used.

# Answer
> 3 votes
Actually you can shoot all three qestions with a single stone.

Since you can easily define a regular language $Even=\Sigma^{2n}$ for all even strings :

1. you prove the result by applying closure of CF languages under intersection with regular sets.
2. You use the standard construction of such an intersection based on CF grammar to get the grammar version of the proof.
3. You use the standard construction of such an intersection based on PDAs to get the PDA version of the proof.

You have to know at least one of the two constructions, since it is usually how the closure under regular set intersection is proved.

The purpose of the question is to check that you know the theorem, and at least one way to prove it.

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


# Question
Title: For Djikstra's algorithm, why are we surely done if we update all edges $|V|-1$ times?
Apparently, if we use Djikstra's algorithm to find the shortest path between the root node and all other nodes in a weighted graph with no negative cycles, we are done after updating the distance of each node $|V| - 1$ times.

This puzzles me because I think that a single round of breadth first search is enough. Why must we do $|V| - 1$ of these searches?

# Answer
Either you mixed up two algorithms or you misinterpreted an upper bound. One level of a BFS with priority queue is enough, but during this one round a neighbor of the root may be updated $|V|-1$ times, therefore the update operation needs to be efficient.
> 2 votes

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


# Question
Title: How can you see which points in the spectrum is from which pixel in the original image?
Take the image and spectrum below. If I look at the spectrum, it just look like noise.... How to make sense of it intuitively?

Image:

Frequency spectrum of image (using Fourier Transform):

# Answer
As stated by @tomasz, the fourier transform relates only globally to the image since the pixels of the transform correspond to frequencies in the original image (which you may intuitively understand - somewhat - as speed of color variation as you move on the original image). This is well explained on the web : An Intuitive Explanation of Fourier Theory

Look in particular at the bottom of the page.
> 1 votes

---
Tags: image-processing, fourier-transform
---


title: serial number of combination

text:
# Question
Title: serial number of combination
How can I find the serial number of an n-choose-k combination?

I would like a function that gets as input:

* $n$,
* $k$,
* a set of $k$ elements out of the set ${0, 1, ... n-1}$.

The output should be a number in the range $\[0, C(n,k)-1\]$, such that:

* Each different combination gets a different number;
* All numbers in the range are covered (i.e. no holes in the index).

For example, for $n=3$, $k=2$, the function could be:

$serial(3, 2, {a,b}) = (a+b-1)$

Since there are only 3 combinations, and their sum is different. Obviously, this doesn't generalize to larger n and k.

One solution is: at the beginning of the program, loop over all combinations, and create a static map from a combination to its index. However, this is very inefficient when n is large.

# Answer
We will use the notation $\binom{n}{k}$ instead of your $C(n,k)$. The idea is to use Pascal's identity $$ \binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1} $$ and its proof: there are $\binom{n-1}{k}$ not containing $n$, and $\binom{n-1}{k-1}$ containing $n$. Suppose we want to encode combinations not containing $n$ before combinations containing $n$. We work recursively. If the input set $S$ doesn't contain $n$, then we recurse on $S$ as a combination in $\[n-1\]$. If it does contain $n$, we recurse on $S \setminus \\{n\\}$ as a combination in $\[n-1\]$ (of size $k-1$), and add $\binom{n-1}{k}$ to the result.

Here is Python code for the procedure:

```
def encode(n, k, S):
    if n == 0:
        return 0
    if n not in S:
        return encode(n-1, k, S)
    S.remove(n)
    return encode(n-1, k-1, S) + choose(n-1, k)

```

The function *choose* (not supplied) should compute the Binomial coefficient. You can also decode the resulting code:

```
def decode(n, k, C):
    if n == 0:
        return []
    if C < choose(n-1, k):
        return decode(n-1, k, C)
    C -= choose(n-1, k)
    return decode(n-1, k-1, C) + [n]

```
> 7 votes

---
Tags: combinatorics
---


# Question
Title: Are these languages RE? How would I determine this?
Are these languages recursively enumerable?

1. $L = \\{ \langle A\rangle \mid x\in L(A)\implies |x|\leq 13\\}$
2. $L = \\{\langle A\rangle \mid L(A) \subseteq \overline{L\_{\mathrm{uni}}}\\}$, where $L\_{\mathrm{uni}} = \\{\langle T\rangle x \in \\{0,1\\}^\*\mid x \in L(T)\\}$.

How would I prove / disprove that these languages are RE?

# Answer
Neither of these languages are RE.

Here's an intuitive way to think about this - a language $L$ is RE iff for any string $w$, there is some finite piece of information you could provide about $w$ that could convince a computer that $w$ belongs to $L$.

In the case of language (1), what information could you give me that would convince me that a TM belonged to this language? To show that a TM belonged to that language, you'd need to convince me that every string ever accepted by that TM has length at most 13. It doesn't seem likely that there is any finite piece of information you could give me that could convince me that the TM has this property. (On the other hand, if a TM *didn't* have this property, it's easy to convince me of this - give me a string that the TM accepts that is longer than length 13, and I could confirm it by running the TM on that string and observing it accept).

To formally prove that language (1) is not RE, you could try doing a reduction from a language that's already known to not be RE. One good example of this would be the diagonalization language $L\_D$:

$$ L\_D = \\{ \langle M \rangle | M \mbox{ is a TM and } \langle M \rangle \notin L(M) \\}$$

This is the set of all descriptions of TMs that don't accept themselves. You can reduce $L\_D$ to your language $L$ using the following reduction: given a TM $M$, build a new TM $N$ that does the following:

> When $N$ receives an input string $w$, it first runs $M$ on $\langle M \rangle$. If $M$ accepts its own description, then $N$ accepts $w$. If $M$ rejects its own description, then $N$ rejects $w$. (Implicitly, if $M$ loops on its own description, then $N$ loops on $w$)

This machine has the property that if $M$ does not accept itself, then $N$ never accepts anything at all, and so $\langle N \rangle \in L$. On the other hand, if $M$ does accept itself, then $N$ accepts everything, so $\langle N \rangle \notin L$. This is a mapping reduction from $L\_D$ to $L$, and since $L\_D \notin RE$, this shows $L \notin RE$.

I'll leave the second of these as an exercise. Use the same intuition as before to think about why the language isn't $RE$, then try using a mapping reduction from $L\_D$ to formalize it.

Hope this helps!
> 2 votes

---
Tags: computability
---


# Question
Title: Optimal algorithm for signaling for help?
I was thinking about the following problem the other day:

> You are stuck on a desert island with a battery-powered emergency radio. You know that if you feed enough power into the radio that you should be able to alert someone to your position. In fact, as soon as you provide the radio enough power to reach someone else, they'll respond back to you and send help.
>
> The problem is that you don't know where anyone else is, so you have no idea how much power to feed into the radio. You can assume that the radio can transmit at power levels that are natural numbers.
>
> What is the most power-efficient way to signal for help?

One inefficient solution to this would be to transmit at power $1, 2, 3, ...$ until you reach the necessary power $n$. This works, but it requires power usage $1 + 2 + 3 + ... + n = \frac{n(n+1)}{2}$.

The algorithm I currently think is optimal is to instead transmit at power $1, 2, 4, 8, 16, ... $ until the necessary power $n$ is reached or exceeded. This requires power $$1 + 2 + 4 + 8 + ... + 2^{\lceil \log\_2 n \rceil} = 2^{\lceil \log\_2 n \rceil + 1} - 1$$

which is somewhere between $2^{\log\_2 n + 1} - 1 = 2n - 1$ and $2^{\log\_2 n + 2} - 1 = 4n - 1$

My question is whether or not this is the optimal algorithm for solving this problem, given that $n$ is completely unknown. I can't seem to find a more efficient algorithm, nor can I find a proof that this is optimal.

Is there a better way to solve this problem? Or is this the optimal solution?

# Answer
> 3 votes
Your problem is very similar to the well-known cow-path problem, though the details are a bit different. When talking about optimal algorithms, we are usually concerned with minimizing the *competitive ratio* (a concept from the field of *online algorithms*), which is the worst ratio between the solution produced by your algorithm and the one produced by the optimal algorithm (in this case, $n$). If your algorithm searches the sequence $a\_1 \< a\_2 \< \ldots$ then the competitive ratio is $$ \sup\_n \frac{\sum\_{i\colon a\_{i-1} \< n} a\_i}{n}. $$ (Here $a\_0 = 0$.)

Suppose we're aiming for a competitive ratio of $C$ (your algorithm gives $C = 4$). Considering $n=1,a\_1+1,a\_2+1,\ldots$, we must have $$ \begin{align\*} a\_1 &\leq C, \\ a\_1 + a\_2 &\leq C(a\_1 + 1), \\ a\_1 + a\_2 + a\_3 &\leq C(a\_2 + 1), \\ &\ldots \end{align\*} $$ The classical solution to the cow-path problem (Searching in the plane) shows that $C \geq 4$, and so your algorithm achieves the optimal competitive ratio.

---
Tags: algorithms
---


# Question
Title: Constructing a Divide and Conquer Algorithm
I'm thinking of using something similar to the Merge Sort algorithm. So the recurrence running time of Merge Sort is T(n) = 2T(n/2) + n. What should I do about if n/2 is less than or equal to m, OR if n/2 is greater than or equal to m?

I believe the given function should be location inside the "Merge" function of the Merge Sort.(Since we're merging a sorted array) Thank you for your time.

Edited: I'm thinking if n/2 is less than or equal to m, use the "Given" function . Otherwise use the original "Merge" function (The usual Merge for Merge Sort)

# Answer
I believe you have misunderstood the question. The magical merge algorithm merges two lists of size $m$ in time $m^{1-\epsilon}$ *for every possible $m$* (of course, such an algorithm is impossible). Since merging usually takes linear time $O(m)$, it is always better to replace it with the magical merge algorithm. You then get a different recurrence for your magical merge sort, and the running time should come out linear rather than $O(n\log n)$.
> 1 votes

---
Tags: sorting, arrays, divide-and-conquer
---


# Question
Title: Where can i find literature about the $\frac{4}{3}$-conjecture for approximation of the Metric TSP?
In Graph-Theory there are many ways for efficient approximation-algorithms to solve the Metric TSP. The best solution seems to be the Christofides Heuristic with a factor of 1.5 to the optimal solution. My Teacher said, there would be the so called $\frac{4}{3}$-conjecture, which states: there might be a approximation solution for the metric tsp, that has only a $\frac{4}{3}$-factor.

But i cannot find any literature or further information about this assumption. Maybe you can?

# Answer
On the Integrality Gap of the Subtour LP for the 1,2-TSP provides some relevant references and discussion in the introduction..
> 3 votes

---
Tags: complexity-theory, reference-request, np-complete, approximation, traveling-salesman
---


# Question
Title: Given NFA to recognize a language, construct a new NFA for that language without the empty string
> Describe a (general) procedure that, given some finite automaton M, produces a new finite automaton M’ with: M’ rejects ε, but accepts otherwise the identical language as M does.Note that M may or may not accept ε, while M’ does not!

My solution is to discuss the different cases. If M doesn't contain ε, then, don't need to produce a new M', but if M contains ε-transition, then convert it to DFA. I'm not sure my procedure is right or not.

Can someone come up with some more effective idea?

# Answer
Why go for a subtle or elegant answer? You can drive a screw in with a jackhammer, too.

1. Define a DFA $M\_{\epsilon}^{-1}$ for the language $\Sigma^\* \setminus \\{\epsilon\\}$. *Hint: it has two states for any $\Sigma$.*
2. Say how to construct $M'$ such that $L(M') = L(M) \cap L(M\_{\epsilon}^{-1})$. *Hint: use the Cartesian Product Machine construction.*
> 4 votes

# Answer
Hint: Duplicate the starting state.
> 2 votes

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


# Question
Title: Proper terminology in Prolog/logical programming theory?
I have a good understanding of how to program using logic languages, but I'm currently writing up a paper describing some of my work, and I wanted to ensure that I wasn't abusing the proper terminology when describing logic languages. I have a few questions:

1. What exactly is a predicate? How does a predicate relate to rules/facts? I.e. are rules predicates but not all predicates facts and rules?
2. What is a clause, and how does it relate to a predicate?
3. When describing how a rule is tested/proven, what is the equivalent term for "calling a function"? Do we say that the rule is called, or that a goal is called?
4. What exactly is a goal? Is a goal equivalent to a query?

Like I said, I have a very good understanding of how Prolog works, just not a good knowledge of the right terms to describe the right things.

# Answer
If you understand Prolog then you're probably fine. The jargon in Prolog-land is not as fixed as you'd expect, because we really only have three things to refer to, with a dozen or more pieces of jargon to use on. These are my working definitions arrived at from reading books and reading/answering questions about Prolog on Stack Overflow. I may have a misconception in here.

This is a Horn clause:

```
foo(X) :- bar(X).

```

It has two components: the *head*, which is `foo(X)`, and the *body*, which is `bar(Y)`.

A *fact* is a Horn clause consisting of just a head:

```
uncle(bob).

```

In ISO Prolog, this is *transformed* into the equivalent clause:

```
uncle(bob) :- true.

```

Similarly, a Horn clause with only a body is just a *goal* or a *query*:

```
:- uncle(X).

```

A *predicate* is defined by a set of clauses. For instance:

```
foo(true).
foo(X) :- bar(X).
foo(X) :- succ(X0, X).

```

The predicate `foo/1` is thus defined. The `1` there is the *arity*. Every clause is a *rule*. I can talk about a bug in the second rule of the predicate or the second clause of the predicate, and in either case I am clearly referring to `foo(X) :- bar(X)`.

"Goal" and "query" can be used interchangeably. You can *prove* or *call* a goal. I would "issue" a query, not sure if others would say that. When a `Variable` is given a `value`, I would say the variable *unifies* with `value` or the variable *receives* `value`. A goal, query or call can *succeed* or *fail* (**not** "return true" or "return false"). When it succeeds, its variables will be *bound*.

So to answer your questions directly:

1. A *predicate* is a unit of code with a name and arity. Its definition is composed of one or more *clauses*. Each clause can be a *rule* or a *fact*, but that distinction is trivial and fairly useless. A predicate is made up of facts and rules. Every fact and every rule is a clause and implies a predicate.
2. Every clause is an alternative of some predicate. Every predicate has at least one clause.
3. Predicates can be called. Goals can be proven or called. Queries can be satisfied. Rules are not called (instead, they are *chosen* out of the set of alternatives while evaluating some query). `(foo(X), bar(X))` is a *compound goal*, more likely called a *query* (but never called a *predicate*).
4. Goal and query are the same.

This is confusing in Prolog because the same syntax is used everywhere. So when you see `foo(X)`, it might be a fact, or it might be a query. It can be given to a meta-predicate to be proven or it can be used simply as a structure. For instance:

```
foo(X).           % 1. "fact": foo(X) always succeeds.
foo(X) :- true.   % 2. "predicate", same as above
:- foo(X).        % 3. goal: prove foo(X). Will succeed without establishing binding.
:- call(foo(X)).  % 4. goal, same as above
:- write(foo(X)). % 5. struct: print out "foo(_G1657)" (or some other gensym variable name)

```

For me, what's still vague is when we refer to a term as a *structure* versus as a *functor*. I think these usages are basically interchangeable, but I'm not sure.
> 9 votes

# Answer
I use predicate to denote p(X) (just like this ).

A clause is a disjunction of literals: both facts and rules are (Horn) clauses (Horn) clauses . See the Horn clause wiki link on how to read Prolog rules and on what is a goal (short answer goal=query).

Hope that helps.
> 1 votes

---
Tags: terminology, programming-languages, logic-programming, prolog
---


# Question
Title: Efficiently checking if two star graphs are disjoint
I have given an undirected graph $G$ with vertex $\\{1, ... n\\}$ and two star subgraphs $S\_1$ and $S\_2$, always consisting of ALL neighbors of a given vertex, and the goal is to check wether the two star graphs have a vertex in common. This will be will be executed $M$ times for $M$ a large integer.

My approach would be to store the graph in adjacency list format and for each vertex store its adjacency list in sorted order.

We can then check in $O(M n \log n)$ time in total if two star graphs of the sequence of $M$ star graph pairs have a vertex in common.

But maybe this can be done more efficiently?

# Answer
I assume the graph $G$ is fixed, and you are doing $M$ queries on $G$.

Your algorithm takes $O(Mn\log n+t)$ time, where $t$ is the amount of time to build the adjacency list. We can use the same time, but remove the log factor by merging the neighbor of $S\_1$ and $S\_2$ list in $O(n)$ time.

If $M \in \Omega(n)$, you can just compute the result for all queries in $O(n^2)$ time. Store the result in a new matrix $N$, initially all $0$s. Set $N\_{i,j}=1$ for all $\\{i,j\\}\in \\{i|M\_{k,i}=1\\}$. Thus $N\_{i,j}=1$ iff $i$ and $j$ share a neighbor.

If you query for star $S\_i,S\_j$, it returns $\max(N\_{i,j},M\_{i,j})$, if it's $0$, then there is no common vertex for the stars.

It takes $O(M+n^2)$ time and $O(n^2)$ memory.
> 3 votes

# Answer
As Chao Xu suggests, first create the adjacency matrix $A$. However, I would then compute the matrix $N=A+A^2$ in $O(n^{2.8})$ steps by using Strassen's matrix multiplication algorithm (or in time $O(n^3)$ using nothing fancy). Now $N\_{uv} = 0$ iff the stars $S\_u$ and $S\_v$ do not intersect. This has a high setup cost, but can then support any number of queries of the form you want by a single lookup in the matrix.

To say more, one needs further information about the parameters: is $M$ larger than $n^2$, or is it between $n$ and $n^2$, or is it smaller than $n$; and what is the cost of doing a matrix lookup in your model of computation?
> 2 votes

---
Tags: algorithms, graphs
---


title: Looking for Rating Functions

text:
# Question
Title: Looking for Rating Functions
I'm looking for something i would call rating functions. I'm searching for some literature about this concept. I'm not really sure about the terminology, but what I mean should be pretty obvious.

A type of function that returns a rating of some input.

Lets have a function that gets some input and returns a number between 0 and 1 as a rating, where 0 is bad and 1 is great. Everything between is well between bad and great depending.

Lets assume inputs are just numbers

$f\colon \mathbb{N} \longrightarrow \[0,1\]$

I would like if I have several rating functions be able to compose them. For example if I have the rating functions $r\_1$, $r\_2$ I would like to compose both to a new rating function that returns a new rating in dependency to $r\_1$ and $r\_2$

Now I'm looking for literature, but was unable to find any. Can somebody hint me into the correct direction? The correct name for the concept I'm looking for would be great.

## Edit

I want to implement various Rating Functions and want to combine them

One functions could be

```
alwaysPerfect = (x) -> 1
alwaysBad = (x) -> 0
isOdd = (x) -> x%2
distanceToOne = (x) ->
  x = 2 if x is 0
  1/abs(x)

```

Anyone could implement this functions, but the contract for this functions would be to always return a value between 0 and 1

I need to evaluate some data with various evaluation conditions. Writing these evaluation seperate small functions and combine them seems to be more clearer than writing one big function that does all the evalauting

# Answer
> 1 votes
So you have a bunch of functions $f\_1, \dots, f\_k$ from $\mathbb{N} \to \[0,1\]$ and want to combine them to a new one. There is a myriad of possibilities, e.g.

* $f(n) = \prod\_{i=1}^k f\_i(n)$,
* $f(n) = \frac{1}{k} \cdot \sum\_{i=1}^k f\_i(n)$,
* $f(n) = \sum\_{i=1}^k c\_if\_i(n)$ for $\sum\_{i=1}^k c\_i = 1$ and $c\_i \geq 0$,
* $f(n) = \min\\{f\_1(n), \dots, f\_k(n)\\}$,
* $f(n) = \max\\{f\_1(n), \dots, f\_k(n)\\}$,
* $f(n) = \operatorname{median}\\{f\_1(n), \dots, f\_k(n)\\}$,
* $f(n) = f\_1( \lceil 1000 \cdot f\_2 ( \lceil 1000 \cdot f\_3( \dots )\rceil)\rceil)$,

or any other of infinitely many choices. Without context, it is impossible to know which one yields something meaningful in your context.

# Answer
> 1 votes
You question is very vague, but there is extensive work on combining weak classifiers into stronger classifiers. Perhaps that's what you mean?

For example the Adaboost algorithm can be used to find the weights you should give individual classifiers in order to combine them optimally.

---
Tags: machine-learning, mathematical-analysis, data-mining
---


# Question
Title: Can we minimise regular expressions using known DFA minimisation algorithms?
Of course, converting NFA to DFA is not a problem. But what about the other direction?

My motivation is the notion of minimization regular expressions using the DFA minimization algorithm.

# Answer
> 1 votes
You should have asked first what you wanted : your second line. Why assume that you have to reverse the determinization procedure to get back to a regular expression. You confused your readers. You might add it as a possible way you imagined to go about it, after you stated what you want, not before.

To find out how to get a RE from a FA, just search the web for : "convert finite automata to regular expressions". It is an interesting topic.

If you want a "minimal regular expression", just search for that. But I am not sure what minimal would mean (number of operators used ?).

If you want to find a "minimal NFA" search for that, but I gather it is a rather difficult problem, still under research.

If you want a "minimal DFA", search for that. It is a well explored problem.

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


# Question
Title: Is there a way to test if two NFAs accept the same language?
Or at least generate a set of strings that one NFA accepts, so I can feed it into the other NFA. If I do a search through every path of the NFA, will that work? Although that will take a long time.

# Answer
> 10 votes
The decision problem is PSPACE-complete as Shaull noted.

However, it turns out that in practice it is often possible to decide NFA equivalence reasonably quickly. Mayr and Clemente (based on experimental evidence) claim that the average-case complexity scales *quadratically*. Their techniques rely on pruning the underlying labelled transition system via local approximations of trace inclusions.

Just like SAT is NP-complete in a worst-case analysis, yet often turns out surprisingly tractable for real-world instances, it therefore seems likely that NFA equivalence can be decided efficiently for many real-world instances.

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


# Question
Title: Is this formal grammar context-free (CFG) but not context-sensitive (CSG)?
I have the following formal grammar: $$G= (\\{S,A,B\\},\\{a,b\\},R,S)$$ $$R=\\{S \rightarrow A\ |B, A \rightarrow \varepsilon\ | aA\ |bA, B \rightarrow \varepsilon\ |Bb\ | b\\}$$

Now, we see, the production rules $A \rightarrow \varepsilon$ and $B \rightarrow \varepsilon$ implies that this grammar is not context-sensitiv ($CSG$). But on the other hand, we see this grammar satisfies the conditions for a context-free ($CFG$) grammar, because every production rule has just one NON-terminal on the left side.

We know, according to the Chomsky hierarchy, a contest-free grammar imples a contest-sensitive grammar: $CFG \implies CSG$

Now i am confused, is my grammar context-free or it is not, even if it satisfies the conditions? Can it be $CFG$ without being $CSG$?

# Answer
Context-free languages are context-sensitive languages; therefore, if there's a valid CFG for a language, then there is a valid CSG for the same language. Depending on how you define CFGs and CSGs, it's possible that a CFG may not count as a CSG. It's quite often the case that CSGs aren't CFGs, even if the CSG generates a context-free language. Basically, even if CFG does not imply CSG, it is still true that CFL implies CSL. That's the confusion: the Chomsky hierarchy implies things about languages.

If your definition of a CSG says "No ϵ transitions", you're right. If it says "The only ϵ transition can be S→ϵ , then you are right. If it doesn't say something specifically excluding α→ϵ , then you're wrong. It's a matter of how you define what consistutes a valid CSG, which sounds obvious, and in fact is.
> 2 votes

---
Tags: formal-languages, formal-grammars
---


# Question
Title: Question about the formal proof of the inorder traversing
In Don Knuth's famous series of books, *The Art of Computer Programming*, section 2.3.1, he describes an algorithm to traverse binary tree in inorder, making use of an auxiliary stack:

> **T1** \[Initialize.\] Set stack $\rm A$ empty and set the link variable $\rm P\gets T$
>
> **T2** \[$\rm P=\Lambda$?\] If $\rm P=\Lambda$, go to step T4.
>
> **T3** \[Stack$\rm \\;\Leftarrow P$\] (Now $\rm P$ points to a nonempty binary tree that is to be traversed.) push the value of $\rm P$ onto stack $\rm A$, then set $\rm P\gets LLINK(P)$
>
> **T4** \[$\rm P\Leftarrow Stack$\] If stack $\rm A$ is empty, the algorithm terminates; otherwise pop the top of $\rm A$ to $\rm P$.
>
> **T5** \[Visit $\rm P$\] Visit $\rm NODE(P)$. Then set $\rm P\gets RLINK(P)$ and return to step T2.

We can plot a flow chart of the algorithm. In the succeeding paragraph, he gives a *formal proof* of the algorithm:

> Starting at step T2 with $\rm P$ a pointer to a binary tree of $n$ nodes and with the stack $\rm A$ containing $\rm A\[1\]\dotsc A\[m\]$ for some $m\ge 0$, the procedure of steps T2-T5 will traverse the binary tree in question, in inorder, and will then arrive at step T4 with stack $\rm A$ returned to its original value $\rm A\[1\]\dotsc A\[m\]$.

However, as far as I know, such a formal proof is quite different from the general method described in section 1.2.1:

> for each box in the flow chart, that if an assertion attached to any arrow leading into the box is true before the operation in that box is performed, then all of the assertions on relevant arrows leading away from the box are true after the operation.

In fact, such a method is somewhat equivalent to Hoare logic, which is used to formally check the validity of algorithms.

Can we turn the statement mentioned to prove the traversing algorithm into a schema of Hoare logic, or the assertion-attachment of a flow chart?

Thanks!

# Answer
It is definitely possible to analyze this algorithm using Hoare triples. The first step would be to replace the VISIT procedure calls with some more reasonable accounting mechanism, say a list that lists the visited nodes in order. You then define formally what a binary tree is and what an inorder traversal is, something along the following lines:

```
Tree = Leaf N | Node N LTree RTree
Inorder(Leaf N) = N
Inorder(Node N LTree RTree) = Inorder(LTree) || N || Inorder(RTree)

```

Here N is the "name" of the node, and || is list concatenation. Armed with these notions, it is an exercise to construct the required Hoare triples. You will probably need to come up with even more notions (for example, you will need to explain what the contents of the stack are when a node P is popped).

What do we gain from this exercise? Do we understand the algorithm any better? Probably not. But we understand how to reason precisely about algorithms, something which is useful if you plan on doing software verification or programming language theory, areas forming the so called "Theory B". If you're more of a "Theory A" type (algorithms and complexity) then, like me, you will find such exercises somewhat beside the point.
> 1 votes

---
Tags: algorithms, correctness-proof, graph-traversal, hoare-logic
---


# Question
Title: Name of an Exact Cover by 3 sets variant
Exact cover by 3-sets is $\sf{NP}$-complete:

> **Instance**: Given a finite set $X = \\{ x\_1,x\_2,...,x\_{3n}\\}$ of $3n$ elements and a collection $C = \\{ ( x\_{i\_1}, x\_{i\_2}, x\_{i\_3}) \\} $ of $m$ 3-elements subsets of $X$;
> **Question**: Find a subcollection $C'$ of $C$ such that every element in $X$ is contained in exactly one member of $C'$.

The problem remains NPC even if we add the following condition:

* every element of $X$ appears exactly in three subsets of $C$

Has this variant an "official" name?

# Answer
> 3 votes
Gonzalez called this variant **RXC3**, for "Restricted Exact Cover by Three Sets."

---
Tags: terminology
---


# Question
Title: Use minimum number of swaps so each bin contains balls of the same color
There are $n$ bins, the $i$th bin contain $a\_i$ balls. The balls has $n$ colors, there are $a\_i$ balls of color $i$. Let $m=\sum\_{i=1}^n a\_i$.

A swap is take a ball from one bin and swap with a ball from another bin. We want minimum number of swaps such that each bin only contain balls with the same color.

I know a easy special cases $a\_i\leq 2$ for all $i$. (If $a\_i=2$ for all $i$, then you can even do it by swapping each ball at most once.)

**Edit**: This is wrong because finding $c(D)$ is NP-hard.

~~If we know which color goes to which bin, the problem is easy.~~

~~Consider a multi-digraph $D=(V,A)$, $V=\\{v\_1,\ldots,v\_n\\}$. If we know color $i$ goes to bin $b(i)$, then there are $k$ parallel arcs $(j,b(i))$ in $A$ iff bin $j$ contains $k$ balls of color $i$. Each component of the graph is Eulerian. The minimum number of swaps required is $m-c(D)$, where $c(D)$ is the number of arc disjoint cycles that covers $A$. We can swap by "following" a Eulerian circuit. (a swap using an arc of a minimal cycle can change it to a smaller minimal cycle and a self loop). Once the entire graph is set of self loops, we have made all the necessary swaps.~~

How hard is this problem in general?

# Answer
Maximal decomposition of an Eulerian directed graph into edge disjoint cycles is NP-Hard, at least according to this book: Algorithms and Applications: Essays Dedicated to Esko Ukkonen on the Occasion of His 60th Birthday.

btw, here is an article which is relevant to the problem you seem to be trying to solve: Asymptotically optimal algorithm for the Dutch National flag algorithm.

For $n \le 6$, the paper gives a simple algorithm.
> 3 votes

---
Tags: algorithms, complexity-theory, balls-and-bins
---


# Question
Title: Is CFL closed against exchanging complementation and reversal?
Let $L$ be a language such that $\overline{L}^R$ (the reversal of the complement of $L$) is context-free. Is then also $\overline{(L^R)} \in \mathrm{CFL}$?

# Answer
> 2 votes
Hint: Show that they are the same language.

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


# Question
Title: Proof of Program Correctness - Loop Invariants
I've been reading a book on using loop invariants and induction to prove program correctness. Then I came across the following program which got me thinking...

# Specification for `Cube_Root(n)`

Pre-Condition: $n$ is a natural number. Post-Condition: `Cube_Root` returns a natural number $i$ that is the cube root of $n$ or it returns $-1$ if no such root exists

```
Cube_Root(n)
  i = 0
  while i < n
    if i * i * i = n
      return(i)
    else
      i = i + 1

  return(-1)

```

In the book, the proof proceeds by finding a loop invariant. So for example let us define the following as our loop invariant:

Loop Invariant $P(i)$: $i$ is either the natural number cube root of $n$ or $i \geq n$. The proof is then supposed to proceed by induction on $i$. So we need to prove that $P(0)$ is true, assume that $P(i)$ is true for some $i$ and then establish that if $P(i)$ is true then $P(i+1)$ is true.

$P(0)$ is trivial to prove true: if $n = 0$ then $i$ is a natural number and the the cube root of $n$ otherwise $n \> 0$ (since $n$ is a natural number) and hence $i \< n$.

However, the problem arises when you try to infer $P(i+1)$ from $P(i)$. it doesn't look like you can because if $i$ is not the cube root of $n$, it doesn't tell you anything about whether $i+1$ is or is not the cube root of $n$.

So my question(s) are:

1. Has it been proven that for any program there exists a loop invariant on which you can use induction to prove the program is correct?
2. The loop invariant chosen for `Cube_Root` is obviously true after the loop terminates which proves that the post-condition of the program is satisfied. Hence, that proves partial correctness of the program. However, we did not need to use induction to prove that. Is that an acceptable proof? If not, how do we use induction to prove Cube\_Root correct?

# Answer
> 4 votes
## Generalities

Regarding your first question, the correctness of every loop (without fancy control flow!) can always be proven using a loop invariant which states *all* the possible values of all variables. In your case (or rather in the modification below), this loop invariant would be $$ (n,i,r) \in \\{(0,0,-1),(0,0,0),(1,0,-1),(1,1,-1),(1,1,1),(2,0,-1),(2,1,-1),(2,2,-1),(2,3,-1), \ldots \\}. $$ Of course, this invariant isn't particularly helpful, though it can certainly be used to prove the correctness of the loop. A more delicate issue is whether we can actually express the invariant in any formal sense - when the loop always terminates as in this case, the set of possible values of the variables is certainly computable.

Regarding your second question, when you're using a loop invariant you always reason by induction - that's how you know that the loop invariant is actually maintained. Consider the following problem:

```
x, y = 0, 1
for i in range(n):
    x, y = y, x + y
return x

```

I claim that this program computes the $n$th Fibonacci number $F\_n$. Here is a "loop invariant" that can be used to prove it: *if $i = n$ then $x = F\_n$*. Of course, this is not really a loop invariant since you can't prove that it's maintained by the loop; an actual loop invariant is $(x,y) = (F\_i,F\_{i+1})$.

Your suggested loop invariant is like the first example above - it's simply not a loop invariant, and in particular it's not clear how you'd prove that if the loop terminates then it holds. It might seem "trivial", but this argument doesn't constitute a formal proof. In contrast, if you use an actual loop invariant, then you can use induction to prove that the loop invariant is maintained throughout the loop, and in particular is satisfied if the loop terminates. That's more formal, and can be turned into an actual formal proof (in the sense of program verification or axiomatic logic).

Whether your type of proof is acceptable or not depends on the venue. If this is a question in a course in which you're supposed to learn how to write this kind of formal proofs, then your answer isn't acceptable. In an algorithms class, it might be acceptable since the proof is "obvious". Ask your professor if in doubt.

## Specifics

We now turn to the problem at hand.

The idea of a loop **invariant** is a condition which is true *throughout* the loop. As you mention, the condition that you describe is only true after the loop terminates (in the return statement). Ergo, it's not the correct condition. First, let's modify the program in the following way: instead of returning $i$, let's have a variable $r$ initialized with $-1$; when $i^3 = n$, assign $r = i$ and break out of the loop. Throughout the loop one of the following is always true, assuming $n \> 1$ (for $n = 0,1$ the program fails; the condition in the main loop needs to be $i \leq n$ instead of $i \< n$):

1. $i^3 \< n$ and $r = -1$.
2. $i^3 = n$. In this case, $r = -1$ if the loop hasn't terminated, and $r = i$ otherwise.
3. $\sqrt\[3\]{n} \notin \mathbb{Z}$ and $i^3 \> n$ and $r = -1$.

The second condition isn't quite of the usual form, and that is because usually *break* statements are not allowed. You can correct this by modifying the code as follows (this code also corrects the bug mentioned above):

```
r = -1
i = 0
while i <= n and r == -1:
    if i*i*i == n:
        r = i
        continue
    else:
        i = i + 1
return r

```

Now the loop invariant becomes:

1. $i^3 \< n$ and $r = -1$.
2. $i^3 = n$ and $r \in \\{-1,i\\}$.
3. $\sqrt\[3\]{n} \notin \mathbb{Z}$ and $i^3\>n$ and $r = -1$.

Now the loop termination condition makes it clear that if $i \leq n$ then necessarily $r \neq -1$, and so by the loop invariant, $r = i$.

---
Tags: loop-invariants, program-correctness
---


title: Count number of special onto functions

text:
# Question
Title: Count number of special onto functions
We define an **onto** function from $\[n\] \times \[n\]$ to $\[n-2\] \cup \\{0\\}$ as follows, where $\[n\] = \\{1,2,3,\ldots ,n\\}$,

$$f : \[n\] \times \[n\] \rightarrow \[n-2\] \cup \\{0\\}.$$

1) $f(x,x) = 0$.

2) $f(x,y) = f(y,x) \> 0$, for $y ≠ x$.

3) $f(x,y) \leq \max\\{f(x,z),f(z,y)\\}$ for all $x,y,z$ belonging to $\[n\]$.

How many such functions are possible for a given $n$? I have tried my best but I am not able to get any close to the solution! One may even see it as a undirected simple graph with n vertices, f(x,y) representing the edge weights. Any help is appreciated!

EDIT: i have been able to find that there are no such functions for n\<3.

for n=3 we have one such function, for n=4, 13 are possible.

# Answer
The parametrization you present is quite arbitrary, and the condition that the mapping be onto only serves to confuse; let's ignore it for now. Instead, given $n,c$, let us consider the number of colorings of $K\_n$ using $c$ colors (in your case, $c=n-2$) such that condition (3) is satisfied: for every three vertices $i,j,k$, $$ c(i,j) \leq \max(c(i,k),c(j,k)). $$ What does this condition *mean*? Let's start by considering the case $c = 2$. For any triangle $i,j,k$, the only situation which is forbidden is $$ \\{c(i,j),c(i,k),c(j,k)\\} = \\{1,1,2\\}. $$

Let $G$ be the graph formed by the edges colored $1$. This condition states that if $(i,j),(i,k) \in G$ then also $(j,k) \in G$. It is not hard to prove that $G$ must be a disjoint union of cliques, and vice versa, every disjoint union of cliques satisfies the condition.

If $G$ is a disjoint union of cliques then the vertex sets of the cliques partition $\[n\]$; isolated vertices are considered as cliques of size $1$. Therefore the number of possible graphs (and so, possible colorings when $k = 2$) is the Bell number $B\_n$.

The case of general $c$ is similar. Consider for example $c = 3$. The graph induced by edges colored $1,2$ must be a disjoint union of cliques, and within each such clique, the graph induced by edges colored $1$ must be a disjoint union of cliques. Therefore each possible coloring corresponds to a two step partition of $\[n\]$: first we partition $\[n\]$, and then we further partition each of the part. The number of such two step partitions is a so-called higher-order Bell number, the row $p = 2$ in this case. For general $c$, consult this table at row $p = c-1$.

Finally, what if we want to count the number of **onto** mappings? We can use the inclusion-exclusion principle. Let $X(n,C)$ denote the number of colorings using colors from $C$, and let $X(n,c) = X(n,\[c\])$; note that $X(n,C) = X(n,|C|)$. Also let $Y(n,C),Y(n,c)$ denote the number of **onto** colorings. We have

$$ Y(n,c) = Y(n,\[c\]) = \sum\_{D \subseteq \[c\]} (-1)^{c-|D|} X(n,D) = \sum\_{i=0}^c (-1)^{c-i} \binom{c}{i} X(n,i). $$

For example, if $n = 4$ and $c = 2$ then $$ Y(4,2) = \binom{2}{0} X(4,2) - \binom{2}{1} X(4,1) + \binom{2}{2} X(4,0) = 1 \cdot 15 - 2 \cdot 1 + 1 \cdot 0 = 13. $$

How do we compute $X(n,c)$? The page linked to above gives the following recurrence:

$$ X(n,1) = X(0,c) = 1, \quad X(n,c) = \sum\_{k=1}^n \binom{n-1}{k-1} X(k,c-1) X(n-k,c). $$
> 5 votes

---
Tags: combinatorics, permutations
---


title: Broadcast with Limited Spreading

text:
# Question
Title: Broadcast with Limited Spreading
Let consider well-known problem in distributed computing Broadcast Problem in network with stopping crashes.

The most appropriate solution to the broadcast problem is flooding algorithm, when the source of the message just send it to all available nodes of the network on the first round, if there are crashes on the edges some number of message will fail. Then on the second round, the nodes that received messages from the previous round send it to all available nodes and so on.

Let consider slightly different model, when on every round the source node with message is capable to send a message to only one single node of course stopping failure might occur. It's very useful model, which can represent a sort of controllable or limited spreading.

Unfortunately I don't know the formal name of the model. Do you familiar with result in the model of "limited spreading", I am sure there are must some work in this direction.

# Answer
> 1 votes
Both models you presented are the same with a slight modification. Theoreticians usually don't care about the difference between both except when calculating time complexity (or number of sent messages in radio networks sometimes).

The first model you presented, broadcast communication, the broadcast operation is only allowed. That is, a node $v$ may send at one time slot a message to all its neighbours, denoted $N(v)$.

In the second model, point-to-point communication, for a node to send a message to all its neighbours, it needs to send $|N(v)|$ messages each of which is at a different time slot. Therefore, we emulate the broadcast operation.

In the broadcast model, in order to emulate the point-to-point communication from $v$ to $u$, a node $v$ broadcasts a message that contains the identifier of $u$. If $u$ receives the message and finds that it contains its identifier, then it accept it. Otherwise, it just throw it.

does that answer your question ?

# Answer
> 1 votes
Canonical solutions to the broadcast problem include, as you mention, flooding (controlled & uncontrolled, although uncontrolled flooding is untenable for a variety of reasons), as well as spanning-tree based approaches and N-way unicast (which is basically just to point out that broadcast protocols don't represent fundamentally more powerful communication mechanisms).

What you're asking about sounds somewhat similar to a sort of controlled flooding with fault tolerance. Alternatively, you might conceive of your scheme as a spanning-tree approach where multiple redundant spanning trees are defined for each node. In fact, a hybrid of these approaches would help avoid loops, explosion, etc.

Kurose and Ross provide a good explanation in their book "Computer Networks - A Top Down Approach", which you might use to develop your own broadcast protocol.

---
Tags: distributed-systems
---


# Question
Title: Is the set of codes of Deterministic Finite-State Automata a regular language?
Let $\Sigma$ be a given alphabet. Is there a way to code up Deterministic Finite state Automata (DFA) over $\Sigma$ as strings of $\Sigma$ in such a way that the corresponding subset of $\Sigma^\*$ is a regular language?

For example for Turing machines, the set of codes of Turing machines over a fixed alphabet is decidable, and we can speak of decidable sets of Turing machines (through their codes).

Of course we can also speak of regular sets of DFA's (through their codes). Is the set of all DFA's regular in this sense?

# Answer
> 4 votes
This answer is, in a sense, a completely cheating approach, but it is indeed possible to encode all DFAs as strings.

We can write out a DFA by writing out its transition table. We can write out the transition table using just 0s and 1s as follows: first, write out a number of 1s equal to the number of states, then a 0. Then, write out a number of 1s equal to the number of symbols in the alphabet, then a zero. Then, write out each row of the transition table by writing out each entry as a number of 1s indicating which state should be transitioned into, then a 1.

Now, this particular encoding of a DFA is **not** regular. However, what we can do is the following. Consider the set of all such encodings. We can then order them in length-lex order, and then can number the DFAs produced this way 0, 1, 2, 3, 4, ..., etc. based on their ordering. In this case, we now have a bijection between $\mathbb{N}$ and the set of all DFAs. From there, we can then consider the regular language consisting of all natural numbers written out in binary. This set is definitely regular; here's a regular expression for it:

> 0 | 1(0|1)\*

So we now have a regular language consisting of encodings of DFAs. The encoding is not at all easy to work with - you'd have to start listing off all encodings of DFAs until you found the one you were looking for - but mathematically it is well-defined.

# Answer
> 0 votes
DFAs can be stored in a regular way:

We assume $\\#\notin \Sigma$ and define

$$L = \\{\\#\\#e\mid e \in \\{0,1\\}^\*\\}^\*\cdot\\{\\#s\\#b\mid b \in \\{0,1\\}^\*,s\in\Sigma\\}^\*\quad ,$$

which is clearly regular. Then for $w\in L$ such that $w = \\#\\#e\_1\dots \\#\\#e\_o\\# s\_1\\#b\_1\\#\dots\\#s\_n\\#b\_n$ we define

$$p\_0 = 1, p\_i = \min\\{r\_{i-1},n\\}$$ where

$$r\_i = \min\\{j\>p\_i\mid \exists k, p\_i \leq k \< j: \ s\_j = s\_k \\}$$

is the index of the first symbol repetition *after* $p\_i$. Let $\\{p\_1,\dots,p\_k\\}$ be the set definable in this way. Now we construct a DFA: The set of states will be $Q=\\{1,\dots,m\\}$, where $m=\max(\\{k\\}\cup\\{\mathrm{bin}(b\_i)\mid 1\leq i \leq n\\})$ and for the sake of simplicity we choose $1$ as the starting state. The set of accepting states shall be $E=\\{\mathrm{bin}(e\_i)\mid 1\leq i \leq o\\}$. By our interpretation of the string $w$, each part $\\#s\_{p\_i}\\#,\dots,\\#b\_{p\_{i+1-1}}$ contains each $s\in\Sigma$ at most once and for each such $s$ a binary string. We'll interpret this string as target for our transition function $\delta: Q\times \Sigma \to Q$:

$$\delta(i,s)=\begin{cases}\mathrm{bin}(b\_j) & \exists p\_i,j: p\_i\leq j \< \min\\{p\_{i+1},n\\}, s\_j=s \\ 1 & \text{else}\end{cases}$$

Now $(\Sigma,Q,\delta,1,E)$ is a DFA. On the other hand it's obvious that any DFA can be sored this way (after renaming the states).

# Answer
> -2 votes
I have no idea, but my intuition is that you couldn't. You are basically asking if you can implement a regexp matcher with a push-down automaton, and I don't think you can... The regexp can be arbitrarily complex, so there is no way you can store all the state necessary in the push-down automaton states, so you'll need to use the push-down to store the state of where you are in the regexp (and/or the word)... And the problem with the push-down, is that you won't be able to do backtracking if you take a wrong turn in the regexp (in a normal automaton you have a state covering for each wrong turn possible, because all the possible combinations are known when you determine the number of states for the automaton, but I think that doing this in the push-down would require backtracking, and I don't think you can implement that)...

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


# Question
Title: Priority queue with ubounded number of elements (i.e., with dynamic storage)
I'm looking for a data structure that can work as a priority queue with reasonable maintenance complexities (like $O(\log n)$ for insertion and deletion) and that has a theoretical unbounded limit for its number of elements (like a tree structure, that is bounded only by the computer's available memory, and unlike a traditional heap, that uses an static array, which is too costly to augment).

The reason is that I'm implementing a program that makes use of a priority queue and I don't know *a priori* how many elements I'm going to insert in this queue at once, so sometimes I'm out of space to add another element.

There is no way to estimate this number, and to create a huge array to support a static type of queue is a terrible option, as maybe not even a half of it will be used and I'll be short on memory to allocate other objects.

I've heard of something like a *Dynamic Heap* (or something in the like) that is some sort of linked list of arrays, whose elements are dynamically allocated when needed, but I'm not sure this is the best strategy to follow, moreover, I would like to know if there were other options.

---

Just for the record, I'm implementing a Branch-and-Bound algorithm for solving a linear integer optimization problem, with each node stored on the queue being the abstraction of an active node on the algorithm. The number of active nodes cannot be estimated at any time, so a theoretically unbounded queue would help a lot.

# Answer
I don't understand your claim that a traditional heap is too costly to augment. If the heap is currently of size $N$ and the $N+1$st element is inserted, allocate a new array of size $2N$ and copy the old heap into its prefix. This takes amortized constant time. You can also shrink the heap in this way, for example if it is only half full you can shrink it to two-thirds of its size.
> 4 votes

# Answer
At the cost of some space and time (affecting only the constant factors), you can implement vectors (i.e. dynamic arrays) whose operations are $O(1)$ *worst case* (and not amortized).

If you have $n$ elements in the vector and it is full, you allocate a new chunk to hold $\alpha n$ elements (where $\alpha \gt 1$ is some constant, which you can parametrize). Don't copy over the old elements just yet (like the standard vector algorithm), and keep the old array around. Instead of using $\alpha n$ space, you use $(1+\alpha)n$ space.

Every time a new element is inserted (i.e. index beyond $n$), you insert that into the new array, *and* you copy over a constant number of elements (determined based on $\alpha$ and your machine/insert characteristics) from the old array to the new.

You deallocate the old array only when you have made sufficient insertions to copy over all the old elements.

Array reads will also become slightly slower, as you will now have a switch to determine which array to access (but still $O(1)$), and memory usage will be slightly more, but that can be tweaked by choosing appropriate $\alpha$.
> 1 votes

# Answer
After browsing for "priority queue" pages, I was finally convinced that some of the already known dynamic storage data structures can be adapted trivially to provide a good priority queue.

I'd already heard of the Binomial Heaps and Fibonacci Heaps, but I didn't know their implementation specifics. Self-balancing binary search trees, like AVL Trees and Red-Black Trees can also be used, since keeping track of the smallest element is simple and updating this reference is fairly cheap.

Then I discovered a new data structures: Brodal Queues, which seems to be very hard to be used in practise, according to the author.

Bear in mind that none of these structures rely on static arrays, but in linked structures, so that rearranging them does not involve lots of memory moves. This is the property I was looking for.

I'm sure that there are more structures like these that can be used as theoretically unbounded priority queues, and this is why I'm marking this answer as a community wiki, so others can increase this list.
> 1 votes

---
Tags: data-structures, efficiency, priority-queues
---


# Question
Title: How this expression leads to the given sequence
Here given is a sequence from OEIS.

The sequence is triangle of coefficients from fractional iteration of e^x - 1. Few terms are:
1, 1, 3, 1, 13, 18, 1, 50, 205, 180, 1, 201, 1865, 4245, 2700, 1, 875, 16674

The expression of finding the sequence is also given as:
A(n;x) for n-th row satisfies
A(n;x) = Sum\_{k=0..n-1} Stirling\_2(n, k)\*A(k;x)\*x, A(1;x) = 1.

The tabular view shows the entries row wise. Stirling\_2(n,k) is most probably stirling numbers of the second type

I am not able to get how above expression is resulting in the given sequence.
In summation, k begins from 0, but nothing is mentioned about A(0;x). I assumed it to be 0, but still can't get the above values.
Please explain how the first few terms are resulting from the expression.

# Answer
> 2 votes
Stirling numbers of the second type satisfy $$ \newcommand{\stirling}\[2\]{\genfrac\\{\\}{0pt}{}{#1}{#2}}\stirling{n}{0} = 0, \qquad (n \neq 0)$$ and so there is no need to define $A(0;x)$, and so the formula seems to work. You can also play with the Mathematica code which can be found in the entry corresponding to the sequence. I am puzzled, however, what is meant by "fractional iteration of $e^x-1$".

The recurrence given is for *generating functions*. Let's rewrite it: $$ A\_1(x) = 1, \qquad A\_n(x) = \sum\_{k=1}^{n-1} \stirling{n}{k} A\_k(x) x. $$ Using a table for the Stirling numbers, we get $$ \begin{align\*} A\_1(x) &= 1 \\ A\_2(x) &= \stirling{2}{1} A\_1(x) x = 1 \cdot 1 \cdot x = x \\ A\_3(x) &= \stirling{3}{1} A\_1(x) x + \stirling{3}{2} A\_2(x) x = 1 \cdot 1 \cdot x + 3 \cdot x \cdot x = x + 3x^2 \\ A\_4(x) &= \stirling{4}{1} A\_1(x) x + \stirling{4}{2} A\_2(x) x + \stirling{4}{3} A\_3(x) x \\ &= 1 \cdot 1 \cdot x + 7 \cdot x \cdot x + 6 (x + 3x^2) x = x + 13x^2 + 18x^3 \end{align\*} $$ and so on. The numbers in the table are $a(n,k) = A\_n(x)|\_{x^k}$ : $$ \begin{align\*} a(2,1) &= 1, \\ a(3,1) &= 1, \\ a(3,2) &= 3, \\ a(4,1) &= 1, \\ a(4,2) &= 13, \\ a(4,3) &= 18, \end{align\*} $$

If you prefer an actual recurrence on the coefficients, here is what you get: $$ \begin{align\*} a(n,l) = \begin{cases} 1 & l = 1, \\ \sum\_{k=l}^{n-1} \stirling{n}{k} a(k,l-1) & l \> 1. \end{cases} \end{align\*} $$

---
Tags: discrete-mathematics
---


# Question
Title: Classes of NFAs which allow efficient subset testing or unambiguity conversions
I'm doing some research regarding NFAs and inclusion problems with them. I know that in general, the inclusion problems, and converting to an unambiguous NFA, are both PSPACE-complete.

I'm wondering, are there any sub-classes of NFA for which these can be decided efficiently? In particular, the NFAs I'm looking at accept finite language where all words have the same Parikh vector.

# Answer
> 2 votes
here are three refs that may be helpful.

> We show that language inclusion for languages of infinite words defined by non- deterministic automata can be tested in polynomial time if the automata are unambiguous and have simple acceptance conditions, namely safety or reachability conditions. An automaton with safety condition accepts an infinite word if there is a run that never visits a forbidden state, and an automaton with reachability condition accepts an infinite word if there is a run that visits an accepting state at least once.

this 2nd ref is more indirect & would rely on a mapping between NFAs and tree automata.

> We show the signiﬁcantly improved efﬁciency of this framework through a series of experiments with verifying various programs over dynamic linked tree-shaped data structures

the above ref also cites the following:

> We show that on the difficult instances of this probabilistic model, the antichain algorithm outperforms the standard one by several orders of magnitude. We also show how variations of the antichain method can be used for solving the language-inclusion problem for nondeterministic finite automata...

# Answer
> 2 votes
As a negative example, It is shown in this paper by Kozen that given DFAs $A\_1,...,A\_n$, deciding whether $\bigcup\_{i=1}^n L(A\_i)=\Sigma^\*$ is PSPACE-complete (a direct result of Lemma 3.2.3 in the paper).

Thus, deciding containment even for finitely-ambiguous NFAs is PSPACE-complete.

While this doesn't mean that your case cannot be decided efficiently, it does give some evidence that it might not be.

---
Tags: complexity-theory, formal-languages, automata, finite-automata, nondeterminism
---


# Question
Title: A regular expression for strings with at most one triple of adjacent zeroes
I am trying to come up with a regular expression for the following language:

> The set of all strings with at most one triple of adjacent 0s.

What does "triple of adjacent 0s" mean? Does it mean 010101, or something else?

# Answer
> 3 votes
It's hard to say for sure precisely what is meant by "triple of adjacent 0s". My best guess would be that it means the substring 000. In this case, an easy way to get a regular expression is to find an expression for strings with no such substring, and a regular expression for strings with exactly one such substring, and then take the union.

No such substring: $r = (1 + 01 + 001 )^\*(\epsilon + 0 + 00)$ should do it.

Exactly one such substring: $s = (1 + 01 + 001 )^\*000(1 + 10 + 100 )^\*$ looks promising, but you should check it to be sure.

If my interpretation is correct, your answer would be $r + s$. In fact, and again, I may be jumping the gun here, I think that this can "simplify" (?) to something like $(1 + 01 + 001 )^\*(\epsilon + 0 + 00 + 000)(1 + 10 + 100 )^\*$.

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