# Question
Title: Can one consider living (biological) cell to be Turing Complete?
Universal Turing Machine can be boiled down to two components. Infinite tape of input and an action table, a finite state machine that moves read/write head along the tape and writes to it depending on input provided by the tape.

From this point of view cells have some properties very similar to UTMs, the DNA is in an essence a tape of instructions that can be read and written to. Rest of the cell behaves similar to action table, defining rules that guide which part of DNA is read and when it happens, a moving "head" along DNA "tape".

Subquestion 1: DNA can be used for computation. Can entire cell be used for similar purposes?

Subquestion 2: If every living organism contains at least one UTM is it possible that all organism are in some sense Turing Complete?

# Answer
> 11 votes
Every living organism has -- to our knowledge -- only a finite amount of resources available. So no, they can not be Turing-complete.

That said, there is quite a number of bio-inspired models of computation that can be studied formally. Sticker systems \[1\], for instance -- an abstraction of recombining DNA fragments -- can be shown to reach Turing-power when we assume infinite resources. Splicing systems \[2\] are another example.

I am not aware of any abstractions of entire cells. To my knowledge, we do not have a full understanding of how cells work so that is out of reach -- today.

Note: Turing-completeness requires programmability resp. universality. Can you elicit *any* response from a cell by applying suitable stimuli? I wouldn't think so. In my opinion, any given cell is more likely to correspond to a specific program with a specific purpose.

---

1. Sticker Systems by G. Păun and G. Rozenberg (1998).
2. Formal language theory and DNA: An analysis of the generative capacity of specific recombinant behaviors by T. Head (1987).

# Answer
> 2 votes
Turing machines do not have infinite but *unbounded* tapes. In his paper, Turing describes his machines as a model of human computers. (The word "computer" at the time mainly referred to the young people employed to process the UK census data :) He was very careful about his infinities, and he specifically said that the tape was *unbounded*. A human computer could always use more notebooks, and a Turing machine could always add more tape so that the head never falls off. But it always has a finite history. Your laptop can always buy more memory, but it never needs infinite memory. The essence of Turing's computer is that there is a universal evaluator of all programs, including the programs for the universal evaluator. The ribosomes transcribe genetic code which regulates among other things cell division, which leads to more cells with more ribosomes. But there are, of course, many different computers, and many different kinds of cells, and not-quite cells, which compute in many different ways.

# Answer
> 1 votes
There are many bio-inspired models of computation. As Raphael has already stated, real implementations would always have the limitation of finite resources. This aside, Membrane Computing uses abstractions of cells with their compartments as the computing hardware. However, they use the quantities of different objects/molecules in the different compartments as memory, not DNA.

The DNA-based models like the sticker systems mentioned by Raphael or also splicing systems do not care about the rest of the cell, but only take DNA as a memory and some enzyme's action on it as the computing operation.

---
Tags: computability, computation-models, turing-completeness, bio-inspired-computing
---


# Question
Title: Do all NP-hard problems have a reduction from one to another (Either A $\leq_m$ B or B $\leq_m$ A)
Given two problems, $A$ and $B$, that are NP-hard. Is either one of the following is true?

1. $A \leq\_m$ B
2. $B \leq\_m$ A

In other words, is there always a relationship between any two arbitrary NP-hard problems?

Also, I am speaking of polynomial time reductions, but I don't think specifying that will change the answer to this question.

# Answer
> 2 votes
No, the polytime m-degrees are not linearly ordered even above SAT.

We can get even stronger incomparability: there are sets which aren't even *arbitrary-time Turing-comparable*. This was proved by Kleene and Post (Friedberg and Muchnik proved an elaboration where the sets involved are also required to be c.e.).

# Answer
> 1 votes
Absolutely not. See you are talking about $NP-hard$ problems. $NP-hard$ problems are not necessarily in $NP$. Thats why they may not be reducible from one another. Cor example $SAT$ is $NP-hard$ as well as $HALT$. $SAT$ can be reduced to $HALT$ but the opposite is not true cause otherwise you will solve the halting problem.

**Edit:** I misunderstood the problem. For any two $NP-hard$ problems $A,B$ itamy not be possible to reduce one to another. For example take $A$ as $NEXP-complete$ problem and $B$ as $coNEXP-complete$ problem. Natural believe is $NEXP\neq coNEXP$. Hence there should not be any reduction from $A$ to $B$ or $B$ to $A$

---
Tags: np-complete, reductions, np-hard, np
---


# Question
Title: For random-access Turing machines, is a pointer an arbitrary-length integer?
(Sorry for my previous ill-posed question; I deleted it. This question is a refinement.)

For every computer we use, it has finite RAM. In perspective of complexity theory, it's one giant memory that is accessible in constant time. However, Turing machines have unbounded memory, and thus cannot be represented in finite RAM.

I can imagine the unbounded counterpart of RAM; not hardware-wise, but theoretically. A pointer is now not as long as `size_t`, but rather, is an arbitrary-length integer.

Given that an arbitrary-length integer with $n$ bits is given as the index, a random-access Turing machine would take a time proportional to $n$ to read the index, and immediately jump as much as the index. This gives a non-constant time complexity.

However, I see a vicious circle. As far as I know, implementations of arbitrary-length integers use a pointer, either pointing to the dynamically allocated contiguous array, or pointing to the front of a linked list of digits, or maybe being a null-terminated string. In other words, arbitrary-length integers require pointers, and in the model above, pointers are arbitrary-length integers.

How can I resolve this?

# Answer
Arbitrary-length integers don't require pointers. There are many ways to store an arbitrary-length string without using a pointer. Here is a simple way: encode the $n$-bit string $s\_1 \cdots s\_n$ as the bit-string

$$1 s\_1 1 s\_2 \cdots 1 s\_{n-1} 0 s\_n.$$

This can be stored in contiguous memory. Of course, you can store an arbitrary-size integers in this way too, by converting it to binary, treating it as an arbitrary-length string, and encoding it as above.
> 1 votes

---
Tags: turing-machines, computation-models
---


title: Is any 2-CNF has 2-DNF representation?

text:
# Question
Title: Is any 2-CNF has 2-DNF representation?
I was asked a question whether I could come up with a 2-CNF over several variables that has no 2-DNF representation. However I thought that any CNF can be converted to DNF through some manipulations e.g. De Morgan, distributivity, etc.

# Answer
> 3 votes
How about $\phi = (x\_1 \vee x\_2) \wedge (x\_1 \vee x\_3) \wedge (x\_1 \vee x\_4)$? This formula is satisfied iff $x\_1$ is true, or $x\_2$, $x\_3$, and $x\_4$ are all true.

Suppose that $\phi$ had a $2$-DNF representation $\phi'$ and assume (w.l.o.g.) that:

* All clauses of $\phi$ contain exactly two literals (you can rewrite $\ell$ as $(\ell \wedge \ell)$).
* $\phi'$ contains no clauses that are trivially false (i.e., no clauses of the form $(x\_i \wedge \overline{x\_i})$).

Then, no clause $(\ell\_1 \wedge \ell\_2)$ of $\phi'$ can contain two literals for variables other than $x\_1$, since otherwise setting $\ell\_1$ and $\ell\_2$ to true, and the rest of the variables to false, would satisfy $\phi'$ but not $\phi$.

Therefore, all clauses have one literal that is either $x\_1$ or $\overline{x\_1}$. However, no clause of the form $(\overline{x\_1} \wedge \ell)$ can exist, since otherwise $\ell \neq x\_1$ and setting $\ell$ to true and all the other variables to false would satisfy $\phi'$ but not $\phi$.

The only remaining case is the one in which all clauses are of the form $(x\_1 \wedge \ell)$. Then, setting $x\_1$ to false and $x\_2$, $x\_3$, $x\_4$ to true satisfies $\phi$ but not $\phi'$.

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


title: Question about Context Switching

text:
# Question
Title: Question about Context Switching
I'm reading OSTEP for my Operating Systems course, and I have a question from Chp.6.3:

> Note that there are two types of register saves/restores that happen during this protocol. The first is when the timer interrupt occurs; in this case, the user registers of the running process are implicitly saved by the hardware, using the kernel stack of that process. The second is when the OS decides to switch from A to B; in this case, the kernel registers are explicitly saved by the software (i.e., the OS), but this time into memory in the process structure of the process. The latter action moves the system from running as if it just trapped into the kernel from A to as if it just trapped into the kernel from B.

I don't really understand what's going on in this following text-segment and the associated diagram:

Specifically:

* What is going on with the registers during the context switch? It mentions that there are "kernel registers" and "user registers"? Why are both saved, and why are each of them saved where they are? In class, I learned that the user registers are saved into the associated PCB whenever a context-switch occurs, but this seems to suggest that the user registers are saved into the k-stack and the kernel registers onto the PCB? What is the difference between these and what exactly is going on here? Details are appreciated. I really enjoy this stuff.

To be clear: to me, it seems like there is redundancy here, as from the diagram alone, it seems that user registers are being saved into PCB and k-stack and being restored from both.

# Answer
> 5 votes
What I think is meant by "kernel registers" in this context is any values that are stored in registers within the kernel itself.

Note: In what follows, I'm going to talk about what happens in xv6, which is the educational operating system kernel used by this book. Most modern operating systems do something broadly similar, although there are some differences.

The context (pun not intended) of what's going on here is that a user task enters the kernel somehow (e.g. a system call or an interrupt), and the kernel decides that this task should be suspended and a different task should run. The actual transfer between tasks occurs in the `swtch` routine. (It is not actually called `switch` because that is a keyword in C!)

This routine, `swtch`, is written entirely in assembly language because of the special job it has to do. To the caller of `swtch`, everything should be as if it called `swtch`, that routine did nothing, and it returned. But what it actually does is transfer control to a *different* caller of `swtch`.

The "user registers" that need to be saved and restored represent part of the state of the *user* program. But the kernel is also a program, and so some registers need to be saved by `swtch` in order to restore the state that the kernel was in.

The reason why they need to be saved is because of the application binary interface (ABI for short). The ABI is a standard that different operating systems define which describe how you call a function in C. It specifies things like this:

* Which function arguments are passed in which registers or, if there are more arguments than registers, how they are laid out on the stack.
* Some registers are designated as "caller-save", in that they should be saved by the caller before calling a function.
* Some registers are designated as "callee-save", in that they should be saved by the called function and restored before that function returns if those registers are used by the callee.

The compiler expects callee-save registers to be preserved by the called function across a call. It might decide that the caller will use some of those registers to store local variables.

Now if you're wondering why there are some caller-save registers and some callee-save registers, it's for efficiency. In modern software, "leaf functions" can often be very small; think accessor functions in OOP, for example. They may only require one or two registers to do whatever work they need to do. The compiler knows this, and can often compile such functions using only caller-save registers, so the callee-save registers don't need to be saved.

As far as the compiler is concerned, calling `swtch` is like calling any other function, and so `swtch` needs save and restore those callee-save registers somehow. These are the "kernel registers" that the book refers to.

xv6 seems to follow the SysV ABI for Intel386. If you look at Figure 3-14 of that document, you will see three registers designated as "local register variable": ebx, esi, and edi. Along with the frame pointer ebp, these are the callee-save registers saved by `swtch`.

---
Tags: operating-systems, virtual-memory, process-scheduling, os-kernel
---


# Question
Title: How does the NFA decide in a state where there are multiple equally valid "next states"?
How does the NFA decide in a state where there are multiple equally valid "next states"?

Such as here:

How does it decide on which state it takes to with 1?

# Answer
> 12 votes
It doesn't decide. Nondeterminism isn't intended to be a realistic model of computation. Check the definition: a nondeterministic automaton accepts if there's any valid sequence of transitions that reach an accepting state.

# Answer
> 4 votes
**NFA**

The nondeterminism arises from the fact that there are multiple choices for possible next states due to multiple edges for the same input and epsilon ($\epsilon$) transitions. There is no sensor that indicates which state is actually chosen.

The interpretation often given in the theory of computation is that when there are multiple choices, the machine clones itself and one copy runs each choice. It is like having multiple universes in which each different possible action of nature is occurring simultaneously. If there are no outgoing edges for a certain combination of state and input, then the clone dies.

# Answer
> 1 votes
It can be seen as parallel computation wherein multiple processes can be running concurrently. An NFA splits into these different paths non-deterministically and will accept a word if at least one of these paths accept

---
Tags: automata, nondeterminism
---


# Question
Title: Product Construction for DFAs with different alphabets
How would you modify the Product Construction for DFAs to find a DFA that recognises the union of two regular languages with different alphabets. I am not looking for a way of finding an NFA then converting that to an equivalent DFA but explicitly modifying the Product Construction Theorem.

# Answer
We can adapt the product construction, but we can also change the original DFA $A\_1$ over alphabet $\Sigma\_1$ into a new DFA $A$ accepting the same language, but over a larger alphabet $\Sigma\supseteq \Sigma\_1$.

Just add a new dummy state $d$ and add transitions to $d$ from every state, for every extra letter $\sigma\in \Sigma\setminus \Sigma\_1$. From $d$ we have a loop back to $d$ for all letters.

Now we can perform the product construction to two (deterministic) automata with the same alphabets. Alternatively we start with the original automata, and for every letter that is not defined for both automata we move that component to dummy state $d$, and we stay in that state. The effect is the same.
> 2 votes

---
Tags: automata, finite-automata, computation-models
---


# Question
Title: Pumpiing Lemma for $0^n1^m0^n$ and $0^{3n}$
To understand the Pumping Lemma, I'm going to prove that the language $L = \\{0^n1^m0^n | n,m \geq0\\}$ is not regular. I choose string $w = 0^{p/2}1^{p/2}0^{p/2}$, for any even number $p$. Clearly $|w| \> p$. I use the following decomposition

* $x = 0^{p/2}$
* $y = 1^{p/2}$
* $z = 0^{p/2}$

Clearly for any $i$, $xy^iz \in L$, because the number of $1$s is not important and it doesn't lead to a contradiction. I think there is something I didn't understand about the Lemma. I appreciated it if you let me know why while $L$ is not a regular language, but my decomposition didn't lead to non-regularity.

As another example, consider language $L\_1 = \\{0 ^{3n} | n \geq 0\\}$. This language is clearly regular. I choose $w = 000000$, for $p=3,$ $x=0, y=00, z=000$. It is clear pumping $y$ in for $i=2$ $xy^iz = 00000000 \notin L\_1$ while the language is regular. Why I could find a decomposition that shows it is non-regular while the language is regular?

Thanks in advance.

# Answer
To show that a language $L$ is not regular you need to argue that the pumping lemma does not hold. That is, you want to show that **for every** $p$, there **exists** some word $w$ such that, **for every** decomposition of $w$ as $xyz$ with $|xy| \le p$ and $|y| \ge i$, **there exists** some $i \ge 0$ such that $xy^i z \not\in L$.

The quantifiers and their order are critical. What you can do is choose $w$ as a function of $p$. You don't get to choose a specific decomposition $xyz$, so you want to pick a $w$ that will make easy to argue about all possible decompositions.

In you first example $w = 0^{p/2} 1^{p/2} 0^{p/2}$ is not a great choice since there is a way to write $w$ as $xyz$ such tat $xy^i \in L$ for all $i \ge 0$. However, this doesn't tell you anything about the (non-)regularity of $L$ since there might be other choices of $w$.

Pick, for example, $w = 0^p 1^p 0^p$. Then, all decompositions are of the form $x= 0^{a}$, $y = 0^{b}$, $z=0^{p-a-b}1^p 0^p$, for some $a \ge 0$, $b \ge 1$ with $a+b \le p$. Therefore $xy^iz = 0^{p + (i-1)b} 1^p 0^p$. You can then pick $i=0$ (this is just an example, any $i\neq 1$ works in this case) to get $xy^0z = 0^{p-b}1^p0^p \not\in L$.

---

Conversely, if a language $L$ is regular, then there is **some** $p$, such that all $w \in L$ with $|w|\ge p$ admit **some** decomposition $w=xyz$ such that $xy^iz \in L$ for all $i$.

You don't get to choose the decomposition (as you have done) and, in general, you don't get to choose $p$. The pumping lemma only tells you that some $p$ exists.

Now, in your particular case it happens that the pumping length $p$ of $L$ is actually $3$ (this can be shown by arguing that a DFA with $3$ states can recognize $L$, you can't just blindly fix a value). Your example doesn't work because you picked the wrong decomposition of $w=000000$. Here is a decomposition that satisfies the pumping lemma: $x= \varepsilon$, $y=000$, $z=000$.
> 2 votes

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


# Question
Title: Time complexity of the following the code for(i = 1; i<=n;i++){for(int j=i+1;j<n-i;j++)}
```
for(int i = 1;i<=n;i++){
      for(int j = i+1;j<=n-i;j++){
        print("hello");
      }
    }

```

The first loop has time complexity of n and second for loop is dependent on i. That means for every i, the number of time inner for loop gets executed is: $\sum\_{k=1}^{n/2}(n-2k)$ After doing some algebra, I get: $\frac{n^2}{2}-\frac{n^2}{4}-\frac{n}{2}$. This is the time complexity for inner for loop. Now we multiplying outer loop $n\*(\frac{n^2}{2}-\frac{n^2}{4}-\frac{n}{2})$. Therefore, time complexity is $\Theta (n^3)$. But this can't be right? It should max be $\Theta n^2$. Cause inner loop doesnt get executed for every i value.$\forall i \\; \\; \\;i\>n/2$ inner loop doesnt get executed at all.

# Answer
Suppose $i=1$ then inner loop get executed $n-2$ times because of $2\leq j\leq n-1$ and $j $increment each step by one, As a result $n-1-2+1=n-2$ times inner loop executed.

If $i=2$ then inner loop executed $n-4$ times ... until $i=\frac{n}{2}$ inner loop executed 1 time.

| Value of $i$ | #inner loop executed |
| --- | --- |
| $i=1$ | $n-2$ |
| $i=2$ | $n-4$ |
| $i=3$ | $ n-6$ |
| ... | ... |
| $i=\frac{n}{2}$ | $n-(n-1)$ |

It's equal to following summation:

$\frac{n}{2}\times n-2\sum\_{i=1}^{\frac{n}{2}}i=\frac{n^2}{2}-\frac{n\times(\frac{n}{2}+1)}{2}=O(n^2)$
> 1 votes

# Answer
If you want to calculate time complexity using asymptotic notation, it's even easier (that's why it's so useful!).

In the first for loop

```
for(int i = 1 ; i <= n ; i++)

```

the number of iterations increases linearly with the size of the input ($n$).

The second,

```
for(int j = i + 1; j <= n - i; j++)

```

the number of iterations is also linear in $n$. In this case the iterations are not exactly $n$ (in fact they are $(n - i) - (i + 1) + 1$), but it is still linear in $n$ (even though the range is affected by $i$).

Clearly if you need the exact number of operations, you have to take into account the $i$ in the second `for`.

If you want to just calculate the complexity using asymptotic notation, you should just identify that you have 2 nested `for` loops that each is lineal in $n$:

$$\text{So the complexity is } \Theta(n^²)$$

furthermore, if is $\Theta(n^2)$, it is also $O(n^2)$
> 1 votes

# Answer
Consider the following code and equivalently transformed versions:

```
count= 0;
for(int i = 1; i<=n; i++) {
      for(int j = i+1; j<=n-i; j++) {
        count++;
      }
}

```

---

```
count= 0;
for(int i = 1; i<=n; i++) {
      count+= max(0, n - 2*i);
}

```

---

```
count= sum(1 ≤ 2i ≤ n:n - 2*i)

```

Using the triangular numbers, for even `n=2m` the final value of `count` is

```
mn - 2m(m+1)/2 = m²-m.

```

The result is similar for odd `n`.
> 0 votes

---
Tags: time-complexity
---


# Question
Title: How does a CPU jump to a instruction thats no longer in ram?
Im designing my own CPU but I don't know how it jumps to an instruction that's no longer in ram. People have told me it puts the address in the SSD but for example, if the address were 3 in ram it would most likely not be in address 3 in the SSD. someone help me I don't understand.

# Answer
> 3 votes
The program counter holds an address. Period. The CPU fetches an instruction from that address. Period.

Most CPUs today have a hardware unit called an MMU (memory management unit) which sits between the CPU and the RAM and messes with the addresses. The MMU takes the top many bits from the address and looks them up in a mapping table (in RAM) and replaces them with the value in the table. E.g. 0x12345678 -\> look at table entry 0x12345 -\> entry says 0xfffbc -\> actual address is 0xfffbc678. (0x1000 bytes is called a *page* and this table is called the *page table*)

The entry can also say the address is invalid. This causes an *exception* i.e. the same kind of thing that is triggered by invalid instruction, or divide by zero, etc. The CPU saves the address somewhere and it sets the program counter to the OS's exception handling code for invalid addresses.

---

The OS can use this to simulate extra RAM. It can promise 1GB of memory even though you only have 512MB. The other 512MB are invalid page table entries. When the program tries to access the 513'th MB, the CPU sees the invalid entry, and raises an invalid-address exception.

The OS code then picks some page it thinks the program isn't using, looks what is there, saves it on the SSD, and makes that page invalid in the page table.

Then it looks at the address that caused the invalid-address exception, looks in some data structure to see what was supposed to be there (e.g. a fresh page with zeroes, or a page that was saved to the SSD before), reads that data into the page it picked before, and puts an entry in the page table which says this page address turns into that page address. Then it goes back to the program which is none the wiser.

As long as the program can use all 1GB of addresses to access memory (because no matter which address the program uses, the OS quickly goes and makes it valid), the program doesn't know the OS and MMU are playing games behind the scenes. The program can think there's more memory than there actually is. This is popularly known as "virtual memory". It works well if the program is using less than 512MB at a time (and maybe the other 512MB are features you aren't using right now, for example). If the program really does use more than 512MB at a time, the program can run *really slowly* (so slowly that you might *wish* it would just crash so you would take the hint and go to the store and buy a RAM upgrade!).

As you can see it's an OS feature, not a CPU feature. The CPU needs to have an MMU, but the OS does the rest.

# Answer
> 1 votes
Virtual addresses can correspond to data in RAM or on disk and the system keeps address translation tables saying for instance:

* address 15037 is mapped to RAM page 7000, at offset 37 (hence address 7037)
* address 15037 is mapped to disk, track 345, sector 25, at offset 37.

(Addresses are mapped by whole pages, 1000 bytes in my example.)

When the CPU wants to access that virtual address, the system will either convert to the correct RAM address, or cause the loading of the relevant page from disk and map it to RAM before it can be accessed. This loading mechanism is transparent to the program being executed (it works by interruption).

---
Tags: computer-architecture, cpu, memory-access, memory-allocation, instruction-set
---


# Question
Title: How to find if a string in a list is an extension of another string with wild card *
**Problem:** Given a list of wild card strings(wild card is a * which is always at the end of a string), determine if the list has strings that are extension of another wild card string in the list.

Examples:

1. \[abc.*, abc.def.* \]

* the list has field abc.def.\* which is an extension of abc.\*

2. \[abc.xyz.*, def.*\]

* the list has unique wildcard fields.

How can I achieve this efficiently in Java ? I know I can do it with two loops. Tried o(n^2) solution. Looking for an efficient way to reduce the time complexity. Any thoughts ?

Thanks.

# Answer
> 0 votes
Use a trie, also known as a prefix tree. The running time will be (approximately) linear in the size of the input.

---
Tags: java
---


# Question
Title: Is there a name for an inverted state machine?
I recently needed something like a state machine, but with a slightly different use case.

In general, I would say a state machine knows about a set of states, and different events. Depending on the current state and the event, a state machine is able to decide if this is a valid event for this state, and to which state it should transition to.

What I need is slightly different: Again, I have a state machine knowing some states, transitions and events, but it does tell me which events have to happen to transition to a certain state. I already implemented such a machine and posted it for code review.

So, while the first machine is able to tell **in which state it is after an event**, the second machine is able to tell **what has to happen to transition to a state**.

According to this, my transition table looks different too. Instead of having new states in the intersection of current states and events, I'm storing the events in the intersection of current and new states.

Is there a name for this kind of inverted state machine, or is it just another implementation of a finite state machine?

# Answer
If I understand you correctly, you could achieve this using transducers (i.e. automata which also produce outputs when taking a transition).

Suppose we are given a DFA $A = (Q,q\_0,\Sigma,\delta)$ describing which events lead to which state transitions. Here $Q$ is the set of states, $q\_0$ is the initial state, $\Sigma$ the alphabet of events, and $\delta:Q\times\Sigma\to Q$ the transition function. Then we can define a (nondeterministic) transducer $A'$ as $(Q,q\_0,Q,\Sigma,\delta')$ as follows:

* $Q$ is the same set of states as before, and $q\_0$ is still initial;
* The input alphabet is now also $Q$ (representing the target state you are trying to reach);
* $\Sigma$ is now the output alphabet;
* The transition relation $\delta'$ contains a tuple $(q,\delta(q,a),a,\delta(q,a))$ for each $q\in Q$ and $a\in\Sigma$ (representing the fact that to get from $q$ to $r$, you can use $a$ if $r=\delta(q,a)$).

Note that I'm assuming that you actually want to proceed to the given target state, otherwise you need to adapt the transition relation. Also, if there is no transition from $q$ to $r$, the computation simply fails; you may want to handle this case differently.
> 2 votes

# Answer
To me, it really seems to be just a definitional variation, not a different kind of computational model.

One could define the transition function of a DFA using $\delta:Q\times Q \to \mathcal{P}(\Sigma)$, instead of the more conventional $\delta:Q\times\Sigma\to Q$. The reason we don't usually do it is because it is awkward when you want to define a language, but it is possible to imagine a different application for which this would be a more suitable definition.
> 1 votes

# Answer
What you have described is not a state machine. Look at the problem this way: a state machine makes only choise at each step.

In your case there may be several choises (exponential large number of choises potentially). Your machine is more complex, as I see this it is a stack machine (a stack is required to a backtracking implementation).
> 0 votes

# Answer
Looking at your code, I think you may be looking for model-based testing.

In model-based testing, you create a model: an explicit declarative specification of the behavior expected from your system. This is what your line

```
    StateMachine<Human> fsm = StateMachineBuilder.create(Human.class)
            .from(Human.UNBORN).to(Human.BORN).to(Human.DEAD, this::died)
            .from(Human.BORN).to(Human.KID).to(Human.DEAD, this::died)
            .from(Human.KID).to(Human.ADULT).to(Human.DEAD, this::died)
            .from(Human.ADULT).to(Human.DEAD).startAt(Human.UNBORN);

```

looks like to me. You then generate test cases from the model and run the actual system against the test cases to determine whether the system complies with the model. Or you develop test cases on the fly, while you test. There are many different ways for specifying models and many different ways to generate test cases from models; for some variants, software is available to generate test cases automatically. This is a whole field.

So I think model-based testing is where you can find terminology to describe what you are trying to do, and perhaps even ready-made software that supports testing in the way you want to do it. One tool I've seen, although I've never used it, is JTorX.
> 0 votes

# Answer
If I understand correctly, you are dealing with a machine with states, and deterministic transitions to other states caused by events. This is an FSM.

Such an automaton is described by a state/event matrix, whatever the way transition data is supplied.
> 0 votes

---
Tags: terminology, reference-request, automata, computation-models
---


# Question
Title: What do people mean they say "set of all programs" in computability theory?
I am going through notes on Computability theory and Galosis Theory by Russel Miller. In it, many times the phrase "set of all programs" is used. Could someone give a formal definition of what the set of all programs are?

# Answer
> 2 votes
Assuming these are the notes you are talking about, the author informally described a Turing machine with the following excerpt

> For our purposes, a Turing machine is an ordinary computer, operating according to a finite program, which accepts a natural number as input and runs its program in discrete steps on that input.

Usually (e.g. in Sipser's *Introduction to the Theory of Computation*), a Turing machine is formally defined as some variation on the following:

Generally in computability and complexity theory, we think of the alphabets $\Sigma$ and $\Gamma$ as simply being $\\{0,1\\}$, and Turing machines as being uniquely specified by their state sets $Q$ and transition functions $\delta$. This part of the tuple is what Miller refers to as the "program" of a Turing Machine in the informal definition excerpted from his notes above. As such, the terms "program" and "Turing machine" are often used interchangeably to mean the same object.

The set of all programs is then understood to mean the set of all possible state sets and transition functions.

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


# Question
Title: Does it require O(|E|) time to visit all nodes?
In an undirected graph it takes $O(|V| + |E|)$ time to visit all nodes in a simple graph using BFS according to our lecture notes. But why can't you visit them all in $(|V|)$ time instead?

# Answer
Particularly for BFS you need to pass over all edges. However, it is a lower bound for any algorithm for that — let's look at the simplified problem of testing whether the graph is connected. Let's look at the following two cases:

1. The graph is made of two random connected graphs.
2. The graph is made of two random connected graphs, with a single random edge connecting them.

To distinguish between those two cases, our algorithm MUST at some time process that edge which connects the two random graphs, which requires passing over all edges. Additionally, there is no possible way to eliminate any edge without examining it. We can see the algorithm must process all edges, so the complexity must be $\Omega(|E|)$.
> 2 votes

# Answer
You are correct in that for many representations of graphs, you could iterate through all the nodes in $O(|V|)$ time. But if someone wants to visit all the nodes according to a BFS order (for instance, producing the BFS tree on |V| nodes) it will require $O(|V|+|E|)$ time. That is, if one wants to process the nodes in some order where each newly-visited node is adjacent to a previously-visited node (if such nodes exist -- which they always do if the graph is connected) then this will require a BFS traversal of $O(|V|+|E|)$ time.
> 0 votes

---
Tags: graph-traversal
---


# Question
Title: Encoding SAT EqualsK Constraint with Two Possible Values
I am wondering about a way to CNF encode an EqualsK constraint with two possible values. In other words, I want to solve for the equation:

$$ (\sum\_{i=1}^n x\_i = A) \lor (\sum\_{i=1}^n x\_i = B) $$

There are CNF encodings already discussed for encoding EqualsK constraints with one value K, like here for instance, where the property $\text{Equals}(k, (x\_1, \dots, x\_n)) \equiv \text{AtLeast}(k, (x\_1, \dots, x\_n)) \land \text{AtMost}(k, (x\_1, \dots, x\_n))$ is used.

I have considered using just the normal EqualsK and adding an OR operation in the middle, but this results in it no longer being in CNF. Any help is very much appreciated, even a slow or naive encoding is fine. Thanks in advance.

# Answer
One option is to use a normal EqualsK, as

$$(t \lor \text{Equals}(A,x\_1 \cdots x\_n)) \land (\neg t \lor \text{Equals}(B,x\_1 \cdots x\_n))$$

where $t$ is a fresh variable. It is easy to convert this to CNF by distributing the $t \lor \cdots$ into the clauses of the EqualsK constraints.

(Why does this work? If $\varphi,\psi$ are two boolean formulas and $t$ is a fresh new variable, then $(t \lor \varphi) \land (\neg t \lor \psi)$ is equisatisfiable with $\varphi \lor \psi$: e.g., if $\varphi$ is satisfiable, you can set $t$ to False, or if $\psi$ is satisfiable, you can set $t$ to True.)

Another option is to count the number of true values, using a boolean adder circuit, and build another small circuit to compare the output of the adder to $A$ and to $B$, and then convert this circuit to CNF using the Tseitin transform. If $A \< B \le n$, this can be done using $O(n \lg B)$ clauses and new variables.

If you are working with a solver in practice, if it supports pseudo-boolean constraints, you can use those to express your condition.

Related: Encoding 1-out-of-n constraint for SAT solvers, Reduce the following problem to SAT.
> 0 votes

---
Tags: satisfiability, constraint-satisfaction
---


# Question
Title: Find the no of substrings a character is part of
I am looking for a O(1) solution for *finding the number of substrings a character is part of.*

For instance, let `s = "abcde"` and all substrings of s are
`a, b, c, d, e, ab, bc, cd, de, abc, bcd, cde, abcd, bcde, abcde`

Now 'a' is part of `a, ab, abc, abcd, abcde`
So I guess The first (and the last character) of the string is part of 5 or in general `len(s)` substrings

'b' is part of `b, ab, bc, abc, bcd, abcd, bcde, abcde`, 8 substrings
'c' is part of `c, bc, cd, abc, bcd, cde, abcd, bcde, abcde`, 9 substrings

So in general how do I find the no of substrings a character in part of ?
also assume all characters are distinct.

Edit:
What I have tried so far.

Total number of substring ?
`n * (n + 1) / 2`, where n = len(s)

Number of substring that start with the given letter ?
I guess its `len(s) - i`, where 'i' is the index (0 based indexing) of given letter ?

Also it looks like the closer a letter is to len(s) / 2, the higher its substing count

# Answer
In your length-5 string, your indices are $0,1,2,3,4$.

Take a character like $b$ of index 1. It will be in every substring defined by $(i,j)$ where $i$ can be $0,1$ and $j$ can be any of $1,2,3,4$. Can you see why the answer for $b$ is 8 without having the write them all out?

Take character $c$ at position index 2. It will be in every substring starting at index $i=0,1,2$ and ending at index $j=2,3,4$. Can you see why your answer for $c$ is 9 without having to write them all out?
> 2 votes

---
Tags: algorithms, strings, substrings
---


# Question
Title: Check if Two Arrays Sorted in Decreasing and Increasing Order Satisfy a Condition
Given 2 arrays $A, B$ each of size $n$. If we want to find if the two arrays satisfy the condition that $A\[i\] + B\[i\] \ge k$ for all indices $i$, it's sufficient to fulfill 3 conditions below:

1. Sum of all elements of $A$ and $B$ is $\ge nk$
2. Sum of max element of $A$ and min element of $B$ is $\ge k$ (edge case)
3. Sum of min element of $A$ and max element of $B$ is $\ge k$ (edge case)

**Edit**: Based on answers, these 3 conditions are not sufficient to prove that they work with all cases please given that they don't go over elements in between edge cases?

# Answer
No, these 3 conditions are not sufficient.

For example, $n=4$, $A=\[6,5,2,1\]$, $B=\[1,3,4,6\]$, $k=7$.

* The sum of all elements in $A$ and $B$ is $14+14=28=4\cdot7$.
* The sum of the max in $A$ and the min in $B$ is $7$.
* The sum of the min in $A$ and the max in $B$ is $7$.

However, $A\[2\]+B\[2\]=2+4=6\<7$.
> 1 votes

---
Tags: arrays, permutations
---


# Question
Title: Complexity of generating all subsets of size $k$ using recursion
What is the complexity of the following (Python) code, that builds the list L of all subsets of size $k$ of a given set?

```
# arr: input array
# k  : size of subsets
# tmp : current subset
# idx : current index in tmp
# i : current array element
# L : list of all subsets of size k
def subsets(arr, k, idx, tmp, i, L = []):

    if(idx == k):
        L.append(tmp.copy())
        return

    # When no more elements are there to put in tmp[]
    if(i >= len(arr)):
        return

    # current is included, put next at next location
    tmp[idx] = arr[i]
    subsets(arr, k, idx + 1, tmp, i + 1, L)

    # current is excluded, replace it with next
    # (i+1 is passed, but index is not changed)
    subsets(arr, k, idx, tmp, i + 1, L)

    return L

# Driver Code
if __name__ == "__main__":
    arr = [10, 20, 30, 40, 50]
    r = 3
    print(subsets(arr, r, 0, [0]*r, 0))

```

Intuitively, the algorithm generates all the $\binom{n}{k} = O(n^k)$ such subsets ; but how to compute the complexity of this algorithm "rigorously" and not "intuitively"?

# Answer
The runtime of a recursive function can be expressed as a recurrence relation in terms of the sizes of its input parameters. Your recurrence begins with $idx=0$ and has a base case (stopping condition) of when $idx=k$. The quantity $k-idx$ starts high and the recursion stops when $k-idx$ reaches $0$.

So let $T(n)$ represent the runtime of your function on a difference of $n=k-idx$. It makes two recursive calls, both with the same $k$ and both with $idx+1$. So the difference $k-idx$ reduces by $1$ every recursion. And every recursive iteration makes two recursive calls. So we have $T(n) = 2T(n-1)+c$ where $c$ is the amount of steps used in each call frame (that is, $c$ counts the number of comparisons made for your base cases and the set-up of two new call frames and the return statement).

Now just solve $T(n) = 2T(n-1)+c$ subject to your base case (when $n = k-idx = 0$ it does 1 or 2 steps, whichever you are counting). So the base case of the recursion is $T(0) = 1$ (or $2$).

Both of these base cases result in solving the recurrence to $T(n)=O(2^n)$.

Note that your algorithm here is essentially producing all subsets (which is an $\Theta(2^n)$ process) and you are only keeping the ones that have $k$ items. So this implementation is doing more work than necessary. As an example, if you are finding all the 3-sets of an initial set of $\[1,2,3,4,5,6,7,8,9,10\]$ in order to get to $\[8,9,10\]$ you consider all the cases of $1$ being chosen or not, $2$ being chosen or not, $3$ being chosen or not, $4$ being chosen or not, etc.
> 1 votes

# Answer
You know how many results are produced. If you can determine how many operations each result takes, then you just multiply.
> 0 votes

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


title: How to prove a language is regular?

text:
# Question
Title: How to prove a language is regular?
There are many methods to prove that a language is not regular, but what do I need to do to prove that some language *is* regular?

For instance, if I am given that $L$ is regular, how can I prove that the following $L'$ is regular, too?

$\qquad \displaystyle L' := \\{w \in L: uv = w \text{ for } u \in \Sigma^\* \setminus L \text{ and } v \in \Sigma^+ \\}$

Can I draw a nondeterministic finite automaton to prove this?

# Answer
Yes, if you can come up with any of the following:

for some language $L$, then $L$ is regular. There are more equivalent models, but the above are the most common.

There are also useful properties outside of the "computational" world. $L$ is also regular if

* it is finite,
* you can construct it by performing certain operations on regular languages, and those operations are closed for regular languages, such as

+ intersection,
    + complement,
    + homomorphism,
    + reversal,
    + left- or right-quotient,
    + regular transduction

and more, or
* using Myhill–Nerode theorem if the number of equivalence classes for $L$ is finite.

In the given example, we have some (regular) langage $L$ as basis and want to say something about a language $L'$ derived from it. Following the first approach -- construct a suitable model for $L'$ -- we can assume whichever equivalent model for $L$ we so desire; it will remain abstract, of course, since $L$ is unknown. In the second approach, we can use $L$ directly and apply closure properties to it in order to arrive at a description for $L'$.
> 59 votes

# Answer
**Elementary methods**

1. Finite automata (possibly nondeterministic, with empty transitions).
2. Regular expressions.
3. Right (or Left, but not both) linear equations, like $X = KX + L$ where $K$ and $L$ are regular.
4. Regular (Type 3) grammar.
5. Operations preserving regular languages (Boolean operations, product, star, shuffle, morphisms, inverses of morphisms, reversal, etc.)
6. Recognized by a finite monoid.

**Logical methods (often used in formal verification)**

1. Monadic second order logic (Büchi's theorem).
2. Linear temporal logic (Kamp's theorem).
3. Rabin's tree theorem (Monadic second order logic with two successors). Very powerful.

**Advanced methods**

1. Sophisticated pumping lemmas. See for instance
\[1\] J. Jaffe, A necessary and sufficient pumping lemma for regular languages, *Sigact News - SIGACT* **10** (1978) 48-49.
\[2\] A. Ehrenfeucht, R. Parikh, and G. Rozenberg, Pumping lemmas for regular sets, *SIAM J. Comput.* **10** (1981), 536-541.
\[3\] S. Varricchio, A pumping condition for regular sets, *SIAM J. Comput.* **26** (1997) 764-771.
2. Well quasi orders. See
\[4\] W. Bucher, A. Ehrenfeucht, D. Haussler, On total regulators generated by derivation relations, *Theor. Comput. Sci.* **40** (1985) 131–148.
\[5\] M. Kunz, Regular Solutions of Language Inequalities and Well Quasi-orders.
3. Support of $\mathbb{N}$-rational series.
4. Algebraic methods based on Transductions (see also Operations preserving regular languages).
> 12 votes

# Answer
Another method, not covered by the answers above, is *finite automaton transformation*. As a simple example, let us show that the regular languages are closed under the *shuffle* operation, defined as follows: $$ L\_1 \mathop{S} L\_2 = \\{ x\_1y\_1 \ldots x\_n y\_n \in \Sigma^\* : x\_1 \ldots x\_n \in L\_1, y\_1 \ldots y\_n \in L\_2 \\} $$ You can show closure under shuffle using closure properties, but you can also show it directly using DFAs. Suppose that $A\_i = \langle \Sigma, Q\_i, F\_i, \delta\_i, q\_{0i} \rangle$ is a DFA that accepts $L\_i$ (for $i=1,2$). We construct a new DFA $\langle \Sigma, Q, F, \delta, q\_0 \rangle$ as follows:

* The set of states is $Q\_1 \times Q\_2 \times \\{1,2\\}$, where the third component remembers whether the next symbol is an $x\_i$ (when 1) or a $y\_i$ (when 2).
* The initial state is $q\_0 = \langle q\_{01}, q\_{02}, 1 \rangle$.
* The accepting states are $F = F\_1 \times F\_2 \times \\{1\\}$.
* The transition function is defined by $\delta(\langle q\_1, q\_2, 1 \rangle, \sigma) = \langle \delta\_1(q\_1,\sigma), q\_2, 2 \rangle$ and $\delta(\langle q\_1, q\_2, 2 \rangle, \sigma) = \langle q\_1, \delta\_2(q\_2,\sigma), 1 \rangle$.

---

A more sophisticated version of this method involves *guessing*. As an example, let us show that regular languages are closed under *reversal*, that is, $$ L^R = \\{ w^R : w \in \Sigma^\* \\}. $$ (Here $(w\_1\ldots w\_n)^R = w\_n \ldots w\_1$.) This is one of the standard closure operations, and closure under reversal easily follows from manipulation of regular expressions (which may be regarded as the counterpart of finite automaton transformation to regular expressions) – just reverse the regular expression. But you can also prove closure using NFAs. Suppose that $L$ is accepted by a DFA $\langle \Sigma, Q, F, \delta, q\_0 \rangle$. We construct an NFA $\langle \Sigma, Q', F', \delta', q'\_0 \rangle$, where

* The set of states is $Q' = Q \cup \\{q'\_0\\}$.
* The initial state is $q'\_0$.
* The unique accepting state is $q\_0$.
* The transition function is defined as follows: $\delta'(q'\_0,\epsilon) = F$, and for any state $q \in Q$ and $\sigma \in \Sigma$, $\delta(q', \sigma) = \\{ q : \delta(q,\sigma) = q' \\}$.

(We can get rid of $q'\_0$ if we allow multiple initial states.) The guessing component here is the final state of the word after reversal.

---

Guessing often involves also verifying. One simple example is closure under *rotation*: $$ R(L) = \\{ yx \in \Sigma^\* : xy \in L \\}. $$ Suppose that $L$ is accepted by the DFA $\langle \Sigma, Q, F, \delta, q\_0 \rangle$. We construct an NFA $\langle \Sigma, Q', F', \delta', q'\_0 \rangle$, which operates as follows. The NFA first guesses $q=\delta(q\_0,x)$. It then verifies that $\delta(q,y) \in F$ and that $\delta(q\_0,x) = q$, moving from $y$ to $x$ non-deterministically. This can be formalized as follows:

* The states are $Q' = \\{q'\_0\\} \cup Q \times Q \times \\{1,2\\}$. Apart from the initial state $q'\_0$, the states are $\langle q,q\_{curr}, s \rangle$, where $q$ is the state that we guessed, $q\_{curr}$ is the current state, and $s$ specifies whether we are at the $y$ part of the input (when 1) or at the $x$ part of the input (when 2).
* The final states are $F' = \\{\langle q,q,2 \rangle : q \in Q\\}$: we accept when $\delta(q\_0,x)=q$.
* The transitions $\delta'(q'\_0,\epsilon) = \\{\langle q,q,1 \rangle : q \in Q\\}$ implement guessing $q$.
* The transitions $\delta'(\langle q,q\_{curr},s \rangle, \sigma) = \langle q,\delta(q\_{curr},\sigma),s \rangle$ (for every $q,q\_{curr} \in Q$ and $s \in \\{1,2\\}$) simulate the original DFA.
* The transitions $\delta'(\langle q,q\_f,1 \rangle, \epsilon) = \langle q,q\_0,2 \rangle$, for every $q \in Q$ and $q\_f \in F$, implement moving from the $y$ part to the $x$ part. This is only allowed if we've reached a final state on the $y$ part.

---

Another variant of the technique incorporates bounded counters. As an example, let us consider change *edit distance closure*: $$ E\_k(L) = \\{ x \in \Sigma^\* : \text{ there exists $y \in L$ whose edit distance from $x$ is at most $k$} \\}. $$ Given a DFA $\langle \Sigma, Q, F, \delta, q\_0 \rangle$ for $L$, e construct an NFA $\langle \Sigma, Q', F', \delta', q'\_0 \rangle$ for $E\_k(L)$ as follows:

* The set of states is $Q' = Q \times \\{0,\ldots,k\\}$, where the second item counts the number of changes done so far.
* The initial state is $q'\_0 = \langle q\_0,0 \rangle$.
* The accepting states are $F' = F \times \\{0,\ldots,k\\}$.
* For every $q,\sigma,i$ we have transitions $\langle \delta(q,\sigma), i \rangle \in \delta'(\langle q,i \rangle, \sigma)$.
* Insertions are handled by transitions $\langle q,i+1 \rangle \in \delta'(\langle q,i \rangle, \sigma)$ for all $q,\sigma,i$ such that $i \< k$.
* Deletions are handled by transitions $\langle \delta(q,\sigma), i+1 \rangle \in \delta'(\langle q,i \rangle, \epsilon)$ for all $q,\sigma,i$ such that $i \< k$.
* Substitutions are similarly handles by transitions $\langle \delta(q,\sigma), i+1 \rangle \in \delta'(\langle q,i \rangle, \tau)$ for all $q,\sigma,\tau,i$ such that $i \< k$.
> 8 votes

# Answer
Occasionally you will encounter a language specified as "all strings $s$ where every $k$-element substring of $s$ satisfies `<some property>`", where $k$ is some fixed constant. In that case, the language will be regular. The idea here is to define a finite automaton some of whose states "remember" the most recently-seen $k$ input symbols, as in the answer to this question.
> 5 votes

# Answer
The answer by Ran G. give a fairly extensive listing of the equivalent models that can be used to specify regular languages (and the list goes on, two-way automata, MSO logic, but that is covered by the link under 'more equivalent models'). And as Raphael stresses, we need an argument to convince the audience that the chosen representation is indeed correct.

Reconsidering the question, it adds 'For instance $\dots$'. That means we have to give a valid *construction* that, given any of the above models we assume specify language $L$, turns that model into one for $L'$. This generally will be the same type of model, but need not be: we can e.g. start with an deterministic FSA for $L$ and end with a nondeterminitic one for $L'$.

This includes the possibility to use closure operations: in the explicitly given operation in the example we have $L'= (\Sigma^\* \setminus L) \cdot \Sigma^\*$.

So, my point is that the answer is great, but we should add the "from $L$ to $L'$ construction", when not building a specific language from scratch.
> 4 votes

# Answer
*Regular expression transformation* is one way to prove closure under certain operations. The two simplest examples are closure under *reversal* and closure under *homomorphism*.

Given a regular expression $r$ representing a language $L$, we can construct a regular expression for $L^R$, the language of the reverse of all words in $L$, recursively:

* $\epsilon^R = \epsilon$, $\sigma^R = \sigma$, $\emptyset^R = \emptyset$.
* $(r\_1+r\_2)^R = (r\_1^R + r\_2^R)$, $(r^\*)^R = (r^R)^\*$, $(r\_1r\_2)^R = r\_2^R r\_1^R$.

All the action happens at the final rule $(r\_1r\_2)^R = r\_2^R r\_1^R$. As an example, you can check that $(0^\*1^\*)^R = 1^\*0^\*$. Structural induction establishes that the language of $r^R$ is indeed $L^R$.

Another simple example is closure under homomorphism. Given a homomorphism $h\colon \Sigma \to \Delta^\*$ and a regular expression $r$ for a language $L$, we can obtain a regular expression for $h(L)$ by replacing every instance of $\sigma$ in $r$ by $h(\sigma)$.
> 4 votes

# Answer
A language is regular iff you can write a scanner that decides on arbitrary strings whether or not they belong to the language using no more than a *fixed* amount of memory - i.e. recognition can be done in *O(1)* space.
> 3 votes

# Answer
Another way is to build up the language using operations under which you know they are closed. This is an extension to exhibiting a regular expression, as you have many more operations available (reverse the string, complement, intersection, chop out a piece, just keep a part, homomorphisms and inverse homomorphisms, ...)
> 0 votes

# Answer
Consider first the language Σ\*∖ which is regular since L is regular and regular languages are closed under complementation

Then consider the language Σ⁺ which is regular since we can find a regular expression for it i.e. if Σ = {0,1} then E = (0 + 1)⁺ denotes the language Σ⁺ and so by Kleene's Theorem, Σ⁺ is regular.

Then the language L'' = {uv | ∈Σ\*∖ and ∈Σ⁺} is just the concatenation of 2 regular languages so it is also regular since regular languages are closed under concatenation.

Finally the language ′:={∈ : = for ∈Σ\*∖ and ∈Σ⁺} is the intersection of the regular language L and the regular language L'' from above and since regular languages are closed under intersection, L' is regular as required.
> 0 votes

---
Tags: formal-languages, regular-languages, automata, proof-techniques, reference-question
---


# Question
Title: Can you simulate the following process in $O(N.log N)$
Given an array $A\[\]$ of N integers.

**pseudocode**:

* Traverse from left to right of this array.
* Let's say you are standing at index $j$.
* For each index i=1 to i=j-1, increment all $A\[i\]$ by $1$ if and only if $A\[i\] \ge A\[j\]$.
* Once done for all $i\<j$ move over to the next $j$ ie $j=j+1$

For example lets start with: $7, 5, 2, 1, 8$(1-indexed)

at $j=2 -\> 8, 5, 2, 1, 8 (A\[1\] \>= A\[2\])$

at $j=3 -\> 9, 6, 2, 1, 8 (A\[1\], A\[2\] \>= A\[3\])$

at $j=4 -\> 10, 7, 3, 1, 8 (A\[1\], A\[2\], A\[3\] \>= A\[4\])$

at $j=5 -\> 11, 7, 3, 1, 8 (A\[1\] \>= A\[5\])$

$11, 7, 3, 1, 8$ is the answer

**Python code** $O(N^2)$. (Note: python list is 0-indexed so printed $j+1$ to match the above 1-indexed example):

```
A = [7, 5, 2, 1, 8]
N = len(A)

for j in range(1, N):
    for i in range(j):
        if A[i] >= A[j]:
            A[i] += 1
    print("at j = ", j + 1, "->", A)

print("Final answer=", A)

```

# Answer
> 2 votes
Since the operation "add 1 to all values greater than or equal to i" preserves order, you can augment a self balancing BST with this operation. While the particulars are dependent on how the balancing is done, the idea is to keep in each node how much you need to add to its subtree, and push it to its children when you touch it.

Once you have such a tree, you can maintain all values up to the current index in it, and implement the algorithm in $O(\log n)$ per step.

In pseudocode:

1. Initialize $T$ to be an empty self balancing BST.
2. For $j = 1 \to n$:
    1. Apply to $T$ the operation "add 1 to all values greater than or equal to $A\[j\]$"
    2. Insert $A\[j\]$ to $T$, with metadata $j$.
3. For every node $v$ in the tree
    1. Set $A\[v.\text{metadata}\] = v.\text{value}$
4. Return A

---
Tags: algorithms, data-structures, balanced-search-trees, priority-queues, segment-trees
---


# Question
Title: Counting States in the trim automaton for $L\circ L'$
**Preliminaries**. Let $n,m \in \mathbb{N}$. Let our alphabet be $\Sigma = \\{0,1\\}$, with **non-empty** languages $ L \subseteq \Sigma^n$ and $ L' \subseteq \Sigma^m$. We follow the standard definition for **deterministic** finite-state automata except that we allow the state-transition function $\delta$ to be a partial function. In other words, an FSM has a finite number of states with transitions between them. We define the *depth* of a state $s$ as the length of the shortest path from the start state (at depth zero) to $s$.

A state $q$ is considered *accessible* if there is a path from the start state to $q$. A state $q$ is called *co-accessible* if there is a path from $q$ to a final state. Finally, an automaton is called *trim* if all its states are both accessible and co-accessible. This is defined here.

Consider the minimal trim finite-state automaton $A$ for the concatenation $L \circ L'$. We observe that this language is also finite.

**Question**: Can we conclude that the number of states in $A$ at level $n$ is 1?

**Argument**: All the strings in $L$ are in the same equivalence class for the Myhill-Nerode congruence for $L\circ L'$, since there is no distinguishing extension for any two strings in $L\in \Sigma^n$. All strings not in $L$ will land in the sink state, which is trimmed out of the minimal trim automaton.

# Answer
> 2 votes
For clarity, automata are assumed deterministic and possibly incomplete in the question and this answer. A trim automaton is incomplete unless it is empty or it accepts all strings.

As your argument indicates, there must be exactly one state in $A$ at depth $n$. Here is a proof for the more general case **when $L'$ is a nonempty finite regular language** instead of a nonempty language $\subseteq\Sigma^m$.

##### A description of the minimum trim automaton

Any two minimum trim automata for the same language are isomorphic. Hence we use the phrase "the minimum trim automaton".

Given a nonempty regular language $R$, we can construct the minimum trim automaton for $R$ as follows. For each equivalence class $e$ of the Nerode congruence for $R$, let $q\_e$ be a state that represents $e$. Let $o$ be the equivalence class that contains the empty string. The minimum trim automaton for $R$ is the $4$-tuple $$(\\{q\_e\mid\text{ there exists } w\in e\text{ and } r\in R\text{ such that }r\text{ starts with }w\\},\\ \delta,\\ q\_o,\\ (\\{q\_e\mid\text{ there exists } w\in e\text{ such that }w\in R\\}),$$ where $\delta(q\_e, a)=q\_{e'}$ for all $e, a, e'$ such that there exists $w\in e$ with $wa\in e'$. Note that $q\_o$ is not trimmed out because $R$ is not empty.

##### A proof of the existence and uniqueness of a state of depth $n$

We can construct the minimum trim automaton $A$ for $R=L\circ L'$ as described above.

Note that $L\circ L'$ consists of every string that is a string in $L\in\Sigma^n$ followed by a string in $L'$. So $L$ is an equivalence class of the Nerode congruence for $L\circ L'$. Since $A$ is a trim automaton for $L\circ L'$, all paths from the initial state of length $n$ end at $q\_L$. It is enough to prove that $q\_L$ is of depth $n$.

Since $L$ and $L'$ are nonempty, there is a path of length $n$ that starts from the initial state and ends at $q\_L$. The depth of $q\_L$ is at most $n$.

Towards a contradiction, suppose the depth of $q\_L$ is $\<n$, i.e. there is a path $h$ of length $\<n$ from the initial state to $q\_L$. Since all paths of length $n$ from the initial state end at $q\_L$ and all strings in $L\circ L'$ have length at least $n$ and $A$ is a trim automaton, we can extend $h$ until its length becomes $n$, at which time it must end at $q\_L$. Since the original $h$ also end at $q\_L$, we have found a cycle in $A$, which implies the language accepted by $A$ is infinite. However, $L\circ L'$ is finite. This contradiction completes our proof.

# Answer
> 1 votes
No. Let $L'=\emptyset$ and $n\>1$. Then $L \circ L' = \emptyset$, so its minimal automaton has no states at level $n$.

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


# Question
Title: How to interpret "Windows - Virtual Memory minimum too low" from a CS student point of view?
On my old 256MB RAM, pc I get this message. (I guess it is quite common)

> **Windows - Virtual Memory minimum too low**
> Your system is low on virtual memory. Windows is increasing the size of your virtual memory paging file. During this process, memory requests for some applications may be denied. ...

Please explain from a CS student point of view-

1. "Windows is increasing the size of your virtual memory paging file." and
2. "during this process...". what is this process called?

Thanks, I am currently studying virtual memory management in OS.

# Answer
> 8 votes
A computer typically has vastly more hard disk space that RAM. To compensate for limitations in the size of RAM, the operating system reserves part of the disk to use as additional RAM. This is called *virtual memory*. The RAM and the virtual memory are then divided into even chunks called pages. From the programmer's perspective, there is a large amount of memory available. Under the hood, the operating system keeps some of the pages of memory in RAM and leaves the remainder in virtual memory, on the disk. The operating system tries to ensure that the more commonly used pages are in RAM, as this is more efficient. If a program needs to access memory that it stored on disk, the operating system swaps out a page from RAM and swaps in a page from the disk. This is called *paging*. Paging is expensive, so the operating system tries to reduce how often it occurs.

If the amount of memory demanded by a program (or the collection of running programs) exceeds the amount of virtual memory, it is possible that the operating system increases the amount of virtual memory. As virtual memory is essentially a file, this explains what is going on when "Windows is increasing the size of your virtual memory paging file."

The "process" you refer to could be called "increasing virtual memory". I'm not sure whether it has a special name.

# Answer
> -1 votes
Paging and swapping are not the same thing. The paging, which is needed for virtual memory, allows programs to run without their entire virtual address space (code and data) to be in RAM.

Swapping moves an entire process to disk. while stored there, no computing occurs.

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


title: Simple pushdown automata question

text:
# Question
Title: Simple pushdown automata question
I'm trying to derive the language it represents. However, I'm kind of new to those topics. What happens if input b is gathered once or more than one time at state q without a in the stack? It does not have any transition, does it fail or since it is stuck is it accepted? example: abb

# Answer
For many DFAs and PDAs, there is a computation path that will lead to a permanent reject state (and once computation reaches that reject state, any further transitions only return to that one state). For DFAs and PDAs that have such a state, these states (and all the transitions that lead to that state) are not shown in a diagram or are even left out of the transition description of such machines, with the understanding that there exists an ***implicit reject state***.

For machines with an implicit reject state, any computational step that is encountered that is not explicitly described in the machine's definition is understood to just lead to the implicit reject state, never to be able to return back to acceptance. It can be thought of as a "crash" state or a "dead" state.
> 0 votes

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


title: Confusion with Execution of NDFA

text:
# Question
Title: Confusion with Execution of NDFA
I do not understand the "execution graph" (I think that's what it's called) of the following Non-Deterministic Finite Automata, given on pg 48-49 of Sipser's *Intro to TCS (3rd edition)*:

And here is the execution graph:

Why after seeing a $1$ does state $q\_1$ stem into three branches? And why after seeing a $1$ does $q\_2$ not branch off into $q\_3$ (isn't this the meaning of the empty symbol $\epsilon$, it acts as a "free pass" in case of no symbol)?

Here is Sipser's explanation, which I do not follow:

# Answer
The left column shows you what symbol (0 or 1) is being consumed from the input. $\epsilon$ is not a consumed symbol, so whenever $q\_2$ is visited, it could just as well be a $q\_2$ or $q\_3$ because of that $\epsilon$-transition.

So upon the first $0$ symbol, the machine remains in $q\_1$. Then after reading the first $1$ symbol, it could have stayed in $q\_1$, moved on the 1-branch to $q\_2$, or moved on the 1-branch and the $\epsilon$-transition to $q\_3$. This is why there are 3 branches there.

The reason you don't see $q\_2$ branch to $q\_2$ and $q\_3$ on the second last row of that tree (on the consumption of the third `1` symbol) is because if the $\epsilon$ was read/processed immediately before the `1`, then we wouldn't actually be in that $q\_2$ state on that level, but in the $q\_3$ state instead.
> 0 votes

# Answer
Oh okay, I think I see the point. Whenever an $\epsilon$ transition is encountered, it puts the resulting state on the same level as the state it came from, in order to have each row of the tree be in the same execution stage (as in they have read the same number of symbols).
> 0 votes

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


# Question
Title: Can a CPU instruction be split into 2 inputs?
Let's say there was a CPU with an input bus of 4 bits and the 4 bits are the opcode then the next 4 bits are the operand. It would just be an 8-bit instruction split in two. Is this possible and how would it be done with logic gates?

# Answer
You should look into "state machines".

Simple CPUs with variable length instructions have some kind of state machine.

Default state is fetching the opcode, then it fetches parameters or do memory accesses, eventually going through different states to execute each instruction.
> 0 votes

---
Tags: data-structures, cpu, database-theory, instruction-set
---


# Question
Title: Solving recurrence relation $T(n) = 5T(\frac{n}{3}) + 2n$
This is not a difficult problem, but I would like please to discuss with you how I solved it:

Solving recurrence relation $T(n) = 5T(\frac{n}{3}) + 2n$, $T(1)=2$. What is the value of $T(9)$? This can be done directly by applying $T(9)$ to get 98. However, I did it recursively as follows:

$$ \begin{align} T(n) = 5\left\[5T(\frac{n-1}{3^2}) + 2(n-1)\right\] + 2n \tag{1} \\ T(n) = 5\left\[5\left\[5T(\frac{n-2}{3^3}) + 2(n-2)\right\] + 2(n-1)\right\] + 2n\\ = 5^3 T(\frac{n-2}{3^3}) + 5^2\times2(n-2) + 5\times2(n-1) + 2n \tag{2} \\ \vdots\\ T(n) = 5^n \times T\left(\frac{n-(n-1)}{3^n}\right) + 5^{n-1}\times2(n-(n-1)) + \cdots 5\times2(n-1) + 2n \tag{3} \\ \end{align} $$

**Question**: what is the value of $T(n)$ above please as we have $n$, so we can not infinite apply geometric series I guess please?

# Answer
You can use either the master theorem or use unrolling to solve this.

If you want to apply unrolling, we note that at level 0 of our recursion tree, we do $2n$ much work, at level 1, we do $2n/3$ much work $5$ times. Let's write it as $2 \frac{n}{3^1}$ and we do it $5^1$ times.

At level 2 we do $2 \frac{n}{3^2}$ and we do it $5^2$ times. As you can see, at level $\ell$ we must do $2 \frac{n}{3^\ell}$ much work $5^\ell$ times.

The height of the recursion tree is bounded by $\log\_3 n$, so this is a geometric series $$\sum\_{\ell=0}^{\log\_3 n} 2n \frac{5^j}{3^j} = 2n \sum\_{\ell=0}^{\log\_3 n} \frac{5^j}{3^j} = \Theta\left(n \cdot \frac{5^{\log\_3 n}}{3^{\log\_3 n}}\right) = \Theta\left( 5^{\log\_3 n} \right) = \Theta\left( n^{\log\_3 5} \right).$$

Beware of mistakes.
> 1 votes

# Answer
Change variables: $n = 3^k$, $t(k) = T(3^k)$. In terms of those variables:

$\begin{align\*} t(k) &= 5 t(k - 1) + 2 \cdot 3^k \\ t(0) &= t\_0 \end{align\*}$

The above is just a linear recurrence of the first order, thus easy to solve:

$\begin{align\*} t(j + 1) &= 5 t(j) + 6 \cdot 3^{j + 1} \\ \frac{t(j + 1)}{5^{j + 1}} - \frac{t(j)}{5^j} &= 6 \left(\frac{3}{5} \right)^{j + 1} \\ \frac{t(k)}{5^k} - \frac{t(0)}{5^0} &= 6 \frac{3}{5} \sum\_{0 \le j \< k} \left(\frac{3}{5}\right)^j \\ &= \frac{18}{5} \frac{1 - (3/5)^k}{1 - 3/5} \\ t(k) &= \frac{18}{5 \cdot 2} \cdot 5^k \cdot \left(1 - \left(\frac{3}{5}\right)^k\right) \\ &= \frac{9}{5} (5^k - 3^k) \\ T(n) &= \frac{9}{5} (5^{\log\_3 n} - n) \\ &= \frac{9}{5} (n^{\log\_3 5} - n) \end{align\*}$
> 1 votes

# Answer
I think, as it says Shar you have a mistake, given that:

\begin{aligned} T(n)&=5T(\frac{n}{3})+2n\\ &=5\big ( 5T(\frac{\frac{n}{3}}{3})+2\frac{n}{3} \big )+2n\\ &\neq 5\left\[5T(\frac{n-1}{3^2}) + 2(n-1)\right\] + 2n \\ \end{aligned}

let's call $a=\frac{1}{3}$, then we rewrite the recurrence as $$T(n)=5T(an)+2n $$ Now let's solve (to do it exactly you must calculate the sum of the m terms):

\begin{aligned} T(n)&=5T(an)+2n \\ &=5\Big (5 \big (T(a^2n)+2an \Big )+2n\\ &=5\Big (5\big(5T(a^3n)+a^2n\big)+2an \Big )+2n\\ &\vdots\\ &=5^mT(a^m n)+ 2n\sum\_{i=0}^{m-1}(a^i) \text{ , where } |a|\<1\\ &=5^mT(a^m n)+2n\frac{1-a^m}{1-a}\\ \end{aligned} since the base case is $T(1)=2$, let's stop the recursive calls when $a^{m}n\leq 1\<a^{m-1}n$ and we get:

$$T(n)=5^m\cdot 2+2n\frac{1-a^m}{1-a}$$
> 1 votes

# Answer
$T(n) = 5T(n/3) + 2n$ ---- (1)

$5T(n/3) = 5^2T(n/3^2) + 2n(5/3)$ ---- (2) \[substitute $n/3$ for $n$ in previous equation and then multiply both sides by 5\]

$5^2T(n/3^2) = 5^3T(n/3^3) + 2n(5/3)^2$ ---- (3)

$5^3T(n/3^3) = 5^4T(n/3^4) + 2n(5/3)^3$ ---- (4)

$\vdots$

$5^{k-1}T(n/3^{k-1}) = 5^kT(n/3^k) + 2n(5/3)^{k-1}$ ---- (k)

Adding the above $k$ equations:

$T(n) = 5^kT(n/3^k) + 2n + 2n.(5/3)^1 + 2n.(5/3)^2 + 2n.(5/3)^3 + \dots + 2n.(5/3)^{k-1}$ as $n=3^{k}$

$T(n) = 5^kT(1) + 2n(1 + 5/3 + (5/3)^2 + (5/3)^3 + .....(5/3)^{k-1})$ where $k = log\_3 (n)$

$ = 5^{log\_3 (n)}.c + 2n\[(5/3)^{log\_3 (n)} - 1\]/(2/3)$

$ = c.n^{log\_3 (5)} +3n\[(5/3)^{log\_3 (n)} - 1\]$

$ = O(n^{log\_3 (5)}+n(5/3)^{log\_3 (n)})$

$ = O(n^{1.465}+n(n)^{log\_3 (5/3)})$

$ = O(n^{1.465}+n^{1+log\_3 (5/3)})$

$ = O(n^{1.465}+n^{1.465})$

$ = O(n^{1.465})$ or $O(n^{log\_3 (5)})$
> 1 votes

---
Tags: recurrence-relation
---


title: FFT algorithm for arbitrary $n$

text:
# Question
Title: FFT algorithm for arbitrary $n$
In section 30.2 of CLRS (third edition), they given an algorithm for computing the fast Fourier transform of a vector represented as an $n$ dimensional array when $n$ is a power of $2$. They say that an algorithm for general $n$ is beyond the scope. Is generalizing the algorithm to any $n$ very tricky? Any references where I can find generalized pseudo code that'll work for any $n$?

# Answer
> 3 votes
Notice that there is always a power of two $2^k$ between $n$ and $2n$. Thus you can extend your array of $n$ numbers to $2^k$ and fill the empty cells with zero. Because $2^k \leq 2n$ the algorithms asymptotic runtime $O(2n\log(2n)) = O(n\log(n))$ doesn't change. This is trick is commonly used in competitive programming.

# Answer
> 3 votes
As plshelp said, sometimes a 2^k point FFT is useful even when you want an n point Fourier transform with n \< 2^k. A 1024 point FFT is not the same as a 1023 point Fourier transform, but in many situations it is useful.

You can do Fourier transformations for any n, just following the definitions, in O(n^2). If you can write n as a product, say 1000 = 2 * 2 * 2 * 5 * 5 * 5, then you can calculate the Fourier transformation quicker; I think O (n * (sum of factors)) is possible, if n = 2^k then this is O (n log n). For the case n = 2^k this is called "Fast Fourier transform" but you can do a faster than normal Fourier transformation whenever the largest prime factor of n is much smaller than n.

If n = 3 * 2^k, you can calculate that transform quite fast. Very likely faster than FFT for n = 4 * 2^k, but a bit more complicated. Or for n = 1025, you could do a transformation for n = 5 * 256 = 1280 instead of FFT for n = 2048.

# Answer
> 0 votes
Use Bluestein's FFT Algorithm, some realizations already exist. Keep in mind that this also increases the calculation error at large sizes (\>10000).

---
Tags: algorithms, fast-fourier-transform
---


# Question
Title: Example 7.1 correctness in Introduction to Automata Theory, Languages, and Computation
The example says that C is unreachable, but there is the production S-\> aBC so C is clearly reachable. This is an error right? or am I missing something.

# Answer
Yes, that is an error, because C is reachable from S by using the production rule S-\>aBC and derives the string ababb using production rule C-\>abb and B-\>b. Hence C is reachable.
> 0 votes

# Answer
Just because C is a suffix of output of rule S -\> aBC doesn't make C reachable from S, since aBC -\> C is not necessarily reachable. Reachability from initial state is about reachability of strings of terminal symbols (denoted by strings containing only lower case letters). Nonterminals (the capital letters) are supposed to be expanded out at some point using the rules.
> -1 votes

---
Tags: automata, context-free, chomsky-hierarchy
---


# Question
Title: Simple, intuitive example of non recursively enumerable languages
This question is a bit of a shot in the dark. I am asking here, though I am not convinced that such an example exists.

I'd like a quick, highly intuitive example that I can throw out to my students *before* we engage in the halting problem. I will come back and explore RELs in more depth later in the lecture, but I was hoping for something I could use earlier in the lecture to help students *intuitively* see that there is a limit to what turing machines can represent before I get to a more formal exploration.

All of the examples I've found are very twisty, and would require me to stop and unpack the notion of the language before students could make any sense of them. (i.e. they are not simply intuitive.)

I have no doubt that, within the infinity of NRE languages, there are some highly intuitive ones, but I've never seen one described *anywhere*, and I've looked for a long time.

Has anyone ever thought of such an example?

# Answer
Perhaps - if you want to avoid the Halting stuff - you can use the set $L$ of incompressible strings:

You start from the definition: a string $x$ is compressible if there is a TM (or a generic "program" in some programming language) smaller in size than $|x|$ that outputs $x$ (when run on empty input)

If there is a TM (a "program") $M$ that enumerates $L$ then you can build another TM $M'$ that simulates/mimics $M$ and as soon as it outputs a string $y$ larger than $|M'|$ it outputs $y$ and halts. The tricky part is to make them realize that a program can "know" its own size and can simulate another program.

In other words $M'$ generates an incompressible string $y$, but $|M'| \< y$ so $y$ is compressible: a contradiction.
> 2 votes

---
Tags: computability, turing-recognizable
---


# Question
Title: Find offset and page number given paged virtual memory address
I ran into this question in class: Assume a machine that is 64-bit and has 8GB memory. They use a paged virtual memory where the page size is 4KB. You run the following program:

```
int main() {
   int *ptr = malloc(16);
   printf("%p\n", ptr);
   return 0;
}

```

and get output: 0x555555756260

We're to find the virtual page number of the address and the offset.

What I'm thinking is that I first convert that to binary, figure out how many bits and which bits represent the address/offset.

But I'm not sure how to figure out the latter. How can I determine which bits in the address correspond to which?

I'd really love some guidance

# Answer
* *assume* address printed out to be a "byte address"
* *guess* whether the offset to find is *addressable unit in page* or *byte in page*
    + if *addressable unit in page*, figure out its size
    with nothing more than *64-bit* to go on a first **assumption** is 8 bytes
* guess the representation wanted for *virtual page number* & *offset*

(Base conversions in the process depend on practice with the representations involved. For a result in hex, too, some would prefer to just double (word offset) or halve ("byte page#") "in hex". A *coder* might have a program print both parts before even considering if coding the task was least effort.)
> 0 votes

# Answer
Rather than converting to binary, it is more convenient to convert the page size to hexadecimal ($\text{0x10000}$). This hints you which are the significant hex-digits in the address.
> 0 votes

---
Tags: memory-management, memory-access, virtual-memory, c
---


title: Best balanced assignment

text:
# Question
Title: Best balanced assignment
I'm at a problem I don't know better to name it... maybe it's already a well known problem?

It seems quite simple: There are objects and labels in a n:m relation. (Each of the n objects may be assigned to any subset of the m labels).

Let s be the overall sum of the label-assignments of all objects.

You can take it as a 2-dim binary matrix.

The assigment patterns of the objects define partitions of the objects. (Each partition with equal assignment pattern).

OK, now the input is three numbers: n, m and s.

I am interested in that overall assigment which produces the "most even" partitioning of the objects. (Unassigned objects shall count as a partition of its own).

"Most even": The partition with the most objects shall be as small as possible. (I'm not sure if this is unambiguous and sufficient). The partitions shall be "most evenly distributed".

About alg: Depending on the values I identified several "sub-cases" (from trivial to complex). Very unsatisfying.

Does someone has an idea/ hint how

* to construct a most even partitioning or/ and
* to determine the result ("n1" objects with combination "m1", "n2" objects ...")?

As there was asked for an example:

```
Let n = 30, m = 5 and s = 50.
Question:
How to distribute the s assigments that the
groups of objects with identical assigment pattern
is most even distributed?

The WORST distribution would be:
X X X X X
X X X X X
(10 lines like that)
O O O O O
O O O O O
(20 lines like that)

==> 2 patterns:
(X X X X X) and (O O O O O)
distributed in the worst way:
20 objects with pattern (O O O O O)
10 objects with pattern (X X X X X)

Another distribution strategy:
O O O O O
O O O O X
O O O X O
O O X O O
O X O O O
X O O O O
Then start from the beginning.
Do that 4 more times (5 times at all)
==> All 30 objects are assigned,
but only 25 assigments set.
==> Add one assigment in every line except the first
Result:
==> 6 patterns, distributed evently
5 objects with pattern O O O O O
5 objects with pattern O O O X X
5 objects with pattern O O X X O
5 objects with pattern O X X O O
5 objects with pattern X X O O O
5 objects with pattern X O O O X
That is pretty well, but obviously it can be done
even better (use pattern with only one X set,
which increases the number of patterns and
by that lowers the number of objects in the groups).

For example "split" the all-unset pattern
3 objects with pattern O O O O O
2 objects with pattern O O O O X
At this point there are 2 assigments too much,
so split the pattern   O O O X X to:
2 objects with pattern O O O X O
3 objects with pattern O O O X X
Result:
3 objects with pattern O O O O O
2 objects with pattern O O O O X
2 objects with pattern O O O X O
3 objects with pattern O O O X X
5 objects with pattern O O X X O
5 objects with pattern O X X O O
5 objects with pattern X X O O O
5 objects with pattern X O O O X
which is wider/ more even distributed.

```

# Answer
If $n\le m$: Assign each object to all but one label (a different missing label for each object). Then $s=n(m-1)$ is the maximum attainable.

Otherwise, if $n\le {m \choose 2}$: Assign each object to all but two labels (a different pair of missing labels for each object). Then $s=n(m-2)$ is the maximum attainable.

Otherwise, if $n\le {m \choose 3}$: Assign each object to all but three labels (a different triple of missing labels for each object). Then $s=n(m-3)$ is the maximum attainable.

etc.

You should be able to take it from here and turn it into an algorithm.
> 1 votes

---
Tags: algorithms, optimization, sets, assignment-problem
---


# Question
Title: Reorder columns in a 2d matrix to maximize the count of all repeated subarrays across all rows
I have a matrix (input):

| -- | c1 | c2 | c3 |
| --- | --- | --- | --- |
| r1 | AA | BB | CC |
| r2 | CC | RR | BB |
| r3 | EE | DD | FF |
| r4 | KK | DD | EE |
| r5 | DD | GG | KK |
| r6 | PP | QQ | KK |

1. Let's call each matrix cell a `namespace`. If two rows begin from the same namespace, then such a namespace is called a `reused` namespace. A reused namespace does not need to be a prefix. In the example below, namespaces `AA`, `BB` are reused twice because a better arrangement does not exist (prefix namespace `HH` has been reused 4 times):

* `[EE, AA, BB, CC, ...]`
* `[HH, AA, BB, RR, ...]`
* `[HH, ...]` x(4)

2. The amount of reused namespaces is a score calculated for the whole matrix. If `N` rows share a common prefix of length `K`, then `(N - 1) * K` is the amount of reused namespaces.
3. Let's define a **score** for a matrix as an amount of reused namespaces for all matrix rows.
4. It is allowed to reorder elements in each row. Other operations are disallowed.
5. Let's define an **arrangement** as a configuration of the matrix where the elements in each row are reordered.
6. Constraints: the largest matrix I have is 1067 rows by 19 columns.

I need to find an arrangement that maximizes the matrix score. An easier explanation is I need to sort all row elements in a way that maximizes the score. The problem is that greedy solution (sort each row by counter across the matrix) will not work for all cases.

**Example 1**:

* `[AA, CC, DD, ...]`
* `[AA, CC, DD, ...]` (score: +3, the whole prefix is reused)
* `[BB, CC, KK, ...]` (`CC`, `KK` namespaces were reused, even though prefix namespaces differ (`BB` and `PP`)); (score +1 for `CC`)
* `[PP, CC, KK, ...]` (score: +2; `CC`, `KK` where reused)

**Example 2** (possible arrangement for the example matrix above; calculated by the code below):

| -- | c1 | c2 | c3 |
| --- | --- | --- | --- |
| r1 | BB | CC | AA |
| r2 | BB (score +1) | CC (score +1) | RR |
| r3 | EE | DD | FF |
| r4 | KK | DD | EE |
| r5 | KK (score +1) | DD (score +1) | GG |
| r6 | KK (score +1) | PP | QQ |

I implemented a naive version in Python.

First, I defined a ranker returning a score for a matrix arrangement. I used a prefix tree to get the count of reused prefixes (it is a simplification of what I need):

```
class Trie:
    def __init__(self, matrix: list[list[str]]):
        self.root = {}
        self.score = 0

        for row in matrix:
            self.add(row)

    def add(self, row: list[str]):
        root = self.root
        for word in row:
            if (child := root.get(word)) is not None:
                if word:  # handle padding empty strings
                    self.score += 1
            else:
                child = {}
                root[word] = child

            root = child

```

Second, I get all possible permutations across all columns and rows:

```
def generate_permutations(matrix: list[list[str]]):
    num_cols = len(matrix[0])
    col_indices = [*range(num_cols)]

    col_permutations = [*permutations(col_indices)]
    row_permutations = product(col_permutations, repeat=len(matrix))

    for row_permutation in row_permutations:
        permuted_matrix = []
        for i, row in enumerate(matrix):
            permuted_row = [row[col_idx] for col_idx in row_permutation[i]]
            permuted_matrix.append(permuted_row)
        yield permuted_matrix

```

Finally, I find the best arrangement based on the ranker score:

```
def namespace_sort(matrix: list[list[str]]):
    best_arrangement = copy.deepcopy(matrix)
    best_arrangement_score = Trie(best_arrangement).score

    for arrangement in generate_permutations(matrix):
        score = Trie(arrangement).score
        if score > best_arrangement_score:
            best_arrangement_score = score
            best_arrangement = arrangement

    return best_arrangement

```

This algorithm will never work for hundreds of rows and columns.

Is there a known optimal algorithm I can use to solve the problem? Otherwise how can I optimize the solution?

# Answer
> 0 votes
Taking `two rows` in `1.` to mean *two consecutive rows*, it would seem to suffice to establish counts of each namespace in either row and permute the subsequent row such that common ones appear in the same column.
I would not call this *Reorder columns in a 2d matrix*.
I have no idea how *repeated subarrays* fit into the picture.

```
def namespace_align(matrix: list[list[str]]):
    ''' Return a matrix with same values in subsequent rows
        column aligned where possible.
    '''
    reference = matrix[0][:]
    ref_counts = Counter(reference)
    arrangement = [reference]
    #
    for row in matrix[1:]:
        counts = Counter(row)
        fresh = (counts - ref_counts).elements()
        arranged = []
        for namespace in reference:
            if 0 < counts[namespace]:
                arranged.append(namespace)
                counts[namespace] -= 1
            else:
                arranged.append(next(fresh))
        arrangement.append(arranged)
        reference, ref_counts = arranged, counts
    #
    return arrangement

```

---
Tags: algorithms, combinatorics, matrices
---


title: Balanced Directed Graph Realization

text:
# Question
Title: Balanced Directed Graph Realization
I have a list of integers: each integer represents a node in a directed graph, and the value of the integer is both the desired indegree and outdegree of said node.

Some research suggests that this is called a "balanced graph", and that my list of integers represents a "realization problem."

I'm looking for a relatively efficient algorithm to generate such a graph. In cases where it is not possible, I'd like to reduce the highest integers in the list until a solution exists.

It would also be ideal if I can use different random seeds to generate different graphs for the same input until I can find one I like (so... I guess one that has some randomness to it?)

Does such an algorithm already exist?

# Answer
This is an instance of the directed graph realization problem. The problem can be solved in polynomial time; see Wikipedia for links to algorithms.
> 1 votes

---
Tags: algorithms, graphs, randomized-algorithms, directed-graphs
---


# Question
Title: Literature on delta encoding serializeable ADTs
Suppose that I have some nested algebraic data type (ie. something one can construct via `data`s in Haskell) that is serializeable (so no functional fields `a -> b`) is there any literature or known algorithms about how to *automatically* derive an *efficient* delta encoding of a change to that data type.

```
data ADT = ...

data ADTDelta = ...

applyDelta : ADTDelta -> ADT -> ADT

```

There are a lot of interesting aspects to this problem, but I am not familiar enough with the CS theory to know how to phrase this question to find prior work. I italicized automatically because one would want to keep the two data types in sync and efficiently because the use case I have in mind has small changes to the data type passed over a costly communication channel.

For example, given a regular optional or maybe type

```
data Optional a
  = Some a
  | None

```

one good representation of a delta could be

```
data DeltaOptional a delta
= Replace a      -- When we go from None -> Some a
| Modify delta   -- Recursively change `a` inside of a Some
| Delete         -- Some a -> None

```

# Answer
I suspect you're not going to like this answer, but the answer is yes, there is an algorithm to automatically derive a delta encoding. Given two instances of this data type, you can recursively compute the difference between them. The diff only contains the portion of the tree that corresponds to parts that are different in both. If an element is different in the two trees, then the delta indicates to replace the old value with a specific new value, and lists the new value.

You can augment this with custom algorithms for computing delta for particular data types if you wish. For instance, if you are computing the difference between two strings, instead of the delta containing the entire new string, it could contain just the "diff" between the two.
> 1 votes

---
Tags: functional-programming, haskell
---


title: Finding max value in a min- heap

text:
# Question
Title: Finding max value in a min- heap
What is the time complexity of finding the maximal value in a minimum heap with n nodes? Can I assume the maximal value is in one of leafs? If yes, there are ceil n/2 leafs. Does that make the time complexity to O(ceil\[n/2\]). Is there a way to find the maximal value in O(logn)?

# Answer
> 1 votes
The maximum value *must* be a leaf, otherwise the heap condition would be violated at that node. For an $O(\log n)$ complexity to be possible, the leaves should be in sorted order, and that does not make a standard heap anymore (updates would be quite different).

---
Tags: data-structures, big-o-notation
---


# Question
Title: Maximum Independent Set of a Tree using Greedy Algorithm
I was attempting to solve "Maximum Independent Set of a Tree" and came up with an algorithm that resembled this one Why is greedy algorithm not finding maximum independent set of a graph?

Code extract shown here:

```
Greedy(G):
S = {}
While G is not empty:
    Let v be a node with minimum degree in G
    S = union(S, {v})
    remove v and its neighbors from G
return S

```

Would this algorithm work for trees? Why or why not?

# Answer
> 2 votes
Yes, it would work for trees (acyclic graphs in general).

You need to prove one thing. Let $\ell$ be a leaf in a tree. Then there exists a maximum independent set that contains $\ell$.

The proof sketch is as follows. Let $S^\*$ be a maximum independent set and assume that $\ell \notin S^\*$. Since it is maximum, the unique neighbor $v$ of $\ell$ is in $S^\*$. Since $v$ is $\ell$'s only neighbor, we can create a new independent set $S = S^\* \setminus \\{v\\} \cup \\{\ell\\}$ with the same size.

This proves that your code is correct. (Strictly speaking you also have to argue that you can put isolated vertices in $S$, but that's fine.)

---
Tags: algorithms, graphs, trees, greedy-algorithms, independent-sets
---


# Question
Title: What are the disadvantages of Fibonacci Heaps?
A Fibonacci heap is a data structure for priority queue / heap operations. It seems to have the best complexity for all operations:

Since it has the best performance, why not use it everywhere? What are the disadvantages of it?

# Answer
> 6 votes
$O(1)$ merely means that no matter how large your heap grows, the operation will always take roughly the same time to execute. It doesn't mean "the fastest".

Wikipedia article you linked has section named "Practical considerations":

> Fibonacci heaps have a reputation for being slow in practice due to large memory consumption per node and high constant factors on all operations. Recent experimental results suggest that Fibonacci heaps are more efficient in practice than most of its later derivatives, including quake heaps, violation heaps, strict Fibonacci heaps, rank pairing heaps, but less efficient than either pairing heaps or array-based heaps.

# Answer
> -1 votes
It's a bit cheating to call insert and decrease-key O(1), because the implementation is incredibly lazy. The insert and decrease-key increase the entropy of the heap (makes it more messy). Instead of rebalancing immediately (which would make it O(log n)), it procrastinates until delete-min is called, which makes that operation more expensive. It's almost like the Fibonacci heap was invented for the sole purpose of looking good on a time complexity table like that!

So yes, consecutive calls to insert and decrease-key are technically O(1), but it results in mounting debt that you'll have to repay at some point. Since delete-min is the entire point of the priority que, you can't really avoid it. Therefore overall it's not necessarily going to have better performance than alternatives. In fact, it could even be outperformed by non-heap alternatives such as take-min operation on a binary tree.

The O(log n) listed for delete-min is amortized complexity, not worst case complexity. A disadvantage is that due to buildup of entropy/debt as described above, the actual cost of a given call could be as much as O(n). Another disadvantage of the Fibonacci heap is that it uses more memory per element than alternatives like binary heap.

---
Tags: algorithms, heaps, priority-queues
---


title: Automated theorem provers using models

text:
# Question
Title: Automated theorem provers using models
I am wondering if they are automated theorem provers which can take as input known models of the theory, for example to help discard statements which are not correct. For example, if the statements are about group theory, the prover could have access to a collection of examples of groups. This approach has been used in synthetic geometry by Gelernter using the standard euclidean model (see "An Examination of the Geometry Theorem Machine" by P. C. Gilmore, page 179). I wonder if it has been used in other fields ?

# Answer
> 1 votes
This is more of a long comment than an answer, but here goes. There's lots of stuff based on the paper you cite, starting with this Ray Reiter paper. This paper in turn seems to have kicked off all kinds of papers. David Plaisted has also done work in this area.

---
Tags: artificial-intelligence, automated-theorem-proving
---


# Question
Title: Time bounded Kolmogorov complexity and one way functions
I recently read the following article https://www.quantamagazine.org/researchers-identify-master-problem-underlying-all-cryptography-20220406/ which links to https://arxiv.org/abs/2009.11514 that proves that the existence of one way functions is equivalent to the time-bounded Kolmogorov Complexity being impossible to compute in polynomial time for a certain fraction of inputs.

But it seems to me obvious that it is impossible to compute time bounded Kolmogorov complexity K without running (or at least checking) all programs of size less than K, of which there are an exponential number (since how else would one know that a program does not output a string x in t(x) time?) so it should always take exponential time to calculate time bounded Kolmogorov complexity. This would imply that one way functions exist according to the authors.

Clearly this was not obvious to the authors of the arxiv paper or the authors of Quanta since they didn’t mention it. My question why don’t people think this is obvious?

# Answer
While intuitively it seems correct, in cryptography you can't assume anything about the particular algorithm an opponent runs. We don't know how to prove that there's no clever way to eliminate many of these programs and remain only with a polynomial number to check.

This is similar to the problem of $P = NP$. While intuitively it makes sense that $P \neq NP$ since you would have to enumerate all exponentially many certificates, we don't know how to prove there's no clever trick which would allow solving the problem in polynomial time.
> 1 votes

---
Tags: complexity-theory, kolmogorov-complexity, one-way-functions
---


# Question
Title: Find and keep minimum and maximum values in circular buffer structure
The **circular buffer** is filled with data one value at a time. The buffer size is N elements (let's take 3 as an example). Is there an algorithm that allows you to always know what is the minimum and maximum of the data in the buffer at a given time?

Example:

```
Initial samples: {3 4 3 1 5 2 7 3 4 1}

Step 1: {[3] 4 3 1 5 2 7 3 4 1} -> The max of [3] is 3.
Step 2: {[3, 4] 3 1 5 2 7 3 4 1} -> The max of [3 4] is 4.
Step 3: {[3 4 3] 1 5 2 7 3 4 1} -> The max of [3 4 3] is 4.
Step 4: {3 [4 3 1] 5 2 7 3 4 1} -> The max of [4 3 1] is 4.
Step 5: {3 4 [3 1 5] 2 7 3 4 1} -> The max of [3 1 5] is 5.
Step 6: {3 4 3 [1 5 2] 7 3 4 1} -> The max of [1 5 2] is 5.
Step 7: {3 4 3 1 [5 2 7] 3 4 1} -> The max of [5 2 7] is 7.
Step 8: {3 4 3 1 5 [2 7 3] 4 1} -> The max of [2 7 3] is 7.
Done.

The output is therefore {3, 4, 4, 4, 5, 5, 7, 7}.

```

# Answer
> 1 votes
Though you don't specify it, you probably mean *in constant time* (otherwise just compute the minimum and maximum in linear time). I don't think that this is possible.

There is a nice procedure to compute sliding window extrema, described in "Efficient Dilation, Erosion, Opening and Closing Algorithms" by Joseph Yossi Gil & Ron Kimmel. It takes no more than 3 comparisons per element, whatever $N$, and requires extra buffers.

Unfortunately, it can only deliver all results on every other $N$ elements.

If you allow $\log(n)$ behavior, a min-max heap can do.

---
Tags: time-complexity, data-structures, maximum-subarray
---


# Question
Title: Wait-Free implementation of an incremental counter
I know the theoretical difference between lock-free and wait-free algorithms, but it's a little hard to me to figure out how do they differ in implementation (code). In particular, i would like to know how would the implementation (code) of a counter be. Thanks

# Answer
> 0 votes
The lock free implementation will be Compare and Swap(CAS) on the counter, inside an indefinite while loop.Let's call it the increment method.The wait free version will have a help method and an announce method.The while loop will run for a fixed number of times, if the CAS does not succeed in these tries, the thread will "announce" for help by writing in it's id to a shared data structure.As soon as thread enters the increment(),it will first "help" all the operations that have been announced. PS:In my implementation,the counter is a structure consisting of integer value, thread id and other information.

---
Tags: algorithms
---