# Question
Title: What is a "contradiction" in constructive logic?
In *Practical Foundations for Programming Languages*, Robert Harper says

> If for a proposition to be true means to have a proof of it, what does it mean for a proposition to be false? It means that we have a *refutation* of it, showing that it cannot be proved. That is, a proposition is false if we can show that the assumption that it is true (has a proof) contradicts known facts.

But then, this begs the question- what is a *contradiction* in constructive/intuitionistic logic?

Is this meant in the sense of deriving $(\bot\text{ true})$ somehow? How would this happen in a sensible way? Would a judgment of the form $(A \supset \bot \text{ true})$ need to be introduced?

Alternatively, is it perhaps meant in the sense of the reader using their discretion to informally label something as contradictory? For example, interpreting $a = b$ and $a \neq b$ as conflicting propositions.

# Answer
> 15 votes
It is immaterial whether we speak about constructive or classical logic in this situation. If you read your questions again, you will see that they apply to boths kinds. The only difference that we need to take notice of is the presentation of *negation* $\lnot A$. It can be presented in several ways classically, but intuitionistically it is best to use it as an abbreviation for $A \Rightarrow \bot$ (which is precisely what Bob Harper is hinting at in the quoted paragraph). But let us not confuse negations and contradictions.

In both cases, **a contradiction is a situation in which we have managed to prove falsity $\bot$**. How could we derive $\bot$ in a sensible way? Well, from an inconsistent set of hypotheses, that wold be a sensible way to do it.

You have *no discretion* to "declare" a contradiction. You must *prove* that a given set of hypotheses is contradictory by deriving $\bot$. For instance, if $a = b$ and $\lnot (a = b)$ then we may use the fact that $\lnot (a = b)$ is an abbreviation for $(a = b) \Rightarrow \bot$ and conclude $\bot$ by modus ponens.

# Answer
> 8 votes
A contradiction is usually represented as $A \land \lnot A$. It's typical in intuitionistic logic to *define* $\lnot A$ as $A \Rightarrow \bot$. It's clear we can derive $\bot$ from $A \land \lnot A$. Ultimately, a contradiction will be a hypothetical derivation of $\bot$ as the very definition of $\lnot$ suggests. It will be hypothetical because otherwise your logic is inconsistent.

The point Harper is making is that to prove something is to *have* a proof and to refute something is to *have* a proof that it implies $\bot$. However, you can easily be in the situation that you can (meta-logically) *prove* that you are unable to provide *either* a proof or refutation. In such a situation, the proposition is neither constructively true nor false.

A way to understand classical logic and contrast it to the above is the following (essentially Kolmogorov's double negation interpretation): we say a proposition is *false* if it implies a contradiction, i.e. it implies $\bot$. A proposition is *true* if we can prove that it can't be contradicted, i.e. we can show assuming it is false leads to a contradiction. In symbols, $A$ is false in this sense if $A \Rightarrow \bot$, as usual. $A$ is true in this sense if $\lnot A \Rightarrow \bot$, i.e. $\lnot \lnot A$ is provable. You can show that the the Law of the Excluded Middle holds constructively if we interpret "true" and "false" in this sense. That is, you can prove that $\lnot \lnot (\lnot \lnot A \lor \lnot A)$ holds constructively. More compactly, you can show $\lnot \lnot \lnot A \Rightarrow \lnot A$. With this notion of "true" and "false", we can say that a proposition is true if we can prove that no refutation exists. By contrast, constructively a proposition can fail to be constructively true even if we can demonstrate within the system that no refutation can exist.

---
Tags: logic
---


# Question
Title: Does XML covers the representation of any structured data and knowledge
I see nowadays XML is used to structure any file or data. It can represent both flat and hierarchical relationships. For example, it can be used to show the parse tree of a sentence in a natural language.

I am not familiar with different types of data and knowledge structures, but I would like to know if XML is theoretically the ultimate representation scheme which can model and structure any data and knowledge?

What are the reasons behind the popularity of XML?

# Answer
> 6 votes
XML is nothing more than a well-defined way to store trees of strings. Since even plain strings can encode everything you can encode in practice (i.e. countable sets), yes, XML can "model" everything.

But that's nothing special.

The popularity of XML is probably due to

1. it being standardized and
2. the amount of tool support that has developed.

There is no information-theoretic miracle involved.

# Answer
> -3 votes
Is XML the ultimate representation scheme? No:

> When the markup overhead exceeds 200%, when attributes values and element contents compete for the information, when the distance between 99% of the "tags" is /zero/, when the character set is Unicode, and when validation takes more time than processing, not to mention the sorry fact that information longevity is more /threatened/ by XML than by any other data representation in the history of computing, then SGML has gone from good kid, via bad teenager, to malfunctioning, evil adult as XML.
>
> As for writing SGML/XML/HTML/whatever, I have a simple way to get rid of the annoying verbosity of these stupid languages while *retaining* that mistake between attribute values and elements, because it is quite hard to make simple regular expression-based conversions retain enough data about an element to decide what should be attribute and element. An element has the form `<name [attributes] | [contents]>`. Attributes have the form `<name | value>`. Internal whitespace is only for readability.

`XML Enamel (NML) CL`

`<foo/> <foo> (foo)`

`<foo bar="zot"/> <foo <bar|zot>> (foo (bar "zot"))`

`<foo>zot</foo> <foo|zot> (foo "zot")`

`<foo bar="zot">quux</foo> <foo <bar|zot> |quux> (foo (bar "zot")"quux")`

`<foo>Hey, &quux;!</foo> <foo|Hey, [quux]!> (foo "Hey, " quux "!")`

`<foo>AT&T you will</foo> <foo|AT&T you will> (foo "AT&T you will")`

`<foo><bar>zot</bar></foo> <foo|<bar|zot>> (foo (bar "zot"))`

> So I have almost none of the annoying and arbitrary quote/escape mania in attribute values or contents alike, either. Entities I write as \[name\], and they end up in the Lisp version as symbols if not the character they represent purely for syntactic reasons. Writing "code" in this language is actually amazingly painless compared to the produced noise. Besides, with a few simple modify-syntax-entry calls in Emacs, I get `<` and `>` to match and blink and I can move up and down the structure very easily.

What are the reasons behind its popularity? Well:

> Inspired by the success of GML, the American National Standards Institute (ANSI) Committee on Information Processing assembled a team, with Goldfarb as project leader, to develop a standard text-description language based upon GML. The GCA GenCode committee contributed their expertise as well. Throughout the late 1970s and early 1980s, the team published working drafts and eventually created a candidate for an industry standard (GCA 101-1983) called the Standard Generalized Markup Language (SGML). This was quickly adopted by both the U.S. Department of Defense and the U.S. Internal Revenue Service.
>
> A number of industries, including the aerospace, automotive, telecommunications, and computer software industries, have been using hub languages to perform data interchange for years, and by this time the process is well understood. Typically, the major players in an industry form a standards consortium tasked with defining a Document Type Definition, which is the way in which the tag set and grammar of a markup language are defined. This DTD can then be sent with documents that have been marked up in the industry standard language using off-the-shelf editing tools, and any standard application on the receiving end can validate and process them.
>
> The XML solution is system-independent, vendor-independent, and proven by over a decade of SGML implementation experience. XML merely extends this proven approach to document interchange over the Web. Interestingly, the same day on which the first XML 1.0 draft was released also saw the formal announcement of an SGML initiative within HL7, the standards organization for health care IS vendors, to develop a Health Care Markup Language designed to solve exactly the kind of problem described in this example.
>
> Previous vertical-industry efforts have shown that capturing data in a rich markup often has benefits beyond the immediate requirements of data exchange. In a well-designed standardized patient data system, for example, specific information originally gathered in the course of a routine physical exam and tagged `<allergies>`, `<drug-reactions>`, and so on would instantly be available to alert the staff of an emergency room that an unconscious patient from a distant city was allergic to penicillin. The ability of XML to define tags specific to an area of application is critical to this scenario, because the otherwise unqualified word "penicillin" in the thousands of pages of a patient's entire medical history could not trigger the recognition that the same word inside an `<allergies>` element could trigger.

**References**

---
Tags: data-structures, database-theory, knowledge-representation
---


# Question
Title: Which is the best data structure for searching under these conditions
I have a system with some factors, say A, B, C, and D. There can be different values of all these factors. Let us consider few values to have a better understanding.

Let's say A has 4 different values, A1, A2, A3, A4. B may have 3 or 5(anything, no order or logic here), similarly C and D may also have many different values.

What I have to do is keep count of is how many times a given combination occurs.

For e.g., one combination is A1, B1, C1, D1. Another may be A1, B1, C2, D1 and so on.

I need to read the count of occurrences of these combination once from a text file, and search for it when queried, and give the corresponding count. There is **one more condition**. There is a threshold for the count. For example, let's say the threshold is 10. If the count for (A1, B1, C1, D1) is less than 10, then I need to find the count of (A1, B1, C1, Dany), if this is less than 10, then just (A1, B1, Cany, Dany) or (A1, B1).

A **trie** might have been an option, but searching will take more time than hashmaps there.

Which would be the best data structure to do so in Java?

Of course, the simplest and most obvious solution is to use hashmaps. But the factors(A,B,C,D) may be ten or twenty, and may take thousands of values. Though the file where I am reading values from is updated only once a day, so updating the hashmap is not a problem, but I am not sure if storing this amount of data at once in a DS is possible or not. Also loading it into hashmaps is going to take a lot of space I guess, as we are going to store all the possible permutations in the hashmaps.

Thank you in advance for all your suggestions and efforts, much appreciated.

# Answer
> 1 votes
**Edit:** Seems like my proposed structure is not more efficient than a HashMap with additional entries like (A3,B1,Cany,Dany).

# Typical values

There are F=20 factors (A, B, ..., T)
Each factor has V=1000 values (A1, A2, ..., A1000).
A lot of combinations (A524,...,T123) do no appear at all. The data structure should be sparse.

## Suggestion: Use the following tree structure

* Non-root Nodes represent a factor-value (for instance A1).
There can be multiple nodes per factor-value.
* Per Node Xx we store
    + The number of (...Xx, Yany, Zany, ...) in the structure
    + A HashMap from Y1,...,YV to the corresponding nodes.

# Example

We have the factor-values
A1–A3, B1–B2, and C1–C4.
In our text, the following combinations appeared:
2 times (A1, B1, C1), 1 time (A1, B1, C4), 4 times (A1, B2, C4)

Then our tree looks like the one in the picture below.
The counter per node is green, the hashmap is red.

# Operations and costs

Insertion is O(F). Query (using "any" or not, and using threshold or not) is O(F).
In case the number of factors F is constant, operations are O(1).

### Insertion

We found x new occurrences of combination (Aa, Bb, ..., Nn) and want to update the structure.

```
curNode := rootNode
for nextFactorValue in (A_a, B_b, ..., N_n)
    nextNode := curNode.hashMap[nextFactorValue]
    if (nextNode == null)
        nextNode := new Node(nextFactorValue)
        curNode.hashMap[nextFactorValue] := nextNode
    endif
    curNode.count := curNode.count + x   // update the "any" counts
    curNode := nextNode
endfor
curNode.count := curNode.count + x     // update the concrete count

```

Should you want to decrement the stored counts, you may want to remove nodes once their counter hits 0.

### Query

Retrieve $count(a,b,...,i)$ = number of found (Aa, Bb, ..., Ii, jany, ..., Nany)

```
curNode := rootNode
for nextFactorValue in (A_a, B_b, ..., I_i)
    nextNode := curNode.hashMap[nextFactorValue]
    if (nextNode == null)
        return 0
    endif
    curNode := nextNode
endfor
return curNode.count

```

### Query with threshold

Compute $ count\_t(a,b,...,m,n) = \begin{cases} count\_t(a,b,...,m),& \text{if } count(a,b,...,m,n)\<t\\ count(a,b,...,m,n),& \text{otherwise} \end{cases} $

```
curNode := rootNode
for nextFactorValue in (A_a, B_b, ..., N_n)
    nextNode := curNode.hashMap[nextFactorValue]
    if (nextNode == null || nextNode.count < t)
        return curNode.count
    endif
    curNode := nextNode
endfor
return curNode.count

```

---
Tags: algorithms, data-structures, java
---


# Question
Title: Less used data (1 byte) in memory address holding 4 bytes
I need to store two distinct variables of 1 byte size in memory.

My memory system stores 4 bytes at one address; therefore, you cannot address byte 3 directly, and you have to logically access it after all 4 bytes are fetched of that address (correct me if I'm wrong please).

So, if I assign the following two variables: `char var1 = "a"` and `char var2 = "b"`,

Will my system store them in memory at two different addresses?

Will 3 bytes in each of those addresses be useless (i.e., will the two variables occupy 8 bytes of memory)?

# Answer
So your computer has 32 bits as the smallest addressable unit.

Your compiler has two choices: It can store var1 and var2 in two different sets of 8 bits in the same 32 bit unit, or it can store var1 and var2 in to different 32 bit units. The former produces likely more code, the latter uses more memory. It's up the compiler to decide.

If your programming language supports "pointer to char" as a type, then a pointer to var1 and a pointer to var2 will be different. Even if both are stored in the same 32 bit unit. A "pointer to char" will not be an address as it is used by the computer, but a combination of an address, plus some indication which of the four bytes of a 32 bit unit to access. Cray built machines that worked that way.

In the end, the compiler for your programming language is responsible to make everything work the way it is supposed to work according to the definition of the programming language, no matter how the underlying hardware works.

PS. The compiler also has the option to make char = 32 bit.
> 2 votes

---
Tags: memory-hardware, memory-allocation
---


# Question
Title: What determines a hit or a miss for direct mapped cache?
I've been stuck on this for a while now, I've tried reading the related topics on cs.stackexchange as well as the textbook and youtube videos.

---

Suppose we have a 8KB direct-mapped data cache with 64-byte blocks.

Offset $= log\_2(64) = 6$ bits

number of blocks $= 8k / 64 = 125$

$Index = 7$ bits

$Tag = 32 – 13 = 19$ bits

Then how do I tell whether or not I have a hit or a miss given an address?

Is it (Block address) modulo (Number of blocks in the cache)

Where block address = byte address / bytes per blocks?

For example if (block address) mod (number of blocks in cache) = 2, then does that mean row 2 of my picture is a hit?

# Answer
> 1 votes
There might be multiple addresses which have the same index bits given a direct mapped cache. Once you have found the index for a address which is to be accessed you then need to compare the TAG field of the cache with the the TAG part of your address. If they match then you have got a cache hit otherwise it is a miss and you have some stall cycles.

---
Tags: computer-architecture, cpu-cache
---


title: How are similar bits separated?

text:
# Question
Title: How are similar bits separated?
A 1 is an "on" signal, and a 0 is an "off" signal. How does a computer know 01110 is different from 010? Does the computer wait between signals?

# Answer
The system operates in a synchronized fashion using a shared clock. This removes the ambiguity.
> 3 votes

---
Tags: arithmetic, signal-processing
---


title: Infinite regular language

text:
# Question
Title: Infinite regular language
Let $M$ be a DFA.

I would like to prove that $L(M)$ is infinite if and only if there exists a string $w \in L$ such that $|Q| \leq |w| \leq 2 \cdot |Q| $.

My idea was to use the fact that the shortest string in $L(M)$ is of size at most $|Q|$, but I am not sure precisely how I should use this. Or is there a different approach?

Thanks!

# Answer
The proof makes use of the pigeonhole principle.

First suppose $L(M)$ is infinite. This means that for every $k \geq 0$ there exists a $w \in L(M)$ with $|w| \geq k$. Therefore there must in particular exist a $w$ with $|w| \geq |Q|$. Take the shortest such $w$ and let $w = a\_1 a\_2 \ldots a\_k$. When reading $w$, $M$ will visit $k+1$ states $q\_0, q\_1, \ldots, q\_k$ where $q\_0$ is the initial state and $q\_k$ is an accepting state. Since $k+1 \geq |Q|$, some state must occur at least twice in this sequence: Now consider the *first* such repeated pair, $q\_i$ and $q\_j$. We have that the substring $a\_i...a\_j$ has length at most $|Q|$. The string $a\_1 \ldots a\_i \ldots a\_j a\_i \ldots a\_j \ldots a\_k$ will be accepted, and its length is at most $2|Q|$.

Next suppose there is a string $w \in L(M)$ where $|Q| \leq |w| \leq 2 |Q|$. Again consider the states that $M$ will visit when reading $w$ and let $w = a\_1 a\_2 \ldots a\_k$. As in the proof of the converse implication above, we notice that when reading $w$, $M$ will visit $k+1$ states $q\_0, q\_1, \ldots, q\_k$ where $q\_0$ is the initial state and $q\_k$ is an accepting state. Since $k+1 \geq |Q|$, some state must occur at least twice in this sequence. Again, consider the *first* such repeated pair, $q\_i$ and $q\_j$. We have that for every $m \geq 0$ that the string $a\_1 \ldots (a\_i \ldots a\_j)^m a\_{j+1} \ldots a\_k$ will be accepted, and this proves that $L(M)$ is infinite.
> 5 votes

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


title: Can you help Sam?

text:
# Question
Title: Can you help Sam?
Sam is a teacher. He teaches exotic materials (he's not a very computer fluent person and knows no programming). In his course he has several topics he teaches, say $a$, and each topic has a variable number of subtopics. The total number of subtopics in his course is $b$. In his exam (which is in essay form), the dean has stipulated that he can only set a maximum of $n$ questions, out of which students can select any $k$ questions to answer. Each of Sam's $n$ questions will have $c$ sub-questions.

Sam wants to design his questions so that no matter which of the $\binom{n}{k}$ question set his students choose, they'll find at least one question on each of the $b$ subtopics. Sam also wants to reduce the number of questions he sets. Loving efficiency, he wants to set the minimum number of $c$ that meets his requirements.

Can you give Sam an algorithm to help him out? Remember Sam is not computer fluent.

P.S: This is **NOT** a homework question. I made it up myself after writing an exam today that was similar to the above scenario.

I have **not** *yet* started a course on Algorithms and Data Structures. My knowledge (meagre as it is) is self taught.

# Answer
Here is a more succinct formulation of your question:

> Given three parameters $n,k,b$, find the minimum $c$ such that there exist $n$ sets $S\_1,\ldots,S\_n \subseteq \\{1,\ldots,b\\}$ of size $c$ such that the union of any $k$ of them is $\\{1,\ldots,b\\}$.

We can obtain a lower bound on $c$ as follows. Each element $i \in \\{1,\ldots,b\\}$ must appear in at least $n-k+1$ sets, since otherwise, we can choose $k$ sets not containing it. It follows that $cn \geq b(n-k+1)$, and so $$ c \geq \lceil \frac{n-k+1}{n} b \rceil. $$ Conversely, if each element $i \in \\{1,\ldots,b\\}$ appears in at least $n-k+1$ sets, then the sets are a solution for the problem. When $c = \lceil \frac{n-k+1}{n} b \rceil$, we can construct such a system in many different ways. For example, we can go over the elements repeatedly ($1,\ldots,c,1,\ldots,c,\ldots$), putting the first $c$ elements in the first set, the following $c$ elements in the second set, and so on. In total the $n$ sets contain $nc \geq (n-k+1)b$ elements, and so each element has appeared at least $n-k+1$ times. Since $c \leq b$, each of these occurrences is in a different set, and so each element appears in at least $n-k+1$ sets.
> 1 votes

---
Tags: algorithms, optimization
---


title: byte addressing memory and 32 bit bus

text:
# Question
Title: byte addressing memory and 32 bit bus
Say I have total 4 bytes on 1 byte addressable memory, with a 32 bit bus.

If I move value at 0'th address to one of the registers will system grab all 32 bits (all 4 bytes) through bus from memory, reprocess it to extract 0'th address value behind the scenes?

Or will it get exactly one byte through bus?

# Answer
It really depends on the hardware, the memory type, ...

Usually, for memory accesses, reading extra data have no side effect so a CPU may read 32bits and use a multiplexer to extract the byte from the correct data lane.

There are still some signals that indicates the width of accesses and which byte is actually read, because some addresses may be mapped to I/O ports, and reading an I/O port can have side effects.

It can also be used to optimize access times : Imagine a 32bits CPU connected to a bridge component as an interface to a 8bits NOR FLASH (for example some boot BIOS). The bridge should check which bytes are needed to minimize the number of accesses to the FLASH chip.
> 1 votes

---
Tags: memory-management, memory-access
---


# Question
Title: Is mapping reduction from $\overline{A_{TM}}$ possible?
I know $\overline{A\_{TM}}$ is not Turing Recognizable (to prove it, infact, I proved its complement to be both Turing-recognizable and not decidable).

My question is, if $\overline{A\_{TM}}$ is not Turing Recognizable, can I reduce $\overline{A\_{TM}}$ to some language A (say $E\_{TM}$) to show it is not Turing Recognizable, too? Or this does not makes sense, because it's not Turing Recognizable and so cannot exists such a reduction function/TM?

# Answer
The notion of mapping reducibility is completely general:

Let $A, B \subseteq \Sigma^\*$ be languages. $A \leq\_{\mathrm{m}} B$ if there exists a computable function $f: \Sigma^\* \rightarrow \Sigma^\*$ such that

$$w \in A \iff f(w) \in B$$

No properties are required of $A$ or $B$.

We can use a mapping reduction from $\overline{A\_{\mathsf{TM}}}$ to show that $EQ\_{\mathsf{TM}}$ is not recognizable. Let $f$ be given by

$$f(\langle M,w \rangle) = \langle M', M'' \rangle$$

where $M'$ is the TM

"On input $x$ simulate $M$ on input $w$ and answer what $M$ answered"

and $M''$ is the TM that rejects every input.

Clearly, $M$ does not accept $w$ if and only if $L(M') = L(M'')$.
> 5 votes

---
Tags: turing-machines, reductions
---


# Question
Title: Admissibility of heuristic in the $A^*$ algorithm
The CS188 course from Berkeley goes to great length in explaining why the optimality of $A^\*$ algorithm is conditioned by the admissibility of heuristic.

Note: admissibility of heuristic means that:

$$\forall n, 0 \leq h(n) \leq h^\*(n) $$

With $h^\*(n)$ being the true optimal distance of $n$ to the goal.

The course's proof reasoning is sound and makes perfect sense.

However, this example uses a heuristic that is not admissible. For instance, the distance between the start state and the goal state is only $h^\* = 2$ while the heuristic of the start state is $h = 17$ (see the example with the 8-puzzle, using Nilsson heuristic). Obviously, $17 \gt 2$ and therefore the heuristic is not admissible.

However, after having implemented the algorithm and tested it, it seems that it is able to find the optimal solution each time. Trying to alter the heuristic function only makes it worse than optimal.

So, if the admissibility of the heuristic a necessary condition for the guaranteed optimality of $A^\*$, how comes that this example seems to refute this?

Did I miss something? Or perhaps, does the condition on the admissibility means that *sometimes, the algorithm will be optimal even with an unadmissible heuristic, but only an admissible one **guarantees** the optimality*?

I'd be curious to hear any thought about that.

# Answer
It's exactly as you suspected:

Sometimes, the algorithm will find an optimal solution even with an unadmissible heuristic... only an admissible heuristic guarantees the optimality of the solution returned.

If you use an unadmissible heuristic, there's no guarantee what will happen. The solution you get back might be the best one; or it might not be. And, you probably won't have any way of telling whether the solution you got back was optimal or not, so you won't even know for sure when this is a problem and when it isn't.

If you use an unadmissible heuristic, you'll often (but not always) get sub-optimal solutions.
> 3 votes

---
Tags: algorithms, search-algorithms, trees
---


# Question
Title: Boolean variable true iff equation is satisfied in ILP
Assuming $y$ is a boolean variable in an ILP program (that is $y \in Z$, s.t. $0 \<= y \<= 1$) and $x\_1$, $x\_2$ are bounded integer variables between $0$ and $M$. I want to encode the following high level constraint:

$$y = 1 \iff x\_1 \le x\_2$$

So far I've got this:

$$x\_1 \le x\_2 + (M+1)y$$

This enforces that whenever $x\_1 \> x\_2$ is true, $y$ must be $1$ or the equation won't hold. However, if $x\_1 \le x\_2$, nothing is restricting $y$ and thus could either be $0$ or $1$.

What other equation could I add in order to encode the constraint?

# Answer
You can do this by introducing the two inequalities

$$x\_1 \le x\_2 + M (1-y)$$

and

$$x\_1 \> x\_2 - M y.$$

The former encodes the requirement $y=1 \implies x\_1 \le x\_2$ (you can see that if $y=1$, then the $M(1-y)$ term disappears; if $y=0$, then $M(1-y)$ becomes something huge and the inequality is automatically satisfied). The latter encodes the requirement $y=0 \implies x\_1 \> x\_2$ (for similar reasons).

Hopefully this gives you an idea how to handle other kinds of implications as well, should they arise. Basically, multiply by something big, and add it/subtract it somewhere.
> 5 votes

# Answer
You could add a constant $0\<A\<M$ and then you add this constraint:

$$A-y(A+M)\leqslant x\_1-x\_2\leqslant M(1-y).$$

If $y=1$ then you are left with

$$-M\leqslant x\_1-x\_2\leqslant 0,$$ which says that $x\_1\leqslant x\_2$.

And if $y=0$ then you will be left with

$$A\leqslant x\_1-x\_2\leqslant M,$$ which says that $x\_1\>x\_2$ (since $0\<A\<M$).
> 4 votes

# Answer
Look into indicator constraints and SOS constraints. While you can define the target relations linearly as other answers have explained, special constraints can be handled more efficiently by the IP solver.

If you decide to implement the constraints directly as described by the other answer, try to use the smallest M possible, and consider lowering the integrality tolerance if your result is not correct. Also, avoid strict inequalities, they are ambiguous in the context of floating point arithmetic.

Using indicator constraints:

$x\_1\le x\_2 \leftarrow y=1$

$x\_2\ge x\_1 +1\leftarrow y=0$

The second constraint is equivalent to $x\_2\>x\_1$ for integers, if you want $x\_2\ge x\_1$ simply drop the 1.
> 3 votes

---
Tags: integer-programming
---


# Question
Title: clarification on multiple access in data link layer
In physical layer, we already have methods to share a common link by dividing into channels using FDM etc.

Then why do we need to think about multiple access at data link layer? I.e why csma, csma/cd are needed? We shouldn't be seeing any collision at all when I'm using a different channel for communication right? Do these protocols come into play only when i'm using a less bandwidth link due to which I can't share them by dividing into frequency bands at all?

# Answer
> 1 votes
If each communication is on a separate channel, you need to figure out what channels are free before you start communicating. How do you propose to do that? If you try to ask somebody, that requires communication, so how do you find out which channels are free for *that* communication? If you try to just listen to what comes past and figure out which channels are free at the moment, how do you know that a channel that's quiet at the moment is really free, and it's not just that its users have paused for a moment. What do you do if somebody else also starts transmitting on that channel at the same time as you?

Alternatively, you need to preallocate $\tfrac12n(n-1)$ channels to your $n$ hosts, so that each pair of hosts has a specific channel to talk on. But that doesn't scale.

---
Tags: computer-networks
---


# Question
Title: Is there a way to check if a path in a graph is infinite?
**Edit:** Maybe this is not the best title, so few free to change it.

So I'm trying to prove the following statement:

> A finitely branching tree $T$ with infinitely many vertices must have an infinite path.

My proof is loosely like this:

1. $P = \emptyset$
2. Start at the root $v\_0$
3. Since there are infinitely many vertices, there must be some vertice with infinitely successors.

Order the successors of $v\_0$ (there is a finite number of them), with the vertices with infinite successors to the left.

$P = P \cup \\{v\_0\\}$

Select $v\_1$ as the new root and repeat **(3)**.

What bothers me the most is that I didn't manage to find a deterministic way to do **step (3)**, at first I though **BFS** would work, since it's complete it would eventually visit all vertices at height $n$ and I could use this to construct an arbitrarily long path $P\_n$, however **arbitrarily long** and **infinite** are two different things.

# Answer
> 4 votes
You will not find an algorithm to do what you want. As you indirectly suggest, an algorithm can only check a finite prefix of any path. You can't even use the process of elimination as there may be multiple infinite paths. (If there was only one, you could eventually rule out all the other finite paths.)

As you are probably aware, this is (a corollary of) König's lemma. What you are asking for is essentially a constructive proof of it which doesn't exist. The typical (classical) proof repeatedly uses double negation elimination in the form: if no child has an infinite (simple) path then the subtree has a finite number of vertices, this is a contradiction thus there must be *some* vertex that has an infinite number of descendants. There is not, in general, a computable function to pick out this vertex though. Knowing that it must "exist" doesn't mean we have any way of calculating it.

---
Tags: graphs
---


# Question
Title: Min-max the component-wise sum of two sets
When I was trying to prove a problem at hand to be NP-complete, I coined the following problem:

> Given two integer sets $A = \\{ a\_1, \cdots, a\_n \\}$ and $B = \\{ b\_1, \cdots, b\_n \\}$. We know that there are $n!$ bijections between $A$ and $B$. For a bijection $f\colon A \to B$, define $$\max f = \max\_{a \in A} \\{ a + f(a) \\}.$$ This problem is to find a bijection which minimizes $\max f$.

I think it is polynomial solvable (which is thus of no use in reduction). The algorithm is simple: Sort $A$ non-decreasingly and $B$ non-increasingly and map $A$ to $B$ component-wisely.

However, I could not find a proof.

*Problem:* How to prove (or disprove) this algorithm?

# Answer
> 4 votes
Let $f$ be an optimal solution in which $f(a\_1) \< f(a\_2)$ for some $a\_1 \< a\_2$. Let $g$ be obtained from $f$ by switching the values at $a\_1$ and $a\_2$: $$ g(a) = \begin{cases} f(a\_2) & a = a\_1, \\ f(a\_1) & a = a\_2, \\ f(a) & \text{otherwise}. \end{cases} $$ Then $$ \begin{align\*} a\_1 + g(a\_1) &= a\_1 + f(a\_2) \< a\_2 + f(a\_2), \\ a\_2 + g(a\_2) &= a\_2 + f(a\_1) \< a\_2 + f(a\_2), \\ a + g(a) &= a + f(a) & \text{otherwise}. \end{align\*} $$ It follows that $\max g \leq \max f$.

Consider now $f$ as a permutation on $\\{1,\ldots,n\\}$: the first element is the index of $f(a\_n)$, the second element is the index of $f(a\_{n-1})$, and so on. It is a classical result that $f$ can be sorted by transposing pairs of numbers in the wrong order, an operation which corresponds to the transformation above (one way is to put $n,n-1,\ldots,2$ in their right place, if needed, in this order). The correctness of your algorithm immediately follows.

Comment: This sort of analysis is very reminiscent of the analysis of greedy algorithms.

# Answer
> 2 votes
I come up with another proof and answer my question.

Denote the bijection produced by this algorithm by $f$. We prove that $f$ is optimal.

Suppose that $a + f(a)$ is maximal for $f$ and consider any bijection $g$ other than $f$. We need to prove that $\max g \ge \max\\,f$ (see the figure below).

* CASE 1: If $g(a) \ge f(a)$, then $\max g \ge \max\\,f$.
* CASE 2: $b = g(a) \< f(a)$. Consider $b' = f^{-1}(b)$. We have $b' \> a$.
    + CASE 2.1: $c = g(f(b')) \ge f(a)$, then $\max g \ge \max\\,f$.
    + CASE 2.2: $c = g(f(b')) \< f(a)$. Consider $c' = f^{-1}(c)$. We have $c' \> a$.

Continue the argument above. We eventually identify some $u \in A (u \> a)$ with $g(u) \ge f(a)$ since the number of elements larger than $a$ in $A$ equals the number of elements smaller than $f(a)$ in $B$. Thus we have $\max g \< \max\\,f$.

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


# Question
Title: Is it possible to copy data in a linear type system?
I'm having a little problem with the abstraction layers in linear types. If every variable is used exactly once, there is no way to copy data, since you have to read each datum twice in order to write it twice to two different locations.

However, you could argue that once a variable is loaded into a register, you may do whatever you want with it, so `a -> (a,a)` is a possible function. I'm simply not sure where the line is drawn, or why.

Linear types in programming allows a compiler to build efficient pipelines of data transformation. Single-use variables allows in-place mutations in pure functional languages, and/or a memory-efficient implementation without using a garbage collector. Copying a value might make this process a lot more difficult, if not impossible, but I'm not sure.

Is it possible to copy data in a linear type system? Why?
Are there any (big) programming languages that implement linear types with/without copying?

# Answer
I don't know why you bring up registers at all, but the answer to your first question is "sure". You (potentially) are able to copy data, you just aren't able to do it freely. For example, an operation $\mathtt{dup}\_A : A \multimap A\otimes A$ may be provided, but only for certain types $A$. Most commonly there are "exponentials", written $!A$ for which $\mathtt{dup}\_{!A}$ is definable or given. The opposite operation is often called $\mathtt{kill}\_A : A \multimap 1$ or $\mathtt{discard}\_A$. You may start to see how this leads to a kind of functional manual memory management.

For programming languages, the exponential modality is usually the opposite of what we want as it allows the defining an operation of type $!A \multimap A$ via a rule called "dereliction". If we think of $!A$ as a type that may have multiple references, then a *linear* type $A$ means that references to $A$ will not be duplicated, *not* that it hasn't already been duplicated. A different modality leading to uniqueness logic gives the more commonly desired sense of a variable of type $A$ has not been multiply referenced (and thus we are free to mutate it, for example).

The main "serious", general purpose languages I'm aware of using substructural types are: Rust, Clean, and Pony. Rust and Pony allow freely "copying" primitive types but put restrictions on reference types.
> 7 votes

---
Tags: type-theory
---


# Question
Title: Is it possible to prove Language L context-free?
Give a question: Language L= {a^n b^(n+m) a^m}, where both n and m are \>=0. Is L context-free or not.

If the answer is yes, can I use the following PDA to prove it?

Since {a^n b^(n+m) a^m}={a^n b^n b^m a^m}, in the PDA, we first push n a's onto the stack. Then, we pop n a's from the stack by reading n b's. Next, we push m b's onto the stack, and we pop m b's from the stack by reading m a's. Finally, the strings will be accepted in q5.

Conversely, if the language is not context-free, should i use pumping lemma to prove it?

Thank you!

# Answer
> 3 votes
```
S → AB
A → aAb | ε
B → bBa | ε

```

This will be the Grammar for that language which follows the context free grammar rules, so the language generated will be CFL.

# Answer
> 1 votes
> If the answer is yes, can I use the following PDA to prove it?

Yes you can. Context-free languages are the languages generated by context-free grammars but also those accepted by push-down automata. So, if you are not explicitly asked to do so, then there is no need to rewrite your PDA into a CFG.

Also note that there exist procedures to transform a PDA into a CFG (or vice versa). This will usually not give you an elegant grammar, but a guaranteed answer. From your notation of your PDA I guess you use Sipser's book. He describes a method that ties the moment where a symbols is pushed on the stack is tied to the same symbol being popped.

# Answer
> -3 votes
The language as you told is a union 2 languages (one for a^nb^n and other one is a^mb^m). As cfls are closed under union even your language is regular. I did not understand your pda notation to validate it.

---
Tags: context-free
---


# Question
Title: A decision algorithm to choose what partner to use
### Background

I have a setup where I need to make an API call to a partner to initiate a financial transaction. I have multiple partners, and I need to choose which one to use each time a transaction needs to happen. The characteristics differentiating two partners are:

* if the transaction is accepted or not (**acceptance**)
* the **cost** of the transaction (fee charged by the partner, assumed to be constant over time)
* the **speed** of the transaction (assumed to be constant over timefor each partner)

The characteristics of a transaction are especially:

* amount
* currency
* (several other factors such as the user's country, the payment method he chose, etc)

Additional info: the acceptance rate of a partner is ***subject to change arbitrarily over time***.

.

### Algorithm

As you probably guessed, I am currently thinking about solutions and algorithms that could be used to solve the following problem.

> **Inputs:**
>
> * a transaction (with all its characteristics)
> * the database of all transactions having ever happened, containing for each transaction
>     + the partner used
>     + the fee charged
>     + if the transaction was accepted or not
>
> **Output**: the *best* partner to use to execute the transaction.

Obviously, the first step is to define *best*. Do we value speed more than cost? Do we value the expected acceptance rate more than both the cost and speed? etc.

Another important aspect I mentioned earlier is that the acceptance of the same transaction by the same partner might change over time. This means that the algorithm should sometimes *try a partner that is believed not to be currently the best* just to be able to, for instance, check if a partner's acceptance rate has improved over time.

### My question

I'm obviously not asking someone to write a magic algorithm solving that. I have a background of CS, but I am unsure about what algorithms and types of algorithms are usually used to solve this kind of problem. I would be grateful to be given some extra terminology (e.g. if this is a typical problem with a particular name in the domain) and resources to be able to dig into the problem.

Please don't hesitate to ask if something is unclear.

Thank you!

\[Edit\] After searching a bit more on the web, it seems that this problem has a lot in common with the multi-armed bandit problem. However I believe that the algorithms presented to solve this problem (e.g. UCB1) could be suboptimal in this context, because they wouldn't take into account the characteristics of a transaction and act as if the partner didn't take them into account.

# Answer
> 2 votes
Techniques developed for the multi-armed bandit problem might be useful for discovering the partner with the best acceptance rate and dealing with the changing acceptance rate over time. Those techniques balance "exploration" (sending transactions to a partner as a way to learn more information about their acceptance rate) vs "exploitation (sending transactions to the partner with the highest acceptance rate, to make use of the information gained previously). You'll probably be especially interested in the non-stationary bandit problem.

---
Tags: algorithms, data-mining
---


title: “Standard” approach to syncing data?

text:
# Question
Title: “Standard” approach to syncing data?
I'm wondering if there are any universally accepted "best" algorithms for syncing data sets.

I imagine there would be different solutions depending on circumstances:

* Are all peers online all the time or not?
* Are we more limited by bandwidth or processing power?
* Are data items large or small?
* Does data get modified and deleted or are we just accumulating a growing collection of data?

My question is what are the equivalents to *Djikstra's and Kruskal's algorthim* of my problem?

You might say the two well known algorithms mentioned solve problems which are much more specific. That's probably true, so let me narrow down my question:

What is a good way to calculate a diff between two versions of a large growing set of very small chunks of data? Assume data is never deleted or modified, synchronisation happens between a limited number of peers, somewhat regularly but there is no real *server and client* situation, any peer could have some new data.

I feel I just don't know where to start looking, what papers to read.

# Answer
> 3 votes
I don't know that there is any "standard" or "best" approach, as the technique that is appropriate will depend on the setting. However, I recommend you start by looking at the algorithms used by rsync and the Remote Differential Compression scheme. More generally, look at techniques for delta compression.

---
Tags: algorithms, synchronization
---


# Question
Title: undecidability proof by using Turing Machines
I have been reading some material about undecidability of a language, and I am not quite sure of one part. For what I see:

I start with a decider H, that has an input `<M,w>` where M is a Turing Machine and w is a string, so I have the following:

```
H(<M,w>)=accept if M accepts w
         rejects if M rejects w

```

all fine until this point. Now it says that I construct a new Turing Machine D, and this TM has H as a subroutine. If I make a graph I imagine something like this:

```
-------------      D that is a TM
|   -----   |
|   | H  |  |
|   |____|  |
|___________|

```

So it says that D calls H to determine what M would do if the input is M, it means something like:

```
H(M,<M>)

```

Now it says that it should do the opposite this decider H, it means that:

```
H(M,<M>)=reject if M accepts <M>
         accepts if M rejects <M>        ---------(1)

```

and this procedure can be generalized for D like:

```
D(<M>)=accept if M does not accept <M> ----------(2)
       reject if M accept <M>

```

I have two questions here, for not opening another thread, but in part (1) why the decider H makes the opposite? What would happen if it does not? I have read in a book that the argument is that sometimes a program can receive a program as an input, such as in a compiler, why it decides to do the opposite?

The interpretation of part (2) does it mean that the Turing Machine D, with input M, this input refers to the same Turing Machine that was put as an input for the decider H?

At the ends there is a contradiction, but I cannot get it, why in step (1) it is decided to do the opposite?

# Answer
> 4 votes
We have the language (commonly called $A\_\text{TM}$): $$ A\_\text{TM}=\\{(\langle M\rangle, w)\mid M\text{ is a TM and $M$ accepts $w$}\\} $$ and we want to show that this language is undecidable. We proceed by contradiction, assuming that there is a TM, $H$ that is a decider for $A\_\text{TM}$. The action of $H$, when given a description $\langle M\rangle$ of a TM $M$ and a string $w$, is to accept if $M$, given $w$, accepts and to reject otherwise.

We use the purported decider $H$ to make another decider $D$ which takes as input a TM description $\langle M\rangle$ and sends that description to $H$, both as a machine description *and* as an input string (which answers your question (2): yes, we send $\langle M\rangle$ to $H$ as *both* inputs).

Now you've correctly interpreted the action of TM $D$:

> $D$, on input $\langle M\rangle$, accepts if and only if $M$, on input $\langle M\rangle$, rejects.

In other words, $D$ always correctly determines whether a TM doesn't accept its own description as an input.

Which brings us to your question (1): why design the decider $D$ in such a peculiar way? The answer is precisely so that we can reach a contradiction. Since $D$ uses $H$ as a subroutine, it's clear that $D$ is a valid TM as long as $H$ is also. But now consider what happens if we give $D$ *its own description* as input? The action of $D$ on its own description is now

> $D$, on input $\langle D\rangle$, accepts if and only if $D$, on input $\langle D\rangle$, rejects.

This contradictory behavior clearly is impossible, so our initial assumption, that there was a decider $H$, must be false. In other words, the language $A\_\text{TM}$ must be undecidable.

# Answer
> 0 votes
If the language is decidable (your assumption), than its complement should be decidable too. So you can get it and it should work anyway. Getting the opposite is good to exploit a paradox (check Russell's one to get the idea), so even if this language could be decided by some TM, there is a cell in the table where the TM does not know how to answer, due to Russell's paradox.

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


# Question
Title: Why does Randomized Quicksort have O(n log n) worst-case runtime cost
**Randomized Quick Sort** is an extension of Quick Sort in which the pivot element is chosen randomly. What can be the worst case time complexity of this algorithm. According to me, it should be $O(n^2)$, as the worst case happens when randomly chosen pivot is selected in *sorted* or *reverse sorted* order. But in some texts \[1\] \[2\] its worst case time complexity is written as $O(n\log{n})$

What's correct?

# Answer
> 24 votes
Both of your sources refer to the "worst-case expected running time" of $O(n \log n).$ I'm guessing this refers to the expected time requirement, which differs from the absolute worst case.

Quicksort usually has an absolute worst-case time requirement of $O(n^2)$. The worst case occurs when, at every step, the partition procedure splits an $n$-length array into arrays of size $1$ and $n-1$. This "unlucky" selection of pivot elements requires $O(n)$ recursive calls, leading to a $O(n^2)$ worst-case.

Choosing the pivot randomly or randomly shuffling the array prior to sorting has the effect of rendering the worst-case very unlikely, particularly for large arrays. See Wikipedia for a proof that the *expected* time requirement is $O(n\log n)$. According to another source, "the probability that quicksort will use a quadratic number of compares when sorting a large array on your computer is much less than the probability that your computer will be struck by lightning."

**Edit:**

Per Bangye's comment, you can eliminate the worst-case pivot selection sequence by always selecting the median element as the pivot. Since finding the median takes $O(n)$ time, this gives $\Theta(n \log n)$ worst-case performance. However, since randomized quicksort is very unlikely to stumble upon the worst case, the deterministic median-finding variant of quicksort is rarely used.

# Answer
> 6 votes
You were missing that these texts talk about "worst case **expected** run time", not "worst case runtime".

They are discussing a Quicksort implementation that involves a random element. Normally you have a deterministic algorithm, that is an algorithm which for a given input will always produce the exact same steps. To determine the "worst case runtime", you examine all possible inputs, and pick the one that produces the worst runtime.

But here we have a random factor. Given some input, the algorithm will not always do the same steps because some randomness is involved. Instead of having a runtime for each fixed input, we have an "expected runtime" - we check each possible value of the random decisions and their probability, and the "expected runtime" is the weighted average of the runtime for each combination of random decisions, but still for a fixed input.

So we calculate the "expected runtime" for each possible input, and to get the "worst case expected runtime", we find the one possible input where the expected runtime is worst. And apparently they showed that the worst case for the "expected runtime" is just O (n log n). I wouldn't be surprised if just picking the first pivot at random would change the worst case expected runtime to o (n^2) (little o instead of Big O), because only a few out of n pivots will lead to worst case behaviour.

# Answer
> 2 votes
Note that there are *two* things to take expectation/average over: the input permutation and the pivots (one per partitioning).

For some inputs and implementations of Quicksort *all* pivots are bad ($n$ times the same number sometimes works) so randomisation does not help. In such a case the expected time (averaging over pivot choices) can be quadratic in the worst case (a bad input). Still, the "overall" expected time (averaging over both inputs and pivot choices) is still $\Theta(n \log n)$ for reasonable implementations.

Other implementations have true worst-case runtime in $\Theta(n \log n)$, namely those that pick the exact median as pivot and deal with duplicates in a nice way.

Bottom line, check your source(s) for which implementation they use and which quantity they consider random resp. fixed in their analysis.

# Answer
> -1 votes
Yes you are corect, it will be $O(n^2)$.

The worst case for randomized quicksort is same elements as input. Ex: 2,2,2,2,2,2

Here the algorithm whatever it picks will be $T(n) = T(n-1) + n$ and hence $O(n^2)$.

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


# Question
Title: Proof that multi-armed bandit optimization has exponential regret if loss function is general
I was reading Robert Kelinberg's paper on Nearly Tight Bounds for the Continuum-Armed Bandit Problem There is a section where he says:

"For a d-dimensional strategy space, any multi-armed bandit algorithm must suffer regret depending exponentially on $d$ unless the cost functions are further constrained. (This is demonstrated by a simple counterexample in which the cost function is identically zero in all but one orthant of $R^d$, takes a negative value somewhere in that orthant, and does not vary over time.)"

Here $d$ is the dimension of the set of strategies (values that we can pick at each time step).

I can't really see why that is the case, that with that given cost function you get exponential regret. Can you please help me understand how the proof would go?

# Answer
I'm not exactly sure what he means, but here's a very similar example in a discrete version. Imagine the strategy space weren't continuous but instead consisted of all points in $\\{\pm 1\\}^d$, one point in each of the $2^d$ orthants. The cost function $C$ is $0$ in all but one of those locations, where it is $-10$.

In order to get any decent regret, you have to figure out which point is the one with cost $-10$ and start choosing it repeatedly. But how will you figure it out? Your only way is to just try different points until you find the right one. But it will take on the order of $2^d$ tries to find it since that are the number of options.

This raises the question - how can a restriction like making $C$ convex rule out this kind of example?
> 3 votes

---
Tags: optimization, machine-learning
---


# Question
Title: What does "monotonicity" mean in the context of mutability
I'm reading *The Rust Programming Language* and found the following passage:

> Remember that writing to a struct is not an atomic operation, and many functions like `vec.push()` can reallocate internally and cause unsafe behavior, so even **monotonicity** may not be enough to justify `UnsafeCell`

It just popped out of nowhere in the book and I've had a hard time online trying to find what it exactly means in this context. Too much information is about the concept of "monotonicity" of mathematical functions, which I already knew but is apparently not very helpful.

I only seemed to find this article that talks about it.

> Now, in addition to respecting equality in the obvious way, I also include the stipulation that a functional program must respect the monotonicity of observations. What do I mean by this? It must be that once you have observed something at a point in time, then that will not cease to be evident in the future. This is analogous to the monotonicity property in Kripke or Beth semantics.

However this is also quite abstract and I'm not sure it talks about the same thing either.

# Answer
The author appears to be using the same (general) concept of "monotonicity" as in pure mathematics.

Using the example of a `vector`, if the size of some particular instance of `vector` is monotonic, then it would seem reasonable to assume that the memory location of any previously `push`ed element will not be subsequently modified, and thus that it is safe to directly change the value of that element without having to synchronize with the `vector`'s subsequent `push` operations.

This assumption seems reasonable for much the same reason why it seems reasonable to assume that the memory location of an element previously pushed onto a (non-circular, array-based, unbounded) stack whose size is strictly increasing will not be affected by a future `push` operation. This stands in contrast to a stack on which both `push` and `pop` operations are being invoked, and so the memory location of a previously pushed element may be "removed" by a `pop` operation, and thus available to be assigned to once again (i.e. modified) by a subsequent `push` operation.

The author's point is that this assumption is not correct, since even in a data structure whose size is strictly increasing, future insertions may affect previously inserted elements by triggering an internal reallocation of some sort that is distinct from the "logical" effect of the insertion.
> 6 votes

---
Tags: programming-languages, synchronization
---


title: MAX SAT Optimization problem

text:
# Question
Title: MAX SAT Optimization problem
search problem: find the assignment that maximize the number of satisfied clauses

For decision problem: determine whether there is an assignment that satisfies k of clauses.

optimization problem : determine the number of clauses that maximize the number of satisfied clauses ( is this correct?)

If I want to reduce search to optimization, how would I do it? Or how do I use the number of clauses (the answer from optimization problem) to determine the assignment (the search problem)?

# Answer
For MAX-SAT:

* The optimization problem is, given a CNF, to find the maximal number of clauses that can be satisfied at once.
* The search problem is, given a CNF, to find an assignment satisfying the maximal number of clauses.
* The decision problem is, given a CNF and a threshold $k$, whether there is an assignment that satisfies at least $k$ clauses.

To reduce from search to optimization, use the self-reducibility of SAT: pick a variable $x$, and try substituting $x=0$ and $x=1$, using your optimization oracle to determine which of these partial assignments leads to an assignment satisfying the maximum number of clauses.
> 0 votes

---
Tags: complexity-theory, optimization, reductions, decision-problem, search-problem
---


title: Comparing complexity of function

text:
# Question
Title: Comparing complexity of function
Let's say I have a function that runs in $O(n \lg n)$.

Let's say instead of running this function with a $n$-sized input, I run it **$k$ times** with an **$(n/k)$-sized** input, so I want to check if

$$ O(n \lg n) = k \left( O \left( \frac{n}{k} \lg \frac{n}{k} \right) \right)$$

I think it is, because of:

$$ O(n \lg n) = O \left( \frac{kn}{k} \lg \frac{n}{k} \right) = O \left( n \lg \frac{n}{k} \right). $$

Supposing $0 \< k \leq n$, as in worst case $k = 1$, we can say that $\dfrac{n} {k}$ is $n$.

Am I right?

In general, will the original $O(n \lg n)$ function be faster or slower? It seems to be slower because what was $\lg n$ now is $\lg \dfrac{n}{k}$ for some $k \> 0$.

PS: $\lg = \log\_2$

# Answer
If a function $f$ is convex and $f(0) = 0$ then $f$ is superadditive: $f(a+b) \geq f(a) + f(b)$ for $a,b \geq 0$. The function $f(n) = n\log n$ is convex (since $f''(n) = 1/n \> 0$) and $f(0) = 0$ (in the limit), and so for all $k\>0$, $$ f(n) \geq k f(n/k). $$ If $f$ were concave rather than convex, $f$ would be subadditive, and then $f(n) \leq kf(n/k)$ for all $k\>0$.
> 1 votes

---
Tags: complexity-theory, time-complexity
---


title: Cases of the Four Color Map Theorem

text:
# Question
Title: Cases of the Four Color Map Theorem
I've been searching for a specific case of the four color map theorem all over the internet, but can't seem to find a reliable explanation.

Does anyone know one or two "cases" of maps as applied to the four color map theorem, including how it could be proved by hand?

The only explanation given on the web is Appel & Haken's computer-based proof, which is not helpful in the sense that the code used in their programs is not available to the public, nor do I understand it completely.

Also, can someone please explain (in depth) what Kempe's chains are and how they work? (maybe also provide an example?)

I am writing a paper for my math class about the four color map theorem, and so far the internet has not been very promising.

# Answer
Kempe chains are explained in textbooks on graph theory. They appear in the five color theorem, an easy result which is proved using them.

The four color theorem is unfortunately rather complicated. You can try reading a summary of the Robertson et al. proof (including pointers to the computer code they use), Steinberger's simplified proof or Gonthier's account of his group's computer-checked proof.
> 4 votes

---
Tags: graphs
---


# Question
Title: What kind of language uses an infinite alphabet?
Kind of what it says on the tin. Let's say I have a countably infinite alphabet $A$ and a "language" $L = \\{s\_1s\_2 | s\_1,s\_2 \in A\\}$ (i.e. all possible strings of length 2). Now, my question is this: does it even make sense to think of this in terms of formal languages? Is there some construct akin to a state machine that I can use to model such a thing? And do any of the above answers change if $A$ is uncountable?

# Answer
> 1 votes
The definition of formal language doesn't depend on the alphabet - it remains exactly the same. Things start getting a bit more complicated when you are interested in certain *classes* of languages. For example, let us consider regular languages. If your alphabet is infinite, the restriction of having only finitely many states seems a bit restrictive. Instead, it makes sense to allow any number of states whose cardinal is strictly less than that of the alphabet (if you allow a cardinal at least as large, every language would be regular). The corresponding notion of regular languages isn't too exciting perhaps, but at least it is a genuine subclass of all languages, which shares some properties with regular languages over finite alphabets.

---
Tags: formal-languages
---


# Question
Title: Finding a path crossing minimum number of distinct colors
Given a set $\cal D$ of unit disks in the plane and a set $C$ of colors. Every disk in $\cal D$ is colored with one of the colors in $C$. Note that multiple disks may be colored with the same color. Every color $c\_i \in C$ is associated with a weight $w\_i$.

for every path $p$ in the plane, we define the weight of $p$ as the sum of the weights of the colors that at least one of the circles with that color is crossed by $p$.

In addition, two points $s$ and $t$ is given in the plane and the goal is to find a path between $s$ and $t$ with the minimum total weight. What is the best approximation factor we can guarantee?

# Answer
For a constant number of colors, the problem can be solved by considering all possible subsets of colors. The rest can be solved using a shortest path with memoization.

You can reduce set cover to this problem: Build a grid with $m+2$ rows and $n+2$ columns. Also assume all points in one column are connected, but connect the points in rows based on the following rule:

Each column represents a member of the universal set and each row a set. The boundary is a color with weight zero. Let $s$ be the leftmost uppermost point and $t$ be the rightmost and lowest point and remove the other two corners of the grid. Color the point $i,j$ with color $i$ if set $S\_i$ contains $u\_j$ and remove it otherwise. The minimum weight path in this graph is the same as the minimum set cover.

This subset of a grid, is a unit disk graph: allow the columns to be $cn$ apart from each other, where $c$ is the vertical distance between the first row and last row. So $\theta(\log n)$ is tight.
> 1 votes

---
Tags: computational-geometry, np-hard, approximation
---


# Question
Title: How are faces of a DCEL updated when triangulating a polygon?
In chapter 3 book how to triangulate a polygon is explained, however it doesn't seems to me that how to handle the faces are explained. My guess would to add two new face and erase the old one every time a diagonal is inserted (both while decomposing the polygon in monotone pieces, and during the actual triangulation). Is my guess correct?

Is there a smarter way to do that?

# Answer
> 3 votes
For the algorithm that triangulates a monotone polygon: every time you add a diagonal, you actually find a triangle. So, you can indeed explicitly relabel the face-value associated with all edges of that triangle. That does not affect the asymptotic running time.

For the algorithm that splits a simple polygon in to monotone polygons you cannot really afford that, as you may have to relabel an (half)edge multiple times. Hence, a solution there is just to be lazy: i.e. use the sweep just to update the vertex/edge fields in the DCEL, and ignore the face values. When you are done with the sweep: use the vertex/edge fields, in particular the next-fields on the half-edges, to walk around every face, and set the face values appropriately.

---
Tags: algorithms, data-structures, computational-geometry
---


# Question
Title: How to obtain the camera extrinsic matrix without using chessboard
I'm working on a problem to find the camera position in the world system when each picture was shot.

I currently have several pictures taken from different angles, and for each picture there is only a black square on a white paper.

I have the actual size of the black square on the paper and the intrinsic matrix of the camera. And since the square is very easy to crop from each image, I can also obtain the perspective transformation matrix for each image. But I think to eventually find the camera position, the key is to get the extrinsic matrix of the camera. What I've researched is that we need to use a chessboard, but I wonder if I can continue my work without using that.

# Answer
> 2 votes
I think the answer is yes, it is possible to get the extrinsic matrix of hte camera with just a single square, though the error might be higher as there is less redundancy. Let's look at how much information we obtain:

* How many unknowns? The extrinsic matrix has 5 real-valued parameters (the rotation matrix has 2 angles; the translation matrix has a 3D location). In other words, there are 5 degrees of freedom or 5 unknowns.
* How many equations? We obtain 8 equations/constraints. I am assuming we know the 3D location of each corner of the square (in world coordinates). We also know the 2D location of each corner (in image coordinates). The camera matrix maps each 3D point to the corresponding 2D point. So, each point gives us 2 equations (from the known 2D image coordinates), and there are 4 corners, so we get 8 equations.

In short, we have 8 equations in 5 unknowns. That's enough that it should be possible to recover the extrinsic matrix. Of course, there's not a lot of redundancy here, so the error might be higher than if you used a chessboard. A chessboard would provide a lot more equations (each corner inside the chessboard provides an additional point with a known 3D-\>2D mapping).

How would you recover it? Follow the guidelines in https://ksimek.github.io/2015/03/29/QA-recovering-pose-of-calibrated-camera/. In particular, you could solve for the 5 parameters of the extrinsic matrix using some optimization routine, such as gradient descent or L-BFGS.

Given some value for those 5 parameters, you can compute the camera matrix and map the 3D world coordinates of each corner to its corresponding 2D image coordinates; then you can compute the $L\_2$ error (sum of squared error) between the inferred 2D coordinates and the known 2D coordinates from the picture. This gives you an objective function that maps a value for the 5 parameters to an error term (which you want to minimize). Next, you can apply any off-the-shelf optimization library to try to minimize this objective function. This sounds pretty doable, with not too many lines of code to implement.

---
Tags: computer-vision
---


# Question
Title: Correctness of algorithm to find maximum in array
I want to show correctness of "Algorithm to find maximum element in array" using induction and contradiction.

```
ans=-infinity
for (i=0; i<n; i++)
    ans= max(ans, A[i])

```

where A\[0:n-1\] is array and max is the function to return maximum of its two arguments.

What I am doing:

Base case: `i=0, ans= max(-infinity,A[0])=A[0],` as only one element has been processsed, it is maximum.

Induction Hypothesis: `i=k<n-1`, assume the algorithm correctly find maximum upto k iterations.

Inductive Step: `i=k+1`, let `ans_{i}` denote maximum element obtained by algorithm upto i steps and let `ans'_{i}` denote another maximum element from array `A[0:i-1]`.

Then from induction hypothsis, `ans_{k} = ans'_{k}`

Now, for the sake of contradiction, assume `ans_{k+1} < ans'_{k+1}`

Now, how should I proceed to show this contradiction ?

Any suggestion? Should I change this approach ?

# Answer
> 1 votes
**Tip**: It's usually easy to proof by contradiction. Ignore the rest if you liked the suggestion.

Suppose you found some **ans** using your algorithm and **ans** is not the biggest.

If it's not the biggest, it means at some point, your **ans** was compared to a value **X** that's bigger than **ans** and **max(ans, X)** returned you ans.

Since **max** returns only the maximum value and **X** is bigger than **ans**, it's a contradiction.

---

By induction in the size **n** of the array, it's quite easy:

Base case: **n = 1**

* the algorithm will run and return the only element who is also the biggest \[OK\]

Hypohtesis: The algorithm works for any **n**

Inductive Step: It works for **n+1**

* Let's say you runned the first **n** elements of the array and you have your **ans**.
* Now you will just compare **ans** with the last element and you will return the biggest.
* As **ans** was the biggest from the first **n** elements (by hypothesis, we can find the biggest between **n** elements) and **ans** will be the maximum between **ans** and the last element, **ans** will be the maximum of the full array. \[OK\]

hope it helps.

---
Tags: algorithms, arrays, correctness-proof
---


# Question
Title: A minimal automaton for a language quotient $w^{-1}L$ if $L$ is regular
For a given language $L$ and $w \in X^{\ast}$ denote by $w^{-1} L := \\{ u \in X^{\ast} : wu \in L \\}$ the (left) quotients of $L$. The left quotients are closely related to the minimal automaton of $L$ in case $L$ is regular, i.e. in that case $(X, Q, \delta, q\_0, F)$ with $Q := \\{ w^{-1} L : w \in X^{\ast} \\}$, $\delta(w^{-1}L, x) := x^{-1}(w^{-1}L)$,$F := \\{ w^{-1}L \in Q : \varepsilon \in w^{-1}L \\}$ is isomorphic to the minimal complete automaton accepting $L$.

I am interested in the minimal automaton of a given quotient $w^{-1}L$ in case $L$ is regular, is there a way to construct it? Also as the quotients and the states in a minimal automaton correspond to each other, I am somehow interested in the set $\\{ u^{-1}(w^{-1}L) : u \in X^{\ast} \\}$ for given quotient $w^{-1}L$.

Note also that the quotients are closely connected to the Nerode (right) congruence, i.e. $u \sim\_L v \Leftrightarrow \forall x \in X^{\ast} : ux \in L \leftrightarrow vx \in L \Leftrightarrow u^{-1}L = v^{-1}L$, giving a bijection between them; and also yielding that the minimal automaton of $L$ is an accepting automaton for the nerode classes.

# Answer
Now that the question is clarified, I transform my comment into an answer and improve the construction. Our goal is to construct a minimal automaton for $w^{-1}L$ given a minimum automaton $A$ for $L$ and $w$.

It is known that $A$ is isomorphic to the automaton where the state correspond to quotients of $L$. This is the minimal automaton that you describe in your question.

Observe that the quotients of $w^{-1}L$ are also quotients of $L$ since $u^{-1}(w^{-1}L) = (wu)^{-1}L$. Thus, intuitively, you have in $A$ all the states that you need for constructing a minimal automaton for $w^{-1}L$.

First, we claim that the automaton $A$ where we change the initial state to be $w^{-1}L$ recognize $w^{-1}L$. Indeed, by reading $v$ from $w^{-1}L$, you end up in the state $v^{-1}w^{-1}L$. We have then $v \in w^{-1}L$ if and only if $\epsilon \in v^{-1}w^{-1}L$ iff $v^{-1}w^{-1}L$ is final.

Now we have two things to do: first, find the state in $A$ that corresponds to $w^{-1}L$: it is easy, it is the state reached by reading $w$ from $q\_0$. Second, we have to minimize this automaton. We claim that if we only keep states that are reachable from state $w^{-1}L$ then we will have a minimal automaton for $w^{-1}L$. Indeed, this automaton still recognize $w^{-1}L$ as we only removed dead state. Moreover each remaining state represents a non-empty quotient of $w^{-1}L$ and two states represent two different quotients. Thus, it has the required minimal size.

To summarize the algorithm:

* read $w$ in $A$ and reach state $q$
* remove states that can't be reached from $q$
* set $q\_0 := q$.
> 5 votes

---
Tags: formal-languages
---


# Question
Title: Is it decidable whether a Turing machine modifies the tape, on a particular input?
Is $L=\\{\langle M,w \rangle|M\text{ does not modify the tape on input w}\\}$ decidable?

We could tell if a TM does not modify the tape on **any** input by checking if there are no transitions in $M$ that write on the tape, but can it be decided for a given $w$?

# Answer
Yes, this is decidable. Here are two different proofs of that fact.

## A counting proof

Define a *configuration* to be the state of the tape, the location of $M$'s head, the state that $M$'s finite control is in, and whether or not $M$ has written to the tape yet. Note that for a *fixed* $w$, if $M$ does not modify the tape on input $w$, there are only finitely many possible configurations, let's say $N$ of them. $N$ can be easily computed; it is about $2 \times (\text{len}(w) + 2|M|) \times |M|$ where $|M|$ is the number of states in $M$'s finite control. (See footnote \*.)

So, run $M$ on input $w$ and keep track of all the configurations it enters. One of three things must happen:

* After at most $N$ steps, $M$ modifies the tape. In that case you know $\langle M,w \rangle \notin L$ and there's no need to keep simulating $M$.
* After at most $N$ steps, $M$ halts without ever modifying the tape. In that case you know $\langle M,w \rangle \in L$ and there's no need to keep simulating $M$.
* After at most $N$ steps, $M$ repeats some prior configuration without ever modifying the tape and thus enters a cycle. In that case you know $M$ will loop forever on input $w$, without modifying the tape, so $\langle M,w \rangle \in L$ and there's no need to keep simulating $M$.

Thus, after simulating $M$ for $N$ steps, we learn whether $M$ will ever modify the tape on input $w$.

Footnote \*: In this proof I will consider as equivalent all configurations where the head is more than $|M|$ cells to the right of the input and that differ only in the location of $M$'s head, and I consider as equivalent all configurations where the head is more than $|M|$ cells to the left of the input and that differ only in the location of $M$'s head. Why? If it ever reaches one of those configurations without modifying the tape, then it will loop forever without modifying the tape. This follows by a pigeonhole argument; the finite control can't count higher than $|M|$, i.e., if it reaches one of those configurations, then some state of the finite control must have repeated during the time when it's wholly to the right/left of the input, so it has entered a loop.

## A conceptual proof

For a given $w$, if $M$ doesn't write to the tape, it is equivalent to a two-way deterministic finite automaton (2DFA). So, you can write down a 2DFA with the following three properties:

1. The DFA has a single accepting state $q\_a$, with a self-loop (once it accepts, it stays accepting forever). All other states are non-accepting.
2. If $M$ never writes to the tape on input $w$, the behavior of the 2DFA on input $w$ is equivalent to the behavior of $M$, and the 2DFA never transitions to the special accept state $q\_a$ and never accepts.
3. If $M$ does write to the tape on input $w$ at some point, the behavior of the 2DFA is equivalent up until the point $M$ first writes to the tape; thereafter the 2DFA follows a transition to the special accept state $q\_a$ and thus accepts.

How do we build such a 2DFA? The 2DFA is just a copy of the finite control of $M$ (which is a finite automaton), except that it moves to $q\_a$ whenever $M$'s finite control would modify the tape:

* If $M$'s finite control has a transition $q\_i \to q\_j$ when symbol $i$ is under the head $i$ and this transition doesn't write anything, then the 2DFA has the same transition.
* If $M$'s finite control has a transition $q\_i \to q\_j$ when symbol $i$ is under the head $i$ and this transition does write to the tape, the 2DFA has a transition $q\_i \to q\_a$ on symbol $i$.

Now the question just becomes: given a 2DFA, does it accept on input $w$? This is decidable, as every 2DFA is equivalent to a (possibly exponentially larger) ordinary DFA.

## Comparison of proofs

Either proof suffices to show that $L$ is decidable. The counting proof has the advantage of not requiring fancy machinery like 2DFA. The conceptual proof shows both that $L$ is decidable and something stronger: if we restrict attention to a single fixed $M$, then the set of $w$ such that $\langle M,w \rangle \in L$ is in fact a *regular* language (since 2DFA are equivalent in power to DFAs). Pretty nifty!
> 9 votes

---
Tags: computability, turing-machines, reductions, undecidability
---


# Question
Title: Without fancy math, how does the MC-AIXI algorithm work?
How does the MC-AIXI algorithm work? I tried to read the paper, but I got lost in the math. I understand the concept of AIXI very well, but I don't get two things:

1) **Where does MC-AIXI get its models from??** Kolmogorov complexity is non-computable! Why can MC-AIXI get models?

2) How *exactly* does the decision tree work? I kinda get the concept, but how does it know what it will do in the future without doing another calculation, and so on ad infinitum?

I would like enough information do make my own version of it. Thank you so much for your help!

# Answer
> 8 votes
I'll assume that the paper you're referring to is Veness et al. (2011) - *A Monte-Carlo AIXI Approximation*. The paper (and the AIXI model more generally) is rather technical, and so it is difficult to talk about without using much math. I'll do my best to explain informally here.

The question is in two parts, so I'll address each separately.

## Models

The full mathematical formulation of AIXI makes use of **Solomonoff induction** to model the environment. Informally, Solomonoff induction involves enumerating every possible model (program) that is consistent with what has been observed, and weighting their likelihood by the inverse of their length. Solomonoff induction can be thought of as a theoretical upper limit on how well you can learn in the general setting while making no assumptions. As the question points out, it is of course incomputable.

We can relax the requirement that we model the world only using the Solomonoff prior, and introduce some other model class, which we will call $\xi$. Our agent is still a Bayesian expectation-maximizing reinforcement learner, but we can now plug it into a less powerful and less general (but computable) model. Hutter calls these agents AI$\xi$. In Veness et al.'s paper, they adapt the Context Tree Weighting (CTW) compression algorithm so that it can be used as a predictive mixture model of the form of $\xi$.

CTW is essentially a mixture over $n^{\text{th}}$-order Markov Models over bits, up to some finite order $N$. Each so-called *context tree* models dependencies in sequences of bits up to some finite depth. The CTW algorithm weights each context tree by its complexity (essentially how many nodes are in the tree). In this way, the CTW compressor can be made into an efficient, general, and fully Bayesian approximation of Solomonoff induction, and is great at learning short-term dependencies in bit sequences.

Veness et al. call their algorithm MC-AIXI-CTW, to emphasize that it is a two-fold approximation of AIXI: both in the planner (MC), and in the modelling (CTW). They could have used a different model, but they chose CTW because it makes no assumptions about the environment, and so is a general and principled choice. This allowed them to use the same model to learn to play various games, like rock-paper-scissors, cheesemaze, Pacman, and Tic-tac-toe.

## Planner

The other side of the MC-AIXI-CTW implementation is the Monte Carlo planner. The algorithm that the authors develop is a straightforward generalization of the commonly used expectimax algorithm, called Monte Carlo tree search (MCTS). MCTS has been used in various AI applications over the last decade or so, and there are lots of online resources about it; the Wikipedia page is a decent starting point. I'll give my own short overview:

If you've studied game theory or introductory AI, then you'll be familiar with **minimax**. This algorithm can be used to compute the optimal next move when playing a deterministic two-player game. In the case of AIXI interacting with some environment, we can model this as a two-player game, but we must lift the deterministic assumption, as the environment is unknown, and in general stochastic; our models (which we use to plan with) are probabilistic, and so minimax won't cut it here. We instead use **expectimax**, which is the stochastic generalization of minimax. Instead of the other player adversarially (and deterministically) choosing the *min* action every turn, we now have to *sample* from some probability distribution.

MCTS is a sampling algorithm for doing just this. The general idea is that we plan ahead by simulating potential outcomes, using our model. Our objective is to compute the *value* of each of the moves available to us, so as to pick the best one. The value is in general a random variable, since our model is probabilistic. Hence we should choose the action that maximizes our *expected* value. The MCTS algorithm repeatedly plays out (simulates) a game tree, but instead of adversarially picking the opponent's moves, they are sampled from AIXI's model. As we collect more samples, our estimate of the value of each move will become more accurate.

Of course, we don't have infinite compute power, and so we can't simulate the agent-environment interaction ad infinitum; we have to stop at some depth of the MCTS tree. In simple game-playing, like chess, we would use heuristics to generate some intermediate value at this finite depth, so that we have something to work with to propagate up the search tree. In this general setting that MC-AIXI is trying to plan in, we have no such heuristics, and so we have no choice but to stop the search once we reach some finite (and typically *small*) depth.

This is the biggest limitation of the algorithm: planning is a huge computational bottleneck for MC-AIXI. In the absence of heuristics, it's hard to perform well in environments that demand long-term planning, since MCTS treats $\xi$ as a black-box environment model. To answer your question: once the planner reaches its planning horizon, it has to stop simulating ahead and make do with whatever it's sampled from that play-out. This is of course very limiting, but is unfortunately necessary, since doing anything else would require some kind of domain knowledge, which defeats the purpose of having a maximally general reinforcement learner.

Sorry if this answer is a bit long and hand-wavy. I interpreted the direction 'without using fancy math' in the strongest sense that I felt I could get away with. Hope it helps! Also, because I'm a new user to CS.SE, I'm limited to two links per answer. Once I've accumulated some points, I'll go back and edit this answer to include more links to external resources.

---
Tags: algorithms, kolmogorov-complexity
---


title: Left quotient of a regular language

text:
# Question
Title: Left quotient of a regular language
I have this problem, and I don't really understand how am I supposed to do this. Could someone please help me with this? I know what left quotient is. I also know about regular, irregular languages. But still I don't know how to show this... Any help would be appreciated, thanks in advance! Also sorry if something is not correctly in English, not my first language.

Problem:

> Show that for any language $L ⊆ Σ^\*$ and any DFA $A = \langle \Sigma, Q, q\_0, \delta, F \rangle$, the left quotient $L \diagdown L (A)$ is a union of languages $L\_q = \\{v | \delta(q,v) \in F\\}$ for selected states $q \in Q$, and explain what are those selected states.

Could someone please also demonstrate on a small (but non-trivial) example, in which the $L$ would be irregular?

# Answer
By definition, $$ L \diagdown L(A) = \bigcup\_{x \in L} \\{ w : \delta(q\_0,xw) \in F \\}. $$ The idea now is to use the identity $$ \delta(q\_0,xw) = \delta(\delta(q\_0,x),w). $$ You take it from here.
> 1 votes

---
Tags: formal-languages, context-free, regular-languages, finite-automata
---


# Question
Title: Properties of language that can be enumerated in a finite amount of time with an enumerator?
Suppose an enumerator *E* can enumerate some language *L* in a finite amount of time (3 days, 3 hours, etc.). What properties does this language have?

My guess:

* *L* is finite, so *L* is a context-free language.
* Since *L* is a context-free language, L is also decidable
* Since *L* is decidable, *L* is also Turing-recognizable and co-Turing recognizable

My Questions:

* Is *L* also a regular language?
* A theorem says that:

> A language is Turing-recognizable iff some enumerator enumerates it

* Is there anything more or less we can say about *L*, compared to a Turing-recognizable language?

# Answer
> 1 votes
If the language can be enumerated in finite time, then the language itself is finite. Almost all natural classes of languages include all finite languages: they're regular, context-free, decidable, recursively enumerable, co-RE, ...

I'm not sure what else you'd want to say about finite languages compared to RE languages. It's enough to say that the language is finite; for any property you might be interested in, it's usually very straightforward to prove that finite languages do or do not have that property.

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


title: Turing machine decides languages in RE

text:
# Question
Title: Turing machine decides languages in RE
Given this language: $$L\_{s\_1,s\_2} = \\{ \langle M\_1 \rangle \langle M\_2 \rangle | L(M\_1) \in S\_1 \text{ and } L(M\_2) \in S\_2 \\}$$ I want to prove that for $S\_1=RE$ and $S\_2=RE$, then $L\_{S\_1,S\_2} \in R$.

The way I started was by trying to build a Turing Machine that decides $L\_{S\_1,S\_2}$:

**Let $M\_{12}$ be that Turing machine.**

1. For each input word $w$:
2. If $w$ cannot be decoded as $\langle M\_1 \rangle \langle M\_2 \rangle$ then halt and reject.
3. Run $w$ on both $M\_1$ and $M\_2$.
4. If one of the two machines above halted, then $M\_{12}$ halts and accepts $w$.

**And here I got stuck:**

What if the two machines didn't stop over $w$? how should I halt and reject $w$ in $M\_{12}$?

# Answer
> 2 votes
By definition, for every Turing machine $M$, $L(M) \in \mathsf{RE}$. Therefore your language can be rewritten as $$ \\{ \langle M\_1 \rangle \langle M\_2 \rangle : M\_1,M\_2 \text{ Turing machines} \\}. $$ This obviates some of the steps in your oddly named machine $M\_{12}$.

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


# Question
Title: Is bounded waiting satisfied in the 2 Process Solution?
Suppose, There are $2$ processes $P1$ and $P2$.

It is given that Mutual Exclusion and Progress are satisfied by these $2$ processes.

Suppose, Programming protocol is designed such that CPU only executes $P1$ and $P2$ is never alloted the CPU, So, here $P2$ starves.

---

```
My Question :- Is Bounded Waiting satisfied here ?

```

---

I think BW is satisfied, as there exists a bound on the number of processes that may enter after process desires to enter CS. And, here that bound is only 1 as only $P1$ is getting executed and if suppose CPU stops executing $P1$ and then after that only $P2$ will be executed.

Please provide the reason that exactly what happens here ?

# Answer
> 3 votes
***A little remark first:*** The bounded waiting (BW) property is defined with respect to algorithms, which is in turn defined as a set of concrete executions. Thus, we cannot conclude whether an algorithm satisfies BW if a specific execution does.

---

***For your question:*** For the specific execution in which only $P\_1$ takes steps, BW is satisfied. However, it is not because "there exists a bound on the number of processes that may enter after process desires to enter CS". Instead, BW is satisfied simply because $P\_2$ does not desire to enter the critical section. See the following definition from Mutual Exclusion (wiki).

> A $k$-bounded waiting property can provide a bounded waiting guarantee and it requires in every execution, a process can only enter the critical section at most $k$ times *while another process is waiting to enter the critical section*.

A more precise definition can be found in the Book: The Art of Multiprocessor Programming; Exercise 9 in Section 2.10:

> Define $k$-bounded waiting for a given mutual exclusion algorithm to mean that if $D\_A^j \to D\_B^l$ then $CS\_A^{j} \to CS\_B^{l+k}$.

Here, $D\_A^j$ means process $A$ finishes its *doorway* section for the $j$-th time, and $CS\_A^j$ denotes the interval during which $A$ executes the critical section for the $j$-th time.

In the execution above, $D\_{P\_2}^j \to D\_{P\_1}^l$ does not hold because $P\_2$ does not take any steps at all. Thus, BW is trivially satisfied.

Suppose that $P\_2$ has finished its doorway section (i.e., $D\_{P\_2}^1$ holds) and then halts. If $P\_1$ continues entering and exiting the critical section, then BW is broken.

---

***A little remark again:***

> I think BW is satisfied, as there exists a bound on the number of processes that may enter after process desires to enter CS.

It seems that you have a misunderstanding about $k$-bounded waiting property. $K$ here is about the number of entering (and exiting) the critical section, instead of the number of processes.

---
Tags: operating-systems, synchronization, deadlocks
---


# Question
Title: Curious about an old algorithm which calculates modular inverse
I am not sure if I should ask this question here or somewhere else. In fact, I initially asked my question here at mathoverflow.net but it was marked as off-topic

**Background**: I was searching through random mathematics paper that are related to cryptography and I came across this paper (page 3). I just read the abstract and algorithm itself, I don't understand Chinese. It offers new method to find a Modular inverses. It has some interesting properties that I observed:

1. during each step iteration of the loop: $x\_{11} * x\_{22} + x\_{12} * x\_{21} = m$ which is good to validate the result during each iteration
2. algorithm terminates in even number of steps for some unknown reason

In abstract section, author says this method was invented by this mathematicians.

My question is, why does this algorithm always terminate in aeven number of steps (or number of iterations of the loop is always even)?

**Algorithm** to calculate: $a^{-1} (\bmod m)$:

> $\text{xgcd}(a, m):$
>
> $\quad x\_{11} \leftarrow 1, x\_{21} \leftarrow 0, x\_{12} \leftarrow a, x\_{22} \leftarrow m$
>
> $\quad \text{While }(x\_{12} \> 1) \text{ do}$
>
> $\quad \quad \text{If }(x\_{22} \> x\_{12}) \text{ then}$
>
> $\quad\quad\quad\quad q \leftarrow \Big\lfloor\frac{x\_{22} - 1}{x\_{12}}\Big\rfloor$
>
> $\quad\quad\quad\quad r \leftarrow x\_{22} - q ~x\_{12}$
>
> $\quad\quad\quad\quad \begin{pmatrix}x\_{11} & x\_{12}\\x\_{21} & x\_{22}\end{pmatrix} \leftarrow \begin{pmatrix}x\_{11} & x\_{12}\\q~x\_{11} + x\_{21} & r\end{pmatrix} $
>
> $\quad\quad \text{If }(x\_{12} \> x\_{22}) \text{ then}$
>
> $\quad\quad\quad\quad q \leftarrow \Big\lfloor\frac{x\_{12} - 1}{x\_{22}}\Big\rfloor$
>
> $\quad\quad\quad\quad r \leftarrow x\_{12} - q~x\_{22}$
>
> $\quad\quad\quad\quad \begin{pmatrix}x\_{11} & x\_{12}\\x\_{21} & x\_{22}\end{pmatrix} \leftarrow \begin{pmatrix}q~x\_{21} + x\_{11} & r\\x\_{21} & x\_{22}\end{pmatrix}$
>
> $\quad \text{Return } x\_{11}$

# Answer
> 4 votes
You can replace:

$$ ~~q \leftarrow \Big\lfloor\frac{a - 1}{b}\Big\rfloor $$ $$ r \leftarrow a - q ~b $$

By $q, r \leftarrow \text{divmod}(a, ~ b)$

> Algorithm terminates in even number of steps for some unknown reason

Those matrices assignments seem to be a fancy way of writing:

$$ \gcd(m\_0, \color{blue}{a\_0}) = \gcd(a\_0, \color{red}{m\_0 \pmod{a\_0}}) = \gcd(\color{red}{m\_1}, \color{blue}{\underbrace{a\_0 \pmod{m\_1}}\_{a\_1}}) = \dots = \gcd(m\_n, 1)$$

So $a\_i$ decreases every $2$ iterations, and $\gcd$ stops when $a\_n = 1$.

Of course, you're not interested in computing the $\gcd$ per see, since you already know it's $1$, but finding the integers such that $Xm + Ya = gcd(m, a) = 1$.

# Answer
> 2 votes
Assuming you replace that second `if` with `else if`, the explanation of an even number of iterations is simple; you are repeatedly computing remainders, so each iteration swaps which of $x\_{12}$ and $x\_{22}$ is bigger. Each iteration alternately decreases $x\_{12}$ or $x\_{22}$ starting with $x\_{22}$. Since the loop ends after decreasing $x\_{12}$, you must go through an even number of iterations.

---
Tags: algorithm-analysis, correctness-proof, number-theory, modular-arithmetic
---


# Question
Title: Providing $1^n$ as input to protect against degenerate cases
The following language is NP-complete:

$$\\{ (\alpha, x, 1^n, 1^t): \exists u \in \\{0,1\\}^n s.t. M\_\alpha \text{ outputs 1 on input } (x,u) \text{ within t steps}\\}$$

I would like to have a stronger understanding of the $1^n$ and $1^t$ inputs that are provided as auxiliary inputs. Is the above language equivalent to the following one?

$$\\{ (\alpha, x, 1^t): \exists \text{ polynomial p and }u \in \\{0,1\\}^{p(t)} \text{ s.t. } M\_\alpha \text{ outputs 1 on input } (x,u) \text{ within t steps}\\}$$

I believe this gets around the technicality of allowing certificates that are sufficiently large, but not too large.

As for the $1^t$ input, what is the situation we are trying to protect ourselves against? Why isn't it sufficient to provide $(\alpha, x))$ as inputs and require that $M\_\alpha$ run in time $p(|x|)$?

# Answer
> 2 votes
Your second language is (probably) not in NP, since it allows witnesses of *arbitrary* size. For every size $m$ there is a polynomial $p$ such that $p(t) = m$, for example the constant polynomial $p \equiv m$. A polynomial time machine should have its running time bounded by a *fixed* polynomial in the input size.

Regarding $t$, if you replaced the unary encoding of $t$ by its binary encoding then you would get a problem in NEXP rather than in NP, since simulating $t$ steps of a machine scales proportional to $t$, whereas the size of the binary encoding of $t$ is only $\log t$.

---
Tags: turing-machines, np-complete
---


# Question
Title: Succinct data structure to return occurences of letters until an index
I want to try and use a succinct type data structure in order to find the amount of occurences of a letter $C$ in a string $S$ until a given index $I$.

Assume we have a string $S$ of length $n$ over the alphabet $\Sigma = \\{1,2,3,\ldots,n\\}$. I want to build a data structure whose space usage is at most $O(n)$ machine-size words.

Given $C$ (a valid letter from $\Sigma$) and an index $i$ such that $0 \le i \lt n$, the data structure should be able to return the number of occurrences of $C$ in $S\[1..i\]$ as efficiently as possible (but not necessarily in $O(1)$ time). This is the only query possible.

The data structure is aware of $S$ when created.

What I've tried to far is to split the string $S$ into blocks and to store info about each block with the number of occurrences of each letter in the previous block. I couldn't find how to make it lighter so the memory complexity be as requested.

# Answer
To put it another way, you want to implement rank queries on an arbitrary string with an arbitrary alphabet.

If $n$ is of modest size, the usual approach is to use a Wavelet tree, associating a succinct binary rank index with each node in the tree. The shape of the tree is arbitrary, but using a Huffman tree gives you a data structure that is very close to zero-order entropy compression.

When the alphabet is very large, though, the size and implementation of the tree itself becomes a concern. A way to fix this which seems to work well in practice is to store $\left\lceil \log\_2 n \right\rceil$ rank-select indexes of length $|S|$, but use an index implementation that it sensitive to local variation in density, such as esp or RRR.

This is covered in Claude & Navarro's 2008 paper, *Practical Rank/Select Queries over Arbitrary Sequences*. There may be some more recent work than this if you chase citations, but that's a good start.
> 5 votes

# Answer
Let's try a few special cases:

* If the letters in the string are all distinct, then a permuted index would give $O(1)$ lookup with $n$ words of storage.
    + Data: an array $A$ where $A\[c\]$ is the position of the letter $c$ in the string.
    + Data size: Array of size $n$.
    + Query: $Q(C,I) = 1$ if $A\[C\] \le I$ and $Q(C,I) = 0$ otherwise.
    + Query time: $O(1)$
* If the string only contains $O(1)$ distinct letters, then you could store the set of positions of each letter independently.
    + Data: for each letter $C$, a binary search tree of the positions of $C$ in $S$, where each node stores the weight of the subtree.
    + Data size: a forest of trees with a total of $n$ nodes.
    + Query: $Q(C,I)$ is the sum of the weights of the subtree to the left of $I$ in the positions tree for the letter $C$.
    + Query time: $O(\lg(n))$ (binary tree lookup)

That last data structure does in fact generalize to the case where the string can contain an arbitrary arrangement of letters. There are now $n$ trees, each of which could have a size up to $n$, but the total size of the forest is still only $n$, so the storage requirement is $\Theta(n)$. The query time is $O(\lg(n))$. The time it takes to set up the data structure is $O(n \lg^k(n))$ for some $k$ that I can't be bothered to calculate.
> 3 votes

---
Tags: data-structures, succinct-data-structures
---


# Question
Title: How to prove regular languages are closed under left quotient?
$L$ is a regular language over the alphabet $\Sigma = \\{a,b\\}$. The left quotient of $L$ regarding $w \in \Sigma^\*$ is the language $$w^{-1} L := \\{v \mid wv \in L\\}$$

How can I prove that $w^{-1}L$ is regular?

# Answer
Assume $M$ is a deterministic finite state machine accepting $L$. Feed the word $w$ into $M$, which will land you in some state $q$. Construct a new machine $M'$ which is the same as $M$ but has start state $q$. I claim that $M'$ accepts $w^{-1}L$.

*Now prove it.*
> 16 votes

# Answer
A very short argument yields the famous Theorem of MyHill and Nerode, which says that a language is regular precisely iff it has a finite number of quotients. So for $w \in X^{\ast}$ and $L \subseteq X^{\ast}$ we have $u^{-1}(w^{-1}L) = (wu)^{-1}L$, hence we have fewer quotients for $w^{-1}L$ as for $L$, in particular if $L$ just has finitely many quotients, for $w^{-1}L$ we also just have finitely many.
> 1 votes

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