# Question
Title: Advantages and disadvantages of microcoded vs hardcoded architectures
### Preamble

I can't understand what are the advantages and disadvantages of microcoded processor architecture and hardcoded one.
Basically what I understood is that a microcode architecture divides an istruction in more microinstructions. I didn't found much documentation written in a simple way (too much complicated) so I'm asking you: **what are the advantages and disadvantages of each one?**
Due to the large amount of aspect of this "subject", I'll recap the question into three main aspects:

### Question (architectural point of view)

A microcoded architecture should semplify the design of each instruction, it means that it's do much more difficoult to design a full hard coded processor?
Or maybe hardcoded archtecture is suitable for microcontrollers or smaller design?

### Question (performance point of view)

Wikipedia (not the most reliable source, I know) says that a microcoded architecture is a **little** slower than an hardcoded one. It also says that microinstruction are used to build complex instruction, but these are not commonly used because programmers prefer high level languages, and compilers prefer using simpler but faster instruction.
From this point of view, is still necessary to design microcoded processor?

### Question (functional point of view)

If microcoded archtectures help the creation of complex instruction (= easier assembly development?), hardcoded ones help programmers in any way during their work? This seems a stupid question but I think it's not.
Looking at this site of assembly game programmers (I hope I can post that link, FAQ says to share your research), one guy says that HuC6280 processor has the best instruction set because:

> Fav\[ourite\]: HuC6280.
> Basically a 65CS02 set (Rockwell's added instructions).
> Optimizing is soo much fun. There are some super crazy optimizations for this style chip out there.
> I know people will fight to the death (or possibly argue) that it's not RISC, but it definitely had some precusor ideas of RISC.
> A very small, simple, but fast instruction set (hard coded, not microcoded), a large set of 128 16bit address registers (also halved as 256 8bit data registers).
> The immediate operand instructions are very fast and lend themselves perfectly for self modifying code.
> The downside is the small logical address range of the PC. All optimizations have to be made local and very specific.
> Look up tables (LUTs) need to be organized accordingly (and interleaved for 16bit and wider data elements).
> One thing I never understood is why they never implemented immediate operand opcodes as 1 cycle instead of 2, since the chip would perform a fetch cycle while operating an ALU operation on other opcodes.
> Same for implied instructions (flag changing).

He seems to be very excited about that architecture. One point to hardcoded design?
However, I found that HuC6280 is an 8bit processor, it is much much simplier than modern ones. It means that hardcoded would be preferrable **if** its design wasn't so hard?
**EDIT:** He also quote self modifying code, which is not commonly used today (due to high level programming maybe) but for assembly programmer is quite an important feature.

### Examples

I know that this is an hard question, explanation might be long. If you (guy with much more experience than me) want to answer, may you add some example of hardcoded architecture? It would be much appreciated. Both modern and deprecated are ok
And thanks for reading all this poem

# Answer
> 6 votes
The distinction between "microcoded" and "hardcoded" multi-cycle control units is a relatively small implementation detail. The distinction was more important in the 1950s when people were inventing new implementation techniques for state machines. In modern processor design there are much more important implementation distinctions, like how much pipelining and instruction overlap you are going to try to achieve, whether you are going to speculatively execute instructions, and whether you are going to try to schedule instructions out-of-order.

That said, here's the distinction: We divide the design into datapath and control. Here's the picture of the MIC-1 from Tanenbaum's Computer Organization book. (The image is by Suyog.karnawat, from Wikimedia commons.) Everything in the design is the datapath except the box in the upper right hand side that says "Instruction decoder and control logic."

The "Insruction decoder and control logic" box is a finite state machine. The datapath in this example is very simple, with only a single bus, so even an instruction to add two registers and put the result in a third register takes multiple cycles (each of which corresponds to a state in the state machine.)

Each instruction goes through the following steps/states (each of which takes a cycle)

1. move the PC (Program Counter) to the MAR (Memory Address Register)
2. assert the controls to perform a load from the memory bus
3. eventually the memory will return the requested data (which corresponds to the next instruction) and put it in the MDR (Memory Data Register)
4. move the instruction from the MDR to the IR (Instruction Register). At this point the instruction gets decoded and we figure out what to do with it. In this case it's an add operation so we know we need to:
5. move Ra to the X register
6. put Rb on the bus (so that it will go to the B input of the ALU) assert the ALU control lines and Mux select appropriately to do an add operation, the result of which will get saved in register Y
7. Move Y to the Rc register, and then every non-branch instruction ends by incrementing the program counter:
8. Put the PC on the bus, set up the ALU to increment (Select the MUX to put constant 1 on the A input and set up the ALU to Add) so that PC+1 will get saved in the Y register
9. Move the Y register back to PC

So 9 state transitions to perform a simple add instruction.

So the "Instruction decoder and control logic" is a finite state machine with inputs from the IR register, outputs are the control signals, and there must be some flip-flops inside to represent the state of the state machine. But there are lots and lots of ways to implement a state machine.

1. $\lceil \log\_2 N \rceil$ flip-flops (where $N$ is the number of states) and a lot of combinational logic (to calculate the control signals and next state).
2. $N$ flip-flops with one-hot encoding and a bunch of combinational logic (usually less than with option A, but a lot.)
3. Somewhere between $\lceil \log\_2 N \rceil$ and $N$ flip-flops with some combinational logic of intermediate complexity.

And the combinational logic for the control signals and next state functions can be implemented any number of ways:

1. As NAND gates reduced (using Quine-McCluskey, or whatever) to sum-of-products form.
2. As NAND gates reduced to some relatively efficient multiple-level circuit. (This is probably what people think they mean when they talk about "hardwired control.")
3. A design using Multiplexers for the combinational logic
4. A design using Programmable logic arrays (although I don't know if you can even buy these anymore.)
5. A design where the combinational logic is implemented with a ROM. (This is probably what people think they mean when they talk about "microcoded control.") The ROM might be a EEPROM so that it is somewhat easier to modify if you find a bug.

ROMs can get really huge if you're not careful. For example a ROM-based design would almost always use $\lceil \log\_2 N \rceil$ flip-flops, because making the state wider also makes it sparser, which is sometimes good for gates but not for ROMs. Also, you would only use the opcode bits as part of the address to the ROM, not the register specifiers and such.

Finally with ROMs you might choose to make the microcode word wide (the microcode word produces the entire set of bits for the control signals) or narrow (the microcode word chooses one of a smaller number of possible control signal combinations and then there's a second ROM that translates from that smaller number to the actual required control signals.

So the distinction between "hardcoded" and "microcoded" is only one very small decision that needs to be made among hundreds of design decisions. And it's certainly not the most important one. (For example, you could choose to put a second bus on the datapath, which would enable you to perform some instructions with a lot less cycles.)

---
Tags: computer-architecture
---


title: Finding Kernel in DAG

text:
# Question
Title: Finding Kernel in DAG
Let $G=(V,E)$ be a DAG. A subset $A \subseteq V$ is called a **kernel** if for all $u,v \in A$ $uv \notin E$ and for all $v \in V-A$ there exists an $a \in A$ such that $av \in E$ (note again, this is a directed graph).

I need to find an algorithm that runs in $O(V+E)$ that upon giving a DAG $G$, would find a kernel in the graph.

I started like this:

Sort the graph toplogically. Such a sorting exists since it is a DAG. Let us mark the output as $v\_1, v\_2,...,v\_n$. Then we run right to left:

If $v\_n$ has no ingoing edges, we add it to our kernel set $K$. Else, here I got stuck.

Maybe dynamic programming can help us here?

# Answer
Let's start the algorithm with these 3 sets:

* $V$ = {all vertices}
* $K$ = {}
* $K'$ = {}

with the semantics:

* $V$ stores unprocessed vertices
* $K$ stores vertices known to be in the kernel
* $K'$ stores vertices known to be outside the kernel

You're right that all vertices without incoming edges always belongs to the kernel. Add the them to the set $K$ & remove from $V$.

The next step is realizing that any vertices that can be immediately reached from vertices in the current $K$ must be outside the kernel. Add these to $K'$ & remove from $V$.

Now, all the vertices that is left in $V$ without incoming edges (from other vertices inside $V$) again can be added to $K$ (and remove from $V$).

...

Repeat the process until $V$ is empty.
> 4 votes

---
Tags: algorithms, graphs
---


title: Bytes--Measured or Counted

text:
# Question
Title: Bytes--Measured or Counted
I hope the Computer Science section is the appropriate place to ask this question. I’m working on profiling some data sets and I am a bit tripped up on something, I was hoping I could get some assistance.

Part of my project is to determine whether some of my data is an integer and whether is a continuous or discrete quantity.

I understand that in a simple sense Discrete data is counted and Continuous data is measured. I also know Discrete Data can only take on certain values while Continuous Data can take on any values.

It seems that the size of a computer file (in bytes) could take on either of these descriptions because bytes are based on bits and are based on a power of 2 (which would make it discrete). However at the same time a file size could be Continuous because it could be of any size.

If anyone could help me out it would be greatly appreciated! Also if you are aware if I misunderstood something please let me know!

# Answer
> 3 votes
A file size is measured in bits, you cannot have a portion of a bit, only a whole bit, it is a discrete quantity. Something is continuous if it can can have any possible value in a range, bounded or not. Something can be discrete and at the same time infinite.

The best way to think about discrete or continuous is if for any two values you can find a value between them then it is continuous, otherwise it is discrete.

---
Tags: discrete-mathematics
---


# Question
Title: Use Dijkstra to find negative cycles in a graph
I will state the problem:

> Suggest an algorithm that works in $O(|E| + |V|log|V|)$ time that checks if there are negative cycles in a graph.

So, I saw the runtime, and I immediately said we need to use Dijsktra's implementation with a fibonacci heap. I suggested the following:

> 1. Run dijkstra, and mark the distances array as $d$. -- $O(|E| + |V|log|V|)$
> 2. Do relax on each edge -- $O(|E|)$
> 3. For each edge $\<u,v\> \in E$: -- $O(|E|)$
>
> 3.1 if ( $d\[v\] \< d\[u\] + w(\<u,v\>)$), report "negative cycle".
> 4. report "No negative cycles"

Would this work?

# Answer
> 2 votes
No, it won't work. If your graph has a negative weight edge and Dijkstra computes the shortest paths wrong, then it might be possible to relax an edge (to make the shortest paths correct) even though there is no negative-weight cycle in the graph.

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


# Question
Title: Does Herbrand's theorem mean any first-order logic formula can be expressed in CNF?
Herbrand's theorem shows that any formula of first-order logic can be expressed as a disjunction of quantifier-free formulas of first-order logic.

Is this equivalent to saying that Herbrand's theorem shows that any first-order logic formula can be expressed in Conjunctive Normal Form (CNF)?

# Answer
Well, that's not really what Herbrand's theorem says. That's not a good way to think about Herbrand's theorem. To understand the answer to your question, you first need to understand a little better what Herbrand's theorem does and doesn't imply.

I suspect I know what you are thinking. You are thinking, given a statement $\varphi$ of first-order logic, you can find a disjunction $\psi\_1 \lor \dots \lor \psi\_k$ of quantifier-free formulas that is equivalent to $\varphi$. However, that's not really what Herbrand's theorem says. Herbrand's theorem doesn't necessarily give an effective or easy way to *find* the disjunction. Herbrand's theorem says that if $\varphi$ is true, then there *exists* such a disjunction, but to actually find the disjunction, you have to know that $\varphi$ is true, and you have to know a proof that it is true (roughly speaking).

Let me give you an example and an analogy that may clear things up. Here is D.W.'s theorem:

**D.W.'s Theorem.** Any formula of first-order logic can be expressed as either True or False. In other words, for every sentence $\varphi$ of first-order logic, there is a formula $\psi \in \\{\text{True}, \text{False}\\}$ such that $\varphi$ is valid if and only if $\psi$ is valid.

D.W.'s theorem is trivially true; I can prove it in a single line. Pretty cool, huh?

However, D.W.'s theorem is actually not very useful. Given a formula $\varphi$ of first-order logic, D.W.'s theorem doesn't help you figure out whether $\varphi$ is valid or not. Similarly, Herbrand's theorem doesn't really help you figure out whether $\varphi$ is valid or not.

Now, the formula $\text{True}$ is in Conjunctive Normal Form. Also, the formula $\text{False}$ is in Conjunctive Normal Form. Therefore, by D.W.'s theorem, every sentence $\varphi$ of first-order logic is equivalent to some quantifier-free formula $\psi$ in CNF form. However, this probably not the kind of equivalence you were hoping for, because given $\varphi$, it's not necessarily easy to compute the $\psi$ that is equivalent to $\varphi$.
> 4 votes

---
Tags: logic, first-order-logic, normal-forms
---


# Question
Title: Examples for incomparable semi-decidable but undecidable languages
In Schönig and Pruim's Gems of Theoretical Computer Science, the following statement is made:

> 'Post's Problem', as it has come to be known, is the question of whether there exist undecidable, computably enumerable sets that are not Turing equivalent to the halting problem. In particular the answer is yes if there are two computably enumerable languages $A$ and $B$ that are incomparable with respect to $\leq\_T$, i.e. such that $A\nleq\_T B$ and $B\nleq\_T A$.

The text goes on proving that there exists such languages $A$ and $B$.

Does this imply undecidable recursively enumerable sets are not isomorphic to the halting problem? Are there examples of such languages?

# Answer
> 2 votes
Some undecidable r.e. sets are isomorphic to the halting problem, for example the halting problem itself. Others are not, for example the one constructed by Friedberg and Muchnik using the priority method, a complicated kind of diagonalization. This set is not easy to describe, though one could argue that its description is "explicit". For some references, check out the Wikipedia article on simple sets, or any lecture notes on recursion theory.

---
Tags: computability, undecidability, halting-problem, semi-decidability
---


title: Automated theorem proving with SAT

text:
# Question
Title: Automated theorem proving with SAT
If you had a polynomial time algorithm for determining boolean satisfiability how would you prove/disprove a conjecture like the Reimann-Zeta hypothesis (or the Pythagorean theorem for that matter) from axioms?

# Answer
If you believe that a proof or disproof has reasonable length, you could come up with one SAT instance which states *$x\_1,\ldots,x\_n$ encodes a proof of the Riemann Hypothesis*, and another one stating *$x\_1,\ldots,x\_n$ encodes a refutation of the Riemann hypothesis*. The formula will have size polynomial in $n$, though probably not linear; if you're careful, maybe quasilinear ($n\log^{O(1)}n$). You can then apply your magic SAT solver to find out which, if any, of these options is correct. Don't hold your breath, though – as mentioned in the comments, it is hard to imagine an algorithm which would be efficient enough to handle the required value of $n$ in a realistic amount of time.
> 4 votes

---
Tags: automated-theorem-proving
---


# Question
Title: Where does the lg(lg(N)) factor come from in Schönhage–Strassen's run time?
According to page 53 of Modern Computer Arithmetic (pdf), all of the steps in the Schönhage–Strassen Algorithm cost $O(N \cdot \lg(N))$ except for the recursion step which ends up costing $O(N\cdot \lg(N) \cdot \lg(\lg(N)))$.

I don't understand why the same inductive argument used to show the cost of the recursive step doesn't work for $O(N\cdot \lg(N))$.

* Assume that, for all $X \< N$, the time $F(X)$ is less than $c \cdot X \cdot \lg(X)$ for some $c$.
* So the recursive step costs $d \cdot \sqrt{N} F(\sqrt{N})$, and we know this is less than $d \cdot \sqrt{N} c \cdot \sqrt{N} \lg(\sqrt{N}) = \frac{c \cdot d}{2} \cdot N \cdot \lg(N)$ by the inductive hypothesis.
* If we can show that $d \< 2$, then we're done because we've satisfied the inductive step.
* I'm pretty sure recursion overhead is negligible, so $d \approx 1$ and we have $\frac{c}{2} N \cdot \lg(N)$ left to do the rest. Easy: everything else is $O(N \cdot \lg(N))$ so we can pick a $c$ big enough for it to fit in our remaining time.

Basically, without digging into the details that will contradict this somehow, it *looks like* things would work out if we assumed the algorithm costs $O(N \cdot \log(N))$. The same thing seems to happen if I expand the recursive invocations then sum it all up... so where is the penalty coming from?

My best guess is that it has to do with the $\lg(\lg(N))$ levels of recursion, since that's how many times you must apply a square root to get to a constant size. But how do we know each recursive pass is not getting cheaper, like in quickselect?

For example, if we group our $N$ initial items into words of size $O(\lg(N))$, meaning we have $O(N/\lg(N))$ items of size $O(\lg(N))$ to multiply when recursing, shouldn't that only take $O(N/\lg(N) \cdot \lg(N) \cdot \lg(\lg(N)) \cdot \lg(\lg(\lg(N)))) = O(N \cdot \lg(\lg(N)) \cdot \lg(\lg(\lg(N))))$ time to do. Not only is that well within the $N \cdot \lg(N)$ limit, it worked even though I used the larger $N\cdot \lg(N)\cdot \lg(\lg(N))$ cost for the recursive steps (for "I probably made a mistake" values of "worked").

My second guess is that there's some blowup at each level that I'm not accounting for. There are constraints on the sizes of things that might work together to slow down how quickly things get smaller, or to multiply how many multiplications have to be done.

---

Here's the recursive expansion.

Assume we get $N$ bits and split them into $\sqrt{N}$ groups of size $\sqrt{N}$. Everything except the recursion costs $O(N \lg N)$. The recursive multiplications can be done with $3 \cdot \sqrt{N}$ bits. So we get the relationship:

$M(N) = N \cdot \lg(N) + \sqrt{N} \cdot M(3 \cdot \sqrt{N})$

Expanding once:

$M(N) = N \cdot \lg(N) + \sqrt{N} \cdot (3 \cdot \sqrt{N} \cdot lg(3 \cdot \sqrt{N}) + \sqrt{3 \cdot \sqrt{N}} \cdot M(3 \cdot \sqrt{3 \cdot \sqrt{N}})$

Simplifying:

$M(N) = N \cdot \lg(N) + 3 \cdot N \cdot lg(3 \cdot \sqrt{N}) + \cdot \sqrt{3} \cdot N^{2-\frac{1}{2}} \cdot M(3^{2-\frac{1}{2}} \cdot \sqrt{\sqrt{N}})$

See the pattern? Each term will end up in the form $3^{2-2^{-i}} \cdot N \cdot lg(N^{2^{-i}} 3^{2-2^{-i}})$. So the overall sum is:

$\sum\_{i=0}^{\lg(\lg(N))} 3^{2-2^{-i}} \cdot N \cdot \lg(N^{2^{-i}} 3^{2-2^{-i}})$

We can upper bound this by increasing the powers of 3 to just 3^2, since that can only increase the value in both cases:

$\sum\_{i=0}^{\lg(\lg(N))} 9 \cdot N \cdot \lg(N^{2^{-i}} 9)$

Which is asymptotically the same as:

$\sum\_{i=0}^{\lg(\lg(N))} N \cdot \lg(N^{2^{-i}})$

Moving the power out of the logarithm:

$\sum\_{i=0}^{\lg(\lg(N))} N \cdot \lg(N) \cdot 2^{-i}$

Moving variables not dependent on $i$ out:

$N \cdot \lg(N) \sum\_{i=0}^{\lg(\lg(N))} 2^{-i}$

The series is upper bounded by 2, so we're upper bounded by:

$N \cdot \lg(N)$

Not sure where the $\lg(\lg(N))$ went. All the twiddly factors and offsets (because many recurrence relations "solutions" are broken by those) I throw in seem to get killed off by the $\lg$ creating that exponentially decreasing term, or they end up not multiplied by $N$ and are asymptotically insignificant.

# Answer
> 5 votes
The sticking point is the size of the integers in the recursive step, which is not quite $\sqrt{n}$, but rather twice as large, since the product of two $t$-bit integers has size $2t$. Assuming that we break the original $n$-bit integer into $\sqrt{n}$ parts of length $\sqrt{n}$, the running time recursion is $$ T(n) = n\log n + \sqrt{n}T(2\sqrt{n}), $$ and by expanding it, we get $$ \begin{align\*} T(n) &= n\log n + \sqrt{n}T(2\sqrt{n}) \\ &= n\log n + 2n\log (2\sqrt{n}) + 2^{1/2} n^{3/4} T(2^{3/2}n^{1/4}) \\ &= n\log n + 2n\log (2\sqrt{n}) + 4n\log (2^{3/2} n^{1/4}) + 2^{5/4} n^{7/8} T(2^{7/4} n^{1/8}) \\ &= n\log n + 2n\log (2\sqrt{n}) + 4n\log (2^{3/2} n^{1/4}) + 2^3 n \log (2^{7/4} n^{1/8}) + \cdots, \end{align\*} $$ so each level of the recursion takes time proportional to $n\log n$. Since there are $\log\log n$ levels, we get the quoted running time. For more information, check out these lecture notes.

# Answer
> 3 votes
The issue is that the expansion factor inside the recursive term is not less than 2, and that causes the bound to fail. Define:

$T\_c(n) = n \log n + \sqrt n T(c \sqrt n)$

I claim that $T\_{2-\epsilon}$ is $O(n \log n)$, but $T\_{2}$ isn't. This is probably most obvious when trying to prove the $n \log n$ bound by induction. Assume that $T\_c(n\_0) \leq 100 n\_0 \log n\_0$ for all $n\_0 \< n$. Then:

$T\_c(n)$

$= n \log n + \sqrt n T(c \sqrt n)$

$\leq n \log n + \sqrt n (100 c \sqrt n \log {(c \sqrt n)})$

$= n \log n + 100 c n (\log c + \frac{\log n}{2})$

$= (50 c + 1) n \log n + 100 c n \log c$

$= (50 c + 1 + 100 c \frac{\log c}{\log n}) n \log n$

${\LARGE ⊜} (50 c + 1 + \epsilon) n \log n$

Clearly this proof is only going to work if $50c + 1 \< 100$, which is only true when $c \< 2 - \frac{1}{50}$. We can move that threshold closer to 2 by increasing the arbitrary constant of 100, but we can't ever get the threshold to *reach* 2.

The algorithm needs *at least* a factor of 2 blowup because otherwise we lose information about the intermediate squared values (because the field is too small). So it must increase faster than $n \log n$.

---
Tags: algorithm-analysis, runtime-analysis, multiplication
---


# Question
Title: Build a scheduler, to simulate parallel game flow
I am building a strategy game where units can interact with each other.

As input I am getting a list of actions. I need to output a scheduler, that will tell when to start each action. The goal is to find the shortest time combination of all the actions.

Action is defined as interaction between two users or user with him self, it build from 4 parts:

1. performing unit - the unit that performs the action
2. receiving unit(optional) - the unit on witch the action is applied
3. supported actions - A list of actions that the receiving unit can perform while applying this action on him.
4. action time - how long does it takes to execute the action

Rules:

1. Units can only perform one action in a time
2. Units may have to perform more than one action

---

The best solution will be: Is to run all those actions in parallel. There are two things that stops me from doing it.

If more than one action have the same performing unit, they cannot start simultaneously as units can perform only one action in a time.(Rull 1)

The other problem is actions with receiving unit. I need to make sure that the receiving unit is currently performing one of the supported actions(defined in action part 4), if it's not, this actions cannot be started.

In case of actions without receiving unit, they can all be started simultaneously. How ever I need to make sure that I am not left with action that have a receiving unit, that cannot be started as the receiving unit already performed all his actions.(So supported action will never be started)

# Answer
> 2 votes
Your set of rules is self-conflicting. You require

> Same unit cannot perform two actions in parallel

but also

> When unit perform attack, the interacting unit must perform `take damage` \[...\] during the attack-action time of the performing unit.

and

> Multiple units can attack single unit at once

In other words, you require that multiple `take damage` actions be performed simultaneously while demanding that that may not happen.

---
Tags: concurrency
---


# Question
Title: How hard is this constrained $n$-rooks problem?
I asked this over on math.stackexchange.com, then I found out about this forum.

Suppose you have an $(n\times n)$-chessboard, together with a constraining function $C : n \times n \to 2$ where $C(i,j) = 1$ iff you're allowed to place a rook in the $ij$-square. Consider the problem:

> Can $n$ non-attacking rooks be placed on the board in squares allowed by $C$?

Is it NP-Hard?

Here's an alternative formulation: Let $x\_1, \dots, x\_n$ be elements (integers, say) and $P\_1, \dots, P\_n$ unary predicates such that $P\_ix\_j$ can be evaluated in constant time. Is there a permutation $\sigma \in S\_n$ such that $P\_ix\_{\sigma(i)}$ for all $i$?

The equivalence can be seen by letting $C(i,j) = 1$ iff $P\_i(x\_j)$. Then a placement of rooks yields a witness to the permutation problem by letting $\sigma(i) = j$ iff there's a rook in square $ij$. $\sigma$ is a permutation because all $n$ rooks are placed in a non-attacking arrangement. $P\_ix\_{\sigma(i)}$ holds because $\sigma(i)=j$ implies theres'a rook in the $ij$ square, which implies $C(i,j) =1$, which, by definition, implies that $P\_i(x\_j)$.

# Answer
This problem can be solved in polynomial time, using bipartite matching.

For a bipartite graph with $n$ vertices on the left, corresponding to the $n$ rows, and $n$ vertices on the right, corresponding to the $n$ columns. Include an edge from $i$ to $j$ if $C(i,j)=1$, i.e., if you're allowed to place a rook in the $(i,j)$ square (in the $i$th row and $j$th column). Now check whether there exists a perfect matching of this bipartite graph. This can be done in polynomial time using standard algorithms.

Notice that there exists a perfect matching if and only if there exists a way to place the rooks so they are non-attacking. Each edge in the matching corresponds to a place where a rook should be placed. Two rooks can attack each other only if they share the same row or the same column. A matching cannot have two edges that share the same left-vertex (same row) or same right-vertex (column), which means that any matching containing $n$ edges corresponds to a way to place $n$ rooks so they don't attack each other.
> 10 votes

---
Tags: complexity-theory, np-hard, permutations
---


# Question
Title: Is random access allowed in the Bit Complexity model, or is it just expensive?
In the RAM model, you're allowed to do unbounded indirect access (pointers can be arbitrarily large and still fit in a single machine word).

In the Bit Complexity model (no wiki article, sorry), machine words are constant sized. So storing the address of an entry in a table of size $N$ would require $O(lg(N))$ words.

This raises the question: Are you even *allowed* to do a multi-word random access into a table of size $N$ when using the bit complexity model? It's a bit of a strange operation, because the machine can't "hold the jump in its head" while making it. On the other hand, it could be allowed but cost $O(lg(n))$ time instead of the RAM model's $O(1)$ time.

I realize that this is basically just a definition, with interesting things on either side, but I'm wondering what the *common* definition is. Is bit complexity just another way of saying "multi-tape turing machine"?

# Answer
> 1 votes
According to Fürer's paper, the underlying complexity model is a Turing machine without random access, or equivalently, Boolean circuits. So no random access is allowed. Check also Diem's writeup on the subject.

---
Tags: complexity-theory, terminology, computation-models
---


# Question
Title: Does a multi cpu system not improve the first come first serve (fcfs) cpu scheduling algorithm?
I created a program that simulates the fcfs scheduling algorithm. First I implemented it for a single core, then modified it for four homogenoues cpus.

I compared the results with several datasets, and for the most part they are identical.

I understand fcfs is nonpreemtive, so there are no context switches. Then each cpu holds the process until its current cpu burst is finished, from there it either terminates or does IO (goes to wait queue).

Im guessing a multi core system only improves performance if many processes are in the ready queue at the same time, otherwise only one cpu is being used.

Here is the algorithm that I implemented:

```
while(TRUE)
{
    for(i = 0; i < NUM_CPUS; i++)
    {
        if(!cpu[i].idle)
        {
            if(cpu[i] is finished executing current burst)
            {
                //either move the process from the cpu to the waitQ, or terminate process if finished all bursts
                if(terminatedPrs == numberOfProcess)
                    break;
            }
        }
        if(waitQ->front != NULL)
        {
            //Check if waitQ->front is finished io
            if(waitQ->front finished IO burst)
            {
                //insert waitQ->front to readyQ, then dequeue waitQ
            }
        }
        if(cpu[i].idle)
        {
            if(readyQ->front != NULL)
            {
                //check if readyQ->front is ready to be executed (that is, arrival time < elapsedTime)
                if(readyQ->front ready to be executed)
                {
                    //move readyQ->front to CPU (begin executing), and dequeue readyQ
                }
            }
        }

    }
    elapsedTime++;
}

```

Is my algorithm fine? I am getting pretty much the same average waiting time, average turnaround time and average cpu utilization.

# Answer
Sounds like something's very wrong. My guess is that you are testing with a load that is too small. You should be able to increase the number of processes and at some point the 4-processor system should be able to handle about 4 times as many processes.

Let's try a simple asymptotic analysis:

Suppose we have $N$ processes each of which goes through the following cycle repeatedly (forever):

1. Wait in the ready queue until a CPU is available.
2. Run on the CPU for average time $S$.
3. Request an I/O that takes average time $Z$.
4. Go back to the ready queue.

What's the *minimum* average response time $R\_{\mathrm{min}}$, for going through this cycle once? $S+Z$. (That's the average time for service at the CPU plus average time for I/O, and *no* time waiting in the queue.) So

$$ R \geq S+Z. $$

Now Little's Law says that the average response time $R$ is equal to the number of processes in the system, $N$, divided by the system throughput, $X$ (in units of number of times through the entire cycle each second).

$$ R = \frac{N}{X}. $$

What's the *maximum* throughput this system can achieve. That would happen in the (unrealistic) case that all the processors were busy all the time. There are $P$ processors and each CPU burst consumes average time $S$, so the maximum throughput is $P/S$. That is $X \leq P/S$. So

$$ R \geq \frac{N}{X} = \frac{NS}{P}. $$

That is, when $\frac{NS}{P} \geq S+Z$ you should start to see the average response time increasing linearly as you increase the number of jobs in the system. Below that and you won't see much difference.
> 3 votes

---
Tags: algorithms, operating-systems, process-scheduling
---


# Question
Title: Lexing and parsing a language with juxtaposition as an operator
Normal human math notation treats juxtaposition as implied multiplication, e.g., $2x$ means $2$ multiplied by $x$. This does not seem to be a common feature of computer languages, although it was, for example, supposed to be included in the language Fortress (now a dead project).

Lexing and parsing such a language seems to me like it would be difficult within the usual lexer-parser framework. In a computer language, unlike human math notation, we want to have variable names that are more than one letter. So if we need to lex the string `xyz`, we have a problem, because this could, e.g., mean `x*yz` if `x` and `yz` are variables, but it could also mean `xy*z` if `xy` and `z` are variables. The lexer normally wouldn't have this type of information available, so it would have no way of resolving the ambiguity.

Are there ways of reducing this problem to a more standard form that can be handled by a traditional lexer-parser pair, or does it require qualitatively different techniques?

# Answer
> 2 votes
There is no issue parsing a language which uses juxtaposition as an operator provided that it is possible to identify lexical tokens. For example, `awk` uses juxtaposition for string concatenation, and the following expressions are completely valid:

```
last_name", "first_name
last_name ", " first_name
last_name comma space first_name

```

However, two juxtaposed variables must be separated by whitespace to satisfy the lexical constraint. Whitespace is also used to resolve the ambiguity:

```
last_name(", ")

```

which might be a function call or a concatenation. Since awk does not require function definitions to precede use of the function, it cannot disambiguate based on the type of `last_name`; instead, it specifies that a function call cannot have whitespace between the function's name and the `(`, so that the above is a function call, while:

```
last_name (", ")

```

is concatenation.

Fortress's syntax has (or had) a number of other issues which are harder to solve with a simple yacc/lex parser; if I recall correctly, the proof-of-concept implementation used a packrat parser. For example, the syntax allows the use of vertical bars either as operators or as brackets, so `|a|` might be the absolute value of `a`. Somewhat complicated whitespace rules were used to disambiguate, and there are other situations in which whitespace is significant, affecting operator precedence. In my opinion, the apparent convenience of having a language which resembles mathematics is out-weighed by the possibility of an unintended parse changing the semantics of the program without any indication as a warning or error. (This sort of issue plagues some more conventional languages also.)

Another class of languages in which juxtaposition is common are unit-aware languages (or calculators), such as GNU Units or Frink. As far as I know neither of these requires any special parsing technology, although there is a general issue with the solidus (`/`) which can require careful juggling of operator precedence. It's clear what:

```
2 cm/sec

```

means. But what about the following:

```
2/3 cm/sec
2 cm/3 sec
2 g/cm sec^2

```

(It's relevant that SI insists on parentheses and prohibits multiple solidus symbols, so that the last value must be written as `2 g/(cm sec<sup>2</sup>)`; neither `2 g/cm sec<sup>2</sup>` nor `2 g/cm/sec<sup>2</sup>` are correct.)

Again, this is not so much a parsing issue as a user interface design problem.

# Answer
> 3 votes
Juxtaposition is used in mathematics because most mathematical texts use single character variables (possibly with diacritic signs, subscripts, superscripts, etc...) so that there is no ambiguity.

A mathematician might write $2x$ to multiply $2$ and $x$. It would be quite unusual to write $x2$ to multiply $x$ by $2$. Actually, as much as I can see (but I am open to contrary examples) a numerical factor always comes first in the product. This unstated rule implies that one never has two numerical factors in succession, which would make it difficult to interpret $22$, which could be $2\times 2$ or the single number $22$. Of course, if two numerical factors in a row were to be acceptable, they would be separated by a space to avoid ambiguity.

Regarding variables, the same has to be true. Several variables can be factors of a product (well, a sequence of products). Either you have a rule that all variables are 1 letter (a constraint that cannot be imposed on numbers), or you maust have a way to separate the variables, either by a space, or by a $\times$ sign.

First I would point out that this is a pure lexer problem: how do I determine what variables are juxtaposed as the factors of a product. The fact that the operator are omitted is not really an issue for the parser (though it may call for some appropriate techniques depending on other syntactic aspects of the language, and the way they interact with the feature we are discussing).

Of course, you can start playing games, like the following which you seem to be actually suggesting. Since all variables are supposed to be declared (that is also true in mathematics), you could juxtapose variables arbitrarily, without spaces, to form a product, and rely on the lexer to determine how to cut the string so that each cut out substring is a declared variable. Of course, depending on what variables you have declared, this can have an ambiguous result (as you suggest in your question), and produce a lattice of variables instead of a sequence of variables.

I created the expression "lattice of variables" after the expression "word lattice" used in speech recognition for exactly the same problem in a different setting. For example, given that you have declared the seven variables: a b c d ab bc cd. Then the string abcd can be cut into several sequences of variables, that can be represented by a loopless finite state automaton like the following (which is what is called a word lattice in speech processing).

```
     /--- ab ---\
    /            \
    --- a --- b --\--cd --------\
-- /     \                       > -----
   \      \-- bc ------/--- d --/
    \                 /
     \-- ab --- c ---/

```

Creating this lattice is not difficult, using finite state techniques, when the available variables are known. It would however probably require some changes in standard lexers, as they usually identify lexical element with simpler techniques, simpler use of context.

One way to do it is for the lexer to first identify the string as an expression. It could then call a routine that would access the current symbol table to find relevant identifiers and organise them as a trie to cut the string into existing identifiers. Assuming no ambiguity, the lexer could then give the successive identifiers to the parser, interspersed with $\times$ symbols. So it is rather easy to integrate into existing architectures.

To limit the ambiguity, one can first eliminates by type checking all variables with a type incompatible with use as factor in a product. Or possibly, if there are different kinds of products requiring compatible types, this can be used to eliminate inconsistant sequences of variables.

Remaining ambiguities would probably no be a major problem for the parser (possibly depending on parsing techniques, typing ...). But of course, the ambiguity has to be resolved at some point, if the language is supposed to convey only one meaning.

One way to do it could be to notify an error whenever such an ambiguity is found, with some details about the ambiguity, thus requesting the user to disambiguate by adding a space or a $\times$ symbol.

Though this can be handled technically, I do not think I would recommend it in a language. Even if unambiguous, this is not extremely readable, notwithstanding the fact that the ancient languages such as Latin and Greek used to be written that way.

An alternative could be to accept this kind of notation only with the usual constraints (in mathematics) that I stated above: number must be first and variables must have a single letter for implicit product. But ambiguity could remain between a single variable $xx$ and the product $x\times x$ written without the $\times$ symbol. I guess it would not be very hard, with standard technology.

I think I have exhausted my imagination on this topic. It is not technically difficult, for what I can see. But why would all this be worth the trouble?

---
Tags: compilers, parsing, ambiguity
---


title: A Reduction from XORSAT to 2-SAT

text:
# Question
Title: A Reduction from XORSAT to 2-SAT
Does anyone know of a non-trivial reduction from XORSAT to 2-sat since they are both in P? (By non-trivial I mean one that does not just solve the instance of XORSAT and map it to a fixed instance of 2-sat. Rather I'm looking for a way to solve XORSAT by a different method other than just using Gaussian Elimination or some other method of linear algebra.)

# Answer
> 5 votes
Your problem can be posed more formally as follows: *Is there a* weak *reduction from XORSAT to 2SAT?* Here weak can be, for example, logspace or AC$^0$.

We know that 2SAT is NL-complete under AC$^0$ reductions, while restricted versions of XORSAT (say 3XORSAT) are $\oplus$L-complete under AC$^0$ reductions, see this paper proving a refined Schaefer dichotomy theorem. Although NL$\subseteq \oplus$L non-uniformly (see this answer), we don't expect the converse to hold, and in particular we don't expect there to be a weak reduction from $\oplus$L to NL. Unfortunately I'm unaware of any concrete results in this direction.

Summarizing, it is expected that there is no weak reduction from XORSAT to 2SAT, but I'm not sure there's much technical work supporting this conjecture.

---
Tags: complexity-theory, reductions, satisfiability, polynomial-time
---


# Question
Title: What are the definitions of syntax and semantics?
1. For **a formal language** $L \subseteq \Sigma^\*$ over an alphabet $\Sigma$. From https://proofwiki.org/wiki/Definition:Syntax

> **The syntax of a formal language** is its **structure**, and is specified by a formal grammar of the formal language.

From http://en.wikipedia.org/wiki/Syntax\_%28logic%29

> In logic, **syntax** is **anything having to do with formal languages** or formal systems without regard to any interpretation or meaning given to them. Syntax is concerned with the rules used for constructing, or transforming the symbols and words of a language, as contrasted with the semantics of a language which is concerned with its meaning

* How do you define the "structure" of a formal language, and therefore define the syntax of a formal language? Ideally define them formally or mathematically?
    * The syntax of a formal language should be defined formally, because it pertains to the formal language which is defined formally as a subset of $\Sigma^\*$, right?
    * Raphael once said that the syntax of a formal language is the language itself. Is it true?
    * From http://en.wikipedia.org/wiki/Syntax\_%28logic%29

    > **Syntax** is usually associated with **the rules (or grammar)** governing the composition of texts in a formal language that constitute the well-formed formulas of a formal system.

    We shouldn't equate the two concepts: the syntax of a formal language, and a formal grammar of a formal language, should we?

    Note that a formal language can have several formal grammars that all generate the language. When a formal language has multiple different formal grammars that generate it, is the syntax different for different grammar?

    Also a formal language may not have a formal grammar that can generate it, and still syntax should make sense to such a formal language?
2. For **a non-formal language** $L'$ over an alphabet $\Sigma$,

* What are the definitions of **its syntax** and **its semantics**, ideally mathematically?
    * When defining **its syntax**, how do you distinguish what pertains to the formal part of the language, and what is not?
    * Can **its semantics** be defined as a mapping $L' \to S$ where $S$ is some other set?
    * Maybe, for example, when $L'$ is a programming language?
    * Maybe, for example, when $L'$ is a natural language, such as English?

Thanks and regards!

# Answer
To beging with, the expression "formal language" may refer to formally defined sets of string as considered in the theory of automata and formal languages. I shall write that "Formal Language" with capital first letters. But "formal language" may also refer to some kind of language that is intended for expressing meaning, but is precisely defined mathematically. I shall rather call it formally defined language.

A first remark is that formally defined languages are similar to natural languages (vernacular), in the sense that both are used to convey meaning through representations of that meaning.

This is the fundamental issue. We have to convey meaning, to others, or to ourselves (when we take notes). Meaning can concern all sorts of things, some finite, some infinite, possibly about strange domains of human imaginations, such as real numbers, or the set of all sets. But we can always do that only through representation. The representation may be a linear sequence of symbols. It may also be a spatially organized collection of symbols. It may be drawings, or data structures in a computer, or sound stream, or gestures. It is physical.

To answer the question in a nutshell, and in a very general way: **the organisation of the physical representation of discourse is syntax, while semantics is the meaning conveyed, and the way it is derived into, or from, the representation.**

A major characteristic of syntax is that **syntactic representations are finite**: they convey a finite amount of information. This is true of pictures that can de digitized with finite precision to convey what they are supposed to convey, But the best example is one of the most common form of representation: the written text. If one takes all the symbols used for writing as digits in a proper base, any written text may be read an integer number, which is a finite object. This does not prevent the discourse from being about infinite objects, or whatever else, including ghosts, leprechauns, the Zeta function, the turtle that carries the planet on its back and the last Sunday before the Big-Bang. And, this does not forbid having an infinite number of representations, of sentences of the language.

But **how is syntax connected to semantics?** How do we associate a meaning with physical representation. The most basic way is to associate a specific meaning to specific representations, and learn these associations. This is basically how ideographic writing gets started. But it has limitation: you can define only a finite number of meanings in this way. An important aspect of language is to be able to handle unbounded number of meaning by associating in an organized way the representation of elementary meanings.

So syntax is not just a collection of elementary representations, but also a collection of rules to associate them to make more complex representations. Elementary representations correspond to elementary meanings, and rules associating them indicate how the simpler meanings can be composed to make more complex meanings.

**A simple example** is the way formally defined languages are specified in mathematics (I am simplifying somewhat, skipping over some technical issues, parsing technology for example). The syntax is defined as a set of string over an alphabet. This set is often defined by a context-free grammar. that provides rules to create strings on the alphabet. The rules also associate strctures to strings: the parse-trees. The definition of semantics associate a value (of whatever domain) to the elements of the alphabet, and associate operations on these values to the rules of the grammar. This define a homomorphism from the set of string in the context-free syntax to the set of values in the semantic domain. (Note that, sometimes, the syntax is directly defined as a set of trees.)

So we have an infinite set (the syntax Formal Language) of finite representations (string or sentences of the formal language) which has a finite definition/description (the Context-Free grammar). The semantics is defined by specifying a domain of values, and both the domain and the values in it may be finite or infinite entities. For example a mathematical text, though finite, can talk about real numbers which are a continuously infinite set of infinite entities (in the sens that most reals do not have a finite description). Furthermore, the mapping is finitely defined, by associating a function with each grammar rule. A rule composes subpart of the text into a larger text, and the associated function composes the meaning of these subparts into a meaning for the larger text.

Not all kinds of Formal Languages may be appropriate for syntax definition. They must provide some structure to the language strings that can be used to define the semantics mapping. Besides context-free languages and grammars, there are many other kinds of Formal Languages and Formal Language Definitions that can provide structure for syntax strings (tree adjoining grammars for example). They are mostly used in computational linguistics for natural language. Other mechanisms, such as attributes or features on grammar symbols, can be added both to specify the strings of the languages or the semantics mapping (but it may be disputed whether they should be considered syntax or semantics).

However, as written earlier, syntax need not be composed of strings of symbols. Other structured representations can be considered, such as graphs, or sound stream. An interesting example is abstract syntax trees that can represent programs of a programming language as tree structures. Some programming systems and development environments actually consider the abstract syntax tree (AST) as the primary representation of programs, and provide tools to create programs represented directly as AST, possibly without ever producing a string representation in some cases. The language Lisp was probably the first to do that. This is also very frequent in proof systems and other symbolic computation systems that manipulate mathematical formulae, which remain represented by tree structures, or even other data types.

This shows that different representation systems, different syntaxes, may be used to represent the same semantic structures. Actually, when these representations can easily be translated into each other, while preserving semantic meaning, they are often considered the same language. In other words, **the same language may have multiple syntactic representations**, including multiple string syntaxes. But the semantics preserving intertranslatability shows that these different representations are structurally similar. Another obvious example is natural language, that can exist as text or as speech.

Conversely, given a syntax, it is possible to combine it with different semantic interpretations, i.e. different semantic mappings.
> 5 votes

# Answer
For what I know, people from formal languages, logic and natural languages may have slightly different ideas about these notions. That is why (at least in the past) the wikipedia page for formal languages has been terribly messy.

Starting from the bottom: Raphael is right. Syntax is the strings itself. The task of formal languages is to research methods to describe the syntax of languages. This can indeed be grammars, but also machines, logical or algebraic methods. The power of the Chomsky Hierarchy is that several levels of grammar and automata descriptions match (e.g., context-free grammar vs. pushdown automata). That is extremely important because we want to be able to construct a string matching the syntax (writing a program) but also we want to be able to check whether it is correct (parsing and compiling).

Grammars (at least the context-free ones) are important because they have a recursive way of specifying syntax. Using that tool we explicitly or implicitly assign a meaning to strings generated by some parts of the grammar. That is very clear when applied in defining programming languages and natural languages. But then, there is no clear division between syntax and semantics anymore: the derivation tree of the string assigns meaning to parts of the string and their relations. I think that is called "deep structure".

So in that respect, a different grammar implies a different structure, so a different meaning. But that is not completely true. There are grammatical tricks to obtain a variant of a grammar to improve parsing (change "leftmost" into "rightmost") but the overal intended meaning must not change.

(More complicated grammars in my feeling are more like machines: they have a computational aspect, but that aside.)

Semantics is indeed a mapping from strings in the language into some domain. For natural languages that might be the intended "meaning" of a word, but also attributes like male/female, singular/plural (which are not always clear from the isolated syntax, but may be derived from context). For programming languages the semantics may be specified the input/output function of the intended construction, or how the variables are changed. Specifying programming language semantics is a large research area: wikipedia lists already three big major approaches, denotational, operational and axiomatic.
> 4 votes

---
Tags: formal-languages, programming-languages, natural-language-processing
---


title: What string operations are basic

text:
# Question
Title: What string operations are basic
What string operations are basic in the sense that the other string operations can be represented in terms of them? Here is a list of string operations off the top of my head (not necessarily a complete list, and your addition is welcome):

* reversal of a string
* concatenation of two strings
* repetition of a string a finite number of times
* search/match a string inside another string
* match and replace a string with another string inside a string
* split a string, at some specified positions, or according to matching result of another string
* taking a substring out of a string, according to specified positions (including taking prefix, or suffix), or according to matching result of another string
* ...

# Answer
There are many "complete bases" for operations on strings. One is based on the representation $$ \Sigma^\* = \epsilon + \Sigma \Sigma^\*. $$ In words, a string is either empty or is composed of a character and a string. In order to use this representation, we need the following functions:

* `nil` – the empty string
* `cons(x,s)` – the string consisting of the character `x` followed by the string `s`
* `null(s)` – true if `s` is empty
* `car(s)` – returns the first character of a non-empty string
* `cdr(s)` – returns the string resulting from removing the first character of a non-empty string

The terminology is from Lisp; `cdr` is read *could-er* or *cudder*.

Another basis considers strings as arrays. There is a standard basis for *reading* strings:

* `len(s)` – the length of `s`
* `s[i]` – the character at position `i`

For *writing* strings there are several options. In the immutable case, one choice is:

* `""` – the empty string
* `str(x)` – the string consisting of the character `x`
* `cat(s1,s2)` – the string resulting from concatenating `s1` and `s2`

If strings are allowed to be mutable, we can add an operation `s[i] = x`, changing the character at position `i` to be `x`.

One can think of many other bases. Some will be more efficient than others. It all depends on what exactly you are trying to capture, what your goal is.
> 6 votes

---
Tags: strings
---


# Question
Title: Why aren't there computers with a base different than 2?
Wouldn't non-digital computers, those that use a base higher than 2, be faster and more efficient? Especially with Moore's law reaching its limit, wouldn't circuits that have three, four or five states have advantages? Are there computers like that?

# Answer
As mentioned in this thread here, this is more due to the electronics of how computers work. It's a lot easier to create an on-off switch then it is an on-off-middle switch. If you're really curious about this, I'd recommend reading about how a computer works at the electronic level, as just doing this on-off switch took a lot of time for people to make properly.

That being said, there are computers coming that work with more than one state, mainly in the form of quantum computers. They can have an on and off state, as well as a "both" state if I'm not mistaken. There are of course advantages such as potential speed boosts from computers like this (though mostly from the way they work physics wise), but then there are also physical limitations imposed as well, such as the fact that they need to be kept incredibly cold to work properly from what has been experimented with so far. Quantum computers are the "main focus" of how to solve the issue of Moore's Law currently though.

But long story short, yes, computers that "use a base higher than 2" could be faster and more effecient, and there are computers like that, but they aren't ready for the mass populations of the world to use yet.
> 0 votes

---
Tags: computer-architecture
---


# Question
Title: What are the tradeoffs in compiler development effort related to CISC vs. RISC?
What advantages and disadvantages does a CISC instruction set have relative to a RISC instruction set with respect to the ease of developing a functioning compiler and the ease of developing a highly optimizing compiler?

# Answer
> 4 votes
CISC vs. RISC is just the wrong distinction. There are some instruction set design decisions that matter to the compiler writer and others that don't, but this simply isn't one of them.

Variable instruction length vs. fixed instruction length pretty much doesn't matter. Writing an assembler for variable instruction length requires you to do a little more bookkeeping, but once its done you never have to worry about it again.

You either want a lot of general-purpose registers or just one (e.g. an accumulator). Register allocation is hard. So hard it is difficult to even figure out the input parameters you are trying to optimize over (you'd like to minimize the number of spills at runtime, but you usually don't know how often any instruction is going to execute at runtime.) If you have only one register then where you have to spill is pretty obvious, and if you have more registers than you need then a greedy heuristic will get you something pretty close to optimal. When you have only half as many or a third as many registers as you need then good heuristics start to matter a lot.

Registers that are special-purpose (used implicitly in a few instructions) are fine, and registers that are general-purpose (can be used for different things in lots of different instructions) are fine, but trying to make a special-purpose register *also* general purpose is hard for the compiler. For example the MIPS architecture's `jump-and-link` instruction uses `R31` as the implicit place to store the return address. `R31` can also be used as a general purpose register, but the compiler has to "special case" it, so that's usually an optimization that takes a few years to get into the compiler.

Having more than one way to do the same thing is generally not helpful to the compiler writer. The internal representation of the compiler is usually a graph where the nodes correspond to operations and the edges correspond to operands. If there are multiple ways to do something (for example, lots of different addressing modes) then this becomes a graph tiling problem, which is hard. The result is that most compiler writers just ignore any addressing modes beyond the simple ones. Given the way modern microarchitectures work the main cost of not using the more complex addressing modes is that the instruction sequence takes up more space than it would in the optimal case. There's a classic story from the 1980s about the VAX. If I remember correctly, the VAX had a special `call` instruction that would also push arguments onto the stack. It turned out that the longer instruction sequence that individually pushed the arguments and then did the call separately was faster.

Large constants are a pain, so this is a place where fixed-length instructions hurts rather than helps. Sparc had something like 12 bits for constants, MIPS has 16, which is better (because then you can construct any 32-bit constant with at most two instructions.) The larger the available constant fields are the less likely it is that you have to construct multi-instruction constant construction sequences. (This is even more painful for PC-relative jumps and branches where *usually* you can fit a relative offset into the constant field, but sometimes not, in which case you need to save the PC in a register and manually add and subtract the appropriate constant. Ick.)

Alignment can be an issue sometimes. For example: some early SIMD instruction sets required that source memory operands be aligned at cache-line boundaries, which is almost impossible for the compiler to guarantee without inserting a bunch of extra code. To be useful a SIMD instruction set needs to allow cache-line-unaligned loads, at least (aligning stores is easier when the loads can be unaligned, so that's less important.)

---
Tags: compilers
---


title: Determining Big O

text:
# Question
Title: Determining Big O
```
    i<--2
    while (i<n)
      someWork (...)
      i <-- power (i,2)
    done

```

> Given that someWork(...) is an O(n) algorithm, what is the worst case time complexity?

I've found this question answered on this site with the solution of O(n log n), however I don't quite understand why. I know that the power function has O(log n), but I don't understand why the overall Big O of the loop becomes O(n log n) instead of just O(n). Can someone please explain this to me?

# Answer
> 1 votes
You're missing a very crucial component of Big-Oh analysis. That question is: given some number `n` and some code `p` how does the **MAXIMUM** runtime of `p(n)` differ with respect to time per each `n` -- that is, what are the bounds of `p(n)` with respect to `n`. When code tracing, create a tally.

Here, we see that `i` is initialized to 2. Then the code enters into a while loop. Then, while `i<n` we perform some work `n` number of times, since we know that `someWork(...)` has a maximum time complexity of `n` -- that is, linear time. We add `n` to our tally.

The next line of code is `i` gets initialized to `i` being raised to the power of `2`. This variable, `i` directly impacts the runtime of the loop, since i with respect to `n` governs the condition upon entering and exiting the loop. We now know that we will perform the loop `log(n)` times.

Putting it all together, we know that since `someWork(...)` takes linear time (`n`) and that we will perform `someWork(...)` log(n) times, we can compute the tally for the big-oh analysis of the function as `n*log(n)`

Does this make more sense now?

# Answer
> 1 votes
The loop runs `O(log(n))` times since it runs until `i > n` and each iteration `i := i^2`.

Assuming `someWork()` takes `O(n)` the total run time will be `O(nlogn)` since you're performing a task that take `O(n)`, `O(logn)` times (loop).

---
Tags: asymptotics
---


# Question
Title: Smallest NFA accepting concatenations of two words of the length $k$ which are different at all positions
Let $k\in \mathbb N$

I'm looking for a small NFA build for the language of concatenation of two words of the length $k$ which are index-wise different, i.e. $$L\_k=\\{u\cdot v \in \Sigma^\* : |u|=|v|=k\wedge \forall i, u\_i\neq v\_i\\}$$

Notice that since $k$ is fixed, $|L\_k|=(|\Sigma|\cdot(|\Sigma|-1))^k$, and is regular as a finite language.

$%$

The trivial DFA for the language contains $k$$|\Sigma| \choose k$$+1$ states and just "remembers" which letters it have seen during the first $k$ letters, however if $k=o(|\Sigma|)$, we can create a significantly smaller NFA.

$%$

A "simple" NFA for it would be of size $O^\*(2^{2k})$ (more precisely, $O(k^2 \log |\Sigma| 2^{2k+O(\log^2 k)})$ ):

$%$

1. Take a $(|\Sigma|,2k)$-universal set (i.e. a set of vectors $\mathcal V\subseteq \\{0,1\\}^{|\Sigma|}$ such that for every vector $u\in \\{0,1\\}^2k$ and a $2k$ indices, there exists a vector $v\in \mathcal V$ such that $v\_{|I}=u$, i.e. if we look only at these $k$ indices in $v$ we find $u$). Such families of size $O^\*(2^{2k})$ are known.

We think of each vector $v$ as a function $\Sigma\to \\{0,1\\}$, where $v(\sigma\_i)=1⟺v\_i=1$.

$%$

1. Create an NFA as follows:

1. From the starting state $q\_0$ create an $\epsilon$-transition to a new state for any $v\in \mathcal V$. Denote this state by $q\_v$.
    2. From each $q\_v$ build a path of states which accepts all words whose first $k$ letters are mapped by $v$ to 0, and the later $k$ letters are mapped by $v$ to 1.

$%$

Basically, the idea is that the universal set allowes us to partition the letters which are allowed to appear in the first $k$ symbols from the rest, and we get every word in the language since there has to be a corresponding vector $v\in \mathcal V$ which partitions it right.

So the questions are:

> **What is the size of the smallest NFA for $L$?**
>
> **Is this construction optimal?**
>
> **What lower bound we can prove for such automaton size?**

# Answer
> 4 votes
Update: this doesn't answer the question that the original poster was looking for, and doesn't help with the general case where $|\Sigma|\>2$, so the question remains open.

---

Here is a simpler construction, showing that in the case where $\Sigma=\\{0,1\\}$, $O(k \cdot 2^{2k})$ states suffice, and in fact you can recognize the language with a *DFA* with that many states.

Let's start by looking at the complement language:

$$\overline{L\_k} = \\{u \cdot v \in \Sigma^\* : |u| = |v| = k, \exists i . u\_i = v\_i\\}.$$

Notice that this can be recognized by a NFA with $2k^2 |\Sigma|$ states. The NFA first guesses $i$ and a symbol $x$, then accepts all strings $u \cdot v$ where $u\_i = v\_i = x$.

Convert this to a DFA using the standard subset construction. We get a DFA with $\le 2^{|\Sigma| k + 1} k$ states. Now we can compute its complement, which is another DFA with the same number of states that recognizes $L\_k$. Since it is a DFA, it is in turn automatically a NFA, too.

This beats your construction for the case where $|\Sigma|=2$, but otherwise leads a NFA that's larger than your scheme. However, I thought it might be of interest, both because it is so simple, and because it in fact provides a DFA (not just a NFA) to recognize your language $L\_k$.

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


# Question
Title: Finding independent sets so that all nodes are hit frequently
I have a problem, and I appreciate it if you could share your thoughts.

Assume that I have a graph. Assume that I have $k$ iterations. I want to find only *one* independent set (IS) in the graph in each iteration. Then, I will increase a counter for those vertices that are in the selected IS. Initially, the counter for all vertices of the graph are zero.

With an integer programming formulation, we can choose one independent set (**provided that we know the set of all ISs**) in every iteration, so that the counter of each vertex $i$ in the graph is at least $r\_i$ over $k$ iterations (clearly $r\_i \leq k$)? In other words, we can make a plan, with IP, so that each vertex $i$ has been selected $r\_i$ times over $k$ iterations. Also, with simple modification, minimum value for $k$ can be included in IP formulation. I aim at finding the minimum $k$ by which all $r\_i$'s are satisfied.

Now the main concern is that the above formulation need the set of all ISs as an input. Finding this set, however, is an NP-hard problem. So, I was wondering if there there is any way to bypass the need for having all ISs? For sure, many heuristic algorithms can be developed (one example is proposed in comments below). However, I am interested to find an algorithm for which I can say something analytically, e.g. convergence proof, optimality gap, etc.

# Answer
> 4 votes
## Approach 1: Use ILP

If you want an algorithm that might work in practice as long as the graph is not too large, one approach is to formulate this as an integer linear problem.

That's pretty straightforward in this case. We'll have $k|V|$ integer variables. In particular, $x\_{v,i}$ will be $1$ if the vertex $v$ is included in the independent set in the $i$th iteration and $0$ otherwise.

First, let's encode the constraint that the $x\_{\cdot,i}$ have to encode an independent set in each iteration. We get $0 \le x\_{v,i} \le 1$ and

$$x\_{v,i} + x\_{w,i} \le 1 \quad \forall (v,w) \in E.$$

Next, note that $x\_{v,1} + x\_{v,2} + \dots + x\_{v,k}$ counts how many times each vertex is covered across the $k$ iterations. We want this to be at least $r\_v$, so we get the constraint

$$x\_{v,1} + x\_{v,2} + \dots + x\_{v,k} \ge r\_v \quad \forall v \in V.$$

Now throw an integer linear solver at the problem, and hope that it finds a solution. The worst-case running time is exponential, but integer linear solvers sometimes work a lot better than you'd expect, so as long as the graph is not too large, it might just work.

If you want to find the smallest $k$ such that this can be solved, use binary search or linear search on $k$.

You can also formulate a similar version that works using SAT, and then throw a SAT solver at it. It's a little more complex because you'll need to encode the constraint $x\_{v,1} + x\_{v,2} + \dots + x\_{v,k} \ge r\_v$ in SAT, but it can be done (e.g., by building a circuit for a small adder and then translating it to SAT using the Tseitin transform).

## Approach #2: A greedy heuristic

Here is an alternative approach, that might work even on larger graphs. It won't find the optimal solution, but it might find a solution that is not too much worse than the optimal solution.

The problem reminds me of a set cover problem: in each iteration you select one set, and you want the union of the sets to cover the universe. One natural approach to set-cover-like problems is to try to apply the greedy algorithm for set cover: in each iteration, choose an independent set that gives you as much progress as possible.

Let me start by assuming $r\_v=1$ for all vertices $v$, for simplicity. Then you could use the following algorithm:

1. Initially all vertices are uncovered. Set $i=1$.
2. Find an independent set $I$ that covers as many of the uncovered vertices as possible. Choose that one, and output it as the independent set $I$ as the one to use in the $i$th iteration. Increment $i$ and go back to step 2.

You can now plug in any algorithm you like for finding independent sets, including a heuristic or approximation algorithm. There's lots written on that subject so you might be able to re-purpose any of a number of different algorithms.

What about the general case where the $r\_v$'s are arbitrary? Well, in any given iteration, you can evaluate each candidate independent set by how much incremental coverage it adds, where now the coverage is given by the sum of the counters on all of the vertices. So, in each iteration, choose the independent set with the largest incremental coverage that you can find. This might give a reasonable approximation algorithm for your initial problem.

---
Tags: algorithms, graphs
---


title: Does a logical system have semantics?

text:
# Question
Title: Does a logical system have semantics?
From Wikipedia:

> A logical system or, for short, logic, is a formal system together with **a form of semantics, usually in the form of model-theoretic interpretation, which assigns truth values to sentences of the formal language, that is, formulae that contain no free variables**. A logic is sound if all sentences that can be derived are true in the interpretation, and complete if, conversely, all true sentences can be derived.

Does a logical system have semantics?

Does the assignment of truth values to sentences of the formal language count as the semantics of a logical system? I feel it provide little interpretation of what the sentences of the formal languages mean.

# Answer
Semantics of a logic describe how to compute the truth value of an expression, possibly given some interpretation. For example, one rule would say that an expression $\varphi \land \psi$ is true iff both $\varphi$ and $\psi$ are true, and another would say that $\forall x \varphi(x)$ is true if for all $x$ in the domain of discourse $D$ (which forms part of the interpretation).

Sometimes the semantics are not obvious – for example, there are different semantics for modal logic. Sometimes we are interested in non-standard semantics, such as the semantics of bounded arithmetic described in Forcing with random variables.
> 8 votes

# Answer
The answer to your literal question, "Does a logical system have semantics?" is "Obviously, yes. The definition you quoted says so!" So I figure that isn't what you're actually asking.

I think the root of your misunderstanding is the word "formal". In this context, it doesn't mean "rigorous", the opposite of "hand-wavy"; it means "depending on form". That is, the truth of a sentence of, say, propositional logic depends only on the form (or shape, if you like) of the sentence. $P\wedge Q$ is true if, and only if the propositions $P$ and $Q$ are both true. It doesn't depend on what, if anything, those propositions represent in the real world: if $P$ is any true thing and $Q$ is any true thing, then $P\wedge Q$ is true.

Consider the formula $\text{I am a human} \wedge \text{My mother is a giraffe}$. Reasoning informally (i.e., not based on the form of the sentence), one would say that it is impossible for a human to have a giraffe as a mother so the sentence must be false. Reasoning formally, one would determine whether the propositions $\text{I am a human}$ and $\text{My mother is a giraffe}$ are true individually, by looking at their interpretation, which assigns each of them a truth value. Then, one would combine those truth values using the semantics of the $\wedge$ operator.

But let's go back to the informal claim that the human/giraffe sentence *must be false*. One property that "reasonable" logics have is that renaming variables makes no difference, as long as you don't make two different variables have the same name. You're familiar with this from programming languages and mathematics: if you take a program and rename all the variables, the program does exactly the same thing; in $\lambda$-calculus, this is called $\alpha$-equivalence. So, since propositional logic is eminently reasonable, I could rename the second proposition in that sentence to be $\text{My mother is a human}$. Formally, the sentence is unchanged but now, reasoning informally, one would say that the sentence must be true! Taking things a little farther, one could even make the proposition $\text{I am a human}$ stand for the real-world fact "It is sunny today". That would be a stupid thing to do but, formally ("shape-wise"), it's perfectly valid. Just like it's perfectly valid but stupid to write a program that says something like

```
colour = "Hello, world!";
message = green;
setColour (message);
print (colour);

```

or to write "Let $v$ be a graph containing a vertex $G$."

**Summary / tl;dr.** Yes, logics do have semantics. The semantics of a logic tells you how to determine whether a formula is true or false, based only on the syntactic structure of the formula and some interpretation that states the truth values of the most simple formulas (propositions in propositional logic, atomic formulas in first-order logic, and so on). That's all the semantics of the logic does: in particular, it has nothing to do with assigning "real world" meaning to the variables and constructs in the formula. Semantics depends only on the form ("shape") of the formula; in particular, it doesn't depend on the names chosen for the variables. That's why the systems are called *form*al.
> 7 votes

# Answer
Unless I've totally misunderstood you, there seem to be two meanings of semantics here:

(1) Semantics in formal logic, which is precisely what the definition you give declares it to be, ie correspondence between values and propositions of the system.

(2) Semantics in semiotics, ie 'meaning' in the sense of correspondence between natural language symbols and their denotata.

Of course, while similar in some respects, the two are quite different -- and this seems to be what is concerning you -- ie, how we make the 'link' between our formal system and our natural language interpretation of it, or making correspondences between propositions in a logical system and states of 'the world'. That is a deep question in semiotics (and even philosophy of science), and particular to neither logical nor linguistic semantics.
> 2 votes

---
Tags: formal-languages, logic, semantics
---


title: recursive lambda expressions

text:
# Question
Title: recursive lambda expressions
From http://www.seas.gwu.edu/~rhyspj/spring09cs145/lab8/lab82.html

> The lambda operator does not bind every occurrence of its variable because "shadowing" can occur. A variable is bound by its nearest enclosing lambda.
>
> In $(\lambda (x) ((y\\,\\, x) (\lambda (x) (x\\,\\, y))))$, the $x$ in $(y\\,\\, x)$ is bound by the outermost lambda, whereas the $x$ in $(x\\,\\, y)$ is bound by the inner lambda. In this example, both occurrences of $y$ are free.

How shall I understand the lambda expression $(\lambda (x) ((y\\,\\, x) (\lambda (x) (x\\,\\, y))))$?

1. I wonder if the $x$ in $(y\\,\\, x)$ and the $x$ in $(x\\,\\, y)$ are the same or different variables?

If I rename one of them, will the renamed version be the same as $(\lambda (x) ((y\\,\\, x) (\lambda (x) (x\\,\\, y))))$? E.g.

* Is $(\lambda (x) ((y\\,\\, x) (\lambda (z) (z\\,\\, y))))$ the same as $(\lambda (x) ((y\\,\\, x) (\lambda (x) (x\\,\\, y))))$?
    * Is $(\lambda (z) ((y\\,\\, z) (\lambda (x) (x\\,\\, y))))$ the same as $(\lambda (x) ((y\\,\\, x) (\lambda (x) (x\\,\\, y))))$?
2. Do the two occurrences of $y$ mean the same variable?

# Answer
1. Informally speaking the two *x*'s are indeed different variables (*technically* speaking, they are the same variables but bound by different abstractors).

As for your two inquiries regarding equivalences: in the strictest sense possible, they are not syntactically equivalent ($M \not\equiv N$). However, they *are* what is called *equivalent modulo alpha* ($M \equiv\_\alpha N$). This basically means that one can be transformed into the other through $\alpha$-conversion (which leaves the behaviour of the term unchanged). The result is that the names of bound variables become arbitrary - as they should be.

Note that most equivalences in lambda calculus are stated modulo $\alpha$, and most lambda logicians seem to regard the formulation and application of the rule as a tedious formality. Once they have specified the $\alpha$-rule (if they even care to do so in the first place), they tend to adopt the following convention: 'from now on, when we say $M$ and $N$ are equivalent ($M \equiv N$), we just mean that they are equivalent modulo alpha ($M \equiv\_\alpha N$), unless stated otherwise'. So in most contexts, you can simply say they are 'the same', but I think you should be aware of the details behind it.
2. Yes. If $y$ were to be substituted for some $z$ in that term, then all occurrences of $y$ will be replaced by $z$.

This is perhaps a useful free resource that covers some of the basics a little more rigorously: http://www.cse.chalmers.se/research/group/logic/TypesSS05/Extra/geuvers.pdf.
> 4 votes

---
Tags: terminology, lambda-calculus
---


# Question
Title: The proportion of halting programs vs non-halting programs, of decidable programs vs undecidable languages
Can the following two statistics be bounded:

1. the proportion of halting programs vs non-halting programs
2. the proportion of decidable vs undecidable languages

For example, can we say that one class is much larger than the other, almost all problems are such and such, or both are similar in size?

By Chaitin's argument on the Omega number, we know that the halting probability is undecidable, so it is difficult to obtain an exact statistic on the number (if not impossible). However, Omega numbers have been computed for specific universal machines for prefix-free programs using probability measures decreasing in length (cf. Calude et al.).

So are there known valid statements about these proportions? My intuition (following the argument of the scarcity of life in the universe) would lead me to believe that there are much more undecidable languages than decidable ones. But it is only an intuition that is not backed.

# Answer
EDIT: There are countably many recursive languages, and uncountably many non-recursive languages, so there are way more non-recursive languages.

There are countably infinitely many halting programs and non-halting programs alike. I can't think of an interesting structure you can put on the set of programs that includes a concept of "proportion" where you end up being able to say anything interesting about the proportion of halting programs, unfortunately.

For instance, one natural structure to put on the set of programs is to give them a computable well-ordering. One can make sense of questions about how big an infinite co-infinite subset of a countable set is if that countable set is well-ordered. For example, the notion of asymptotic density can give credence to the intuition that there are more non-square integers than there are integers. It basically says that the percentage of numbers that are not square tends towards 100% as you consider larger and larger finite initial segments of the naturals. Asymptotic density makes sense for subsets of the naturals which have a canonical (computable) well-ordering. The same cannot be said, however, for subsets of the set of all programs. Since there is no canonical enumeration of the programs, there's no canonical answer to the question of proportion of halting programs in terms of asymptotic density.

**Proposition**: If $0 \leq \alpha \leq \beta \leq 1$ where $\alpha, \beta$ are computable real numbers, then there is an effective enumeration of the set of all programs such that the lower asymptotic density of the halting programs is $\alpha$, and the upper asymptotic density is $\beta$.

**Proof Sketch**: Let $\pi\_1, \pi\_2, \dots$ be a computable enumeration of all programs. Let $\eta\_n$ be the program:

```
print n
exit

```

Let $\nu\_n$ be the program:

```
print n
loop {}

```

Note that $\eta\_1, \eta\_2, \dots$ is an effective enumeration of (some, obviously not all) programs that halt, and $\nu\_1, \nu\_2, \dots$ is an effective enumeration of programs that don't halt.

Let $0.a\_1a\_2\dots$ be the decimal expansion of $\alpha$, and $0.b\_1b\_2\dots$ the expansion of $\beta$. Note that since $\alpha, \beta$ are computable, the sequences $a\_1, a\_2, \dots$ and $b\_1, b\_2, \dots$ are also computable.

Our goal is to build an effective enumeration of all the programs such that the lower and upper asymptotic densities of the halting programs are $\alpha$ and $\beta$ respectively. We're going to build this enumeration in stages. Each stage is going to have 3 parts:

*At stage $n$*:

1. (Sketch) Select programs from the front of the $\eta$ and $\nu$ lists that aren't already in our partially-constructed enumeration so far, and append them to the partial enumeration. In this selection of programs, the proportion of $\eta$ (halting) programs chosen should be $0.a\_1a\_2\dots a\_n$. Select **a lot** of programs so that the proportion in the overall list (what had already been construct plus what has just been appended) is pretty close to $0.a\_1a\_2\dots a\_n$ as well. If we do this carefully at each stage $n$, we can assure ourselves that the lower density of the halting programs will be $\alpha$.
2. (Sketch) Do the same thing, this time so that the proportion of halting programs in the selection is $0.b\_1b\_2\dots b\_n$. Again, select **a lot** so that after appending these programs to the list so far, the overall proportion is close to $0.b\_1b\_2\dots b\_n$. If we do this carefully, we assure ourselves that the upper density of the halting programs will be $\beta$.
3. If $\pi\_n$ isn't already in the list, append it to the end. This ensures us that the enumeration we're building really does enumerate **all** the programs.
> 3 votes

---
Tags: undecidability, halting-problem
---


# Question
Title: Ordering of conditions in multi-way conditional constructs
Most programming languages provide multi-way conditional constructs (like `cond` in Lisp, guards in Haskell, etc) that allow one to define program behavior according to different conditions. But most of them also implies a default top-down ordering: the next condition is checked only when all preceding conditions are unsatisfied. I wonder if there is any work on conditional constructs that does not follow this convention but rather automatically sort the conditions according to some order. I can foresee how hard it is to get conditions independent. Maybe it is not feasible anyway?

# Answer
On what basis you want to sort out conditions conditions are not specific. If they are specific then you may sort out the conditions to not follow top down approach.

And conditions are the only thing that decide which condition next to be tested. That is they handle the flow of your code and one condition is dependent on other.
> -1 votes

---
Tags: programming-languages
---


# Question
Title: The number of different regular languages
Given an alphabet $\Sigma = \\{ a,b \\}$, how many different regular languages are there that can be accepted by an $n$-state non-deterministic finite automaton?

As an example, let us consider $n=3$. We then have $2^{18}$ different transition configurations and $2^3$ different start- and end state configurations, so we have an upper bound of $2^{24}$ different languages.
However, many of these will be equivalent and since testing for that is PSPACE-Complete, it is probably unfeasible to test each setting.
Are there other means or combinatorial arguments that bound the number of different languages accepted by a given resource?

# Answer
> 14 votes
This is a summary of the paper *On the Number of Distinct Languages Accepted by Finite Automata with n States*. The paper provides relatively easy, yet far from tight, lower and upper bounds on the number of distinct languages accepted by NFA's. Their discussion on the number of distinct DFA's is very insightful, so I will also include that part.

The paper starts with a quite rigorous asymptotic for the number of distinct languages accepted by a DFA with $n$ states over a unary alphabet. This is done by observing under which conditions a given $n$-state unary DFA is minimal. In such cases the description of the automaton may be mapped (bijectively) to a *primitive word*, and the enumeration of such words is well-known and done with the help of the *Möbius function*. Using that result, bounds for non-unary alphabets, both in the DFA and in the NFA case, are proven.

Let's go into more detail. For a $k$-letter alphabet, define \begin{align\*} f\_k(n) &= \text{the number of pairwise non-isomorphic minimal DFA's with } n \text{ states}\\ g\_k(n) &= \text{the number of distinct languages accepted by DFA's with } n \text{ states}\\ G\_k(n) &= \text{the number of distinct languages accepted by NFA's with } n \text{ states} \end{align\*} Note that $ g\_k(n) = \sum\_{i=1}^n f\_k(i)$. We start with $f\_1(k) $ and $g\_1(k)$.

## Enumeration of Unary DFA's

A unary DFA $M = (Q, \\{a\\},\delta, q\_0,F) $ with states $q\_0,\dots, q\_{n-1}$ is minimal iff

1. It is connected. Thus, after renaming, it the transition diagram consists of a loop and a tail, i.e. $\delta(q\_i,a) = q\_{i+1}$ and $\delta(q\_{n-1},a)=q\_j$ for some $j \leq n-1$.
2. The loop is minimal.
3. If $j \neq 0$, then either $q\_{j-1} \in F $ and $q\_{n-1} \notin F$ or $q\_{j-1} \notin F $ and $q\_{n-1} \in F$.

The loop $q\_j,\dots, q\_{n-1}$ is minimal iff the word $a\_j \cdots a\_{n-1}$ defined by \begin{equation\*} a\_i = \begin{cases} 1 \quad \text{if } q \in F, \\ 0 \quad \text{if } q \notin F \end{cases} \end{equation\*} is *primitive*, which means it cannot be written in the form $x^k$ for some word $x$ and some integer $k \ge 2$.
The number $\psi\_k(n)$ of primitive words of length $n$ over $k$-letter alphabets is known, see e.g. Lothaire,*Combinatorics on Words*. We have \begin{equation\*} \psi\_k(n) = \sum\_{d | n} \mu(d) k^{n/d} \end{equation\*} where $\mu(n)$ is the *Möbius function*. With the help of $ \psi\_k(n) $ the paper proves exact formulas for $f\_1(n)$ and $g\_1(n)$ and shows that asymptotically (Theorem 5 and Corollary 6), \begin{align\*} g\_1(n) &= 2^n \left(n-\alpha+O \left(n 2^{-n/2} \right)\right) \\ f\_1(n) &= 2^{n-1}\left(n+1-\alpha+O \left(n 2^{-n/2} \right)\right). \end{align\*}

## Enumeration of DFA's

The next step is a lower bound for $f\_k(n)$. Theorem 7 states that \begin{equation\*} f\_k(n) \ge f\_1(n) n^{ (k-1)n} \sim n 2^{n-1}n^{(k-1)n}. \end{equation\*} For a set $\Delta \subset \Sigma$ of an automaton $M$, define $M\_{\Delta}$ as the restriction of $M$ to $\Delta$.
The proof works by considering the set $S\_{k,n}$ of DFA's $M$ over the $k$-letter alphabet $\\{0,1,\dots,k-1 \\}$ defined by

1. Letting $M\_{ \\{0 \\}}$ be one of the $f\_1(n) $ different unary DFA's on $n$ states, and
2. Choosing any $k-1$ functions $h\_i : Q \to Q$ for $1 \le i \< k$ and defining $\delta(q,i) = h\_i(q)$ for $1 \le i \< k$ and $q \in Q$.

The observation is then that $S\_{n,k}$ contains $f\_1(n) n^{ (k-1)n}$ different and minimal languages.

## Enumeration of NFA's

For $G\_1(n)$ one has the trivial lower bound $2^n$, since every subset $\epsilon, a,\dots, a^{n-1}$ can be accepted by some NFA with $n$ states. The lower bound is improved slightly, yet the proof is rather lengthy.
The paper *Descriptional Complexity in the unary case* by Pomerance et al shows that $G\_1(n) \le \left( \frac{c\_1 n}{\log n}\right)^n $.
Proposition 10 shows that, for $k \ge 2$ we have \begin{equation\*} n 2^{(k-1)n^2} \le G\_k(n) \le (2n-1) 2^{kn^2} +1. \end{equation\*} The proof is quite short, hence I include it verbatim (more or less). For the upper bound, note that any NFA can be specified by specifying, for each pair $(q,a)$ of state and symbol, which subset of $Q$ equals $\delta(q,a)$ (hence the factor $ 2^{kn^2}$. We may assign the final states as follows: either the initial state is final or not, and since the names of the states are unimportant, we may assume the remaining final states are $\\{1,\dots,k\\}$ for $k \in \[0..n-1\]$. Finally, if we choose no final states, we obtain the empty language.
For the lower bound the authors proceed in a similar way as in the proof for the DFA case: Define an NFA $M=(Q,\Sigma,\delta,q\_0, F)$ with $\Sigma = \\{ 0,1,\dots,k-1 \\}$, $Q=\\{ q\_0,\dots, q\_{n-1} \\}$ and $\delta$: \begin{align\*} \delta(q\_i,0) &=q\_{(i+1) \mod n} \quad \text{for } 0 \le i \<n \\ \delta(q\_i,j) &=h\_j(i) \quad \text{for } 0 \le i \<n,\\, 1 \le j \< k \end{align\*} where $h\_j: \\{ 1,\dots,n-1\\} \to 2^Q$ is any set-valued function. Finally, let $F=\\{q\_i\\}$ for any $i \in \[0..n-1\]$. There are $ 2^{(k-1)n^2} $ such functions and $n$ ways to choose the set of final states. One can then show that no two such NFA's accept the same language.

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


# Question
Title: Finding shortest path from a node to any node of a particular type
I have an un-directed, un-weighted graph G.Starting from a given node A, i want to find whether there is a path from A to a node of a certain type .There can be many nodes of that type. The problem is to find the shortest path from A to any such node, if it exists. This can be achieved by doing a breadth first search which would give the shortest distance between A and the desired node if it exists. Given that the graph can be pretty dense, what could be a better algorithm to achieve this? Both memory and time taken for the search are to be kept in mind while designing this.

If such queries could be optimized by doing some pre-processing while the graph is built, such additional hit on performance could be acceptable (not memory though).

# Answer
> 1 votes
I don't have enough rep to comment, but here are some suggestions rather than a definitive answer. These algorithms assume the graph is fixed.

Let $k$ be the number of types. The number of nodes is $n$, similarly $m$ for edges.

**Case 1:** $k$ is acceptably small.

*Strategy:* Just store the info.

Preprocessing: $\mathcal{O}(k(n + m))$, Memory: $\mathcal{O}(kn + m)$, Query Time: $\mathcal{O}(1)$

Simply store the shortest distance to any type for each node. This can be done in $\mathcal{O}(k)$ space per node. The values can be obtained by running BFS $k$ times, once for each type. Let $D\[v\]\[t\]$ be the distance from node $v$ to any node of type $t$, initialized to $\infty$.

For each type $t$, find the connected component of nodes of just that type, by BFS. During the BFS, keep a set (the "boundary" nodes) of all nodes of other types that are encountered. Now BFS using that set as a starting point, record the distance in $D\[v\]\[t\]$ for each node encountered. Runtime is $\mathcal{O}(n + m)$ for each type $t$.

*Querying*: $\mathcal{O}(1)$, just look up the value in $D$.

---

**Case 2:** $k$ is not that small. But the graph is very dense.

*Strategy*: Utilize bidirectional search after graph transform.

Preprocessing: $\mathcal{O}(n + m)$, Memory: $\mathcal{O}(n + m)$

Query Time: $\mathcal{O}(n + m)$ (but possibly better in practice, see: http://en.wikipedia.org/wiki/Bidirectional\_search)

We will be adding nodes / edges and transforming the undirected graph into a directed one.

Create $k$ supernodes, $S\[t\]$, one for each type. For edges that link different types of nodes: $e\_{u,v}$ where $type(u) \neq type(v)$, create additional edges from $v$ and $u$ directly to the supernode of the other type (directed into the supernode). Next convert all the original undirected edges into two directed edges, one in each direction.

At most, we've added $n + m$ extra links and $k \< n$ (assuming a node can belong to only one type) extra nodes, preserving the memory and time bounds. The transformation itself takes $\mathcal{O}(n + m)$ time. Essentially, the supernodes allow us to search in both directions, without affecting correctness. While we BFS from the starting node, we can also BFS in reverse from the supernode of the target type. This can be more efficient if the nodes originally had large degrees (big branching factor).

*Querying*: To find the shortest path from node $v$ to type $t$, run a bidirectional BFS from $v$ and $S\[t\]$. Depending on the graph, this could be significantly faster than just a BFS for very dense graphs, and will **not** be *asymptotically* slower.

# Answer
> 1 votes
## Reduction to standard shortest path in a weighted graph

As indicated in comments, your question is not to clear about what is constant and what changes, and when, in your problem.

So, I am proposing an answer that can meet this fuzziness.

You extend your graph with new nodes which I am calling type-nodes. There is one type-node noted $N\_t$ for each type $t$ of node you are considering.

You add edges from each node $X$ of the original graph to all type-nodes corresponding to the types the node $X$ belongs to.

Given a type $t$ and a node $A$, in order to get the shortest path from $A$ to a node of type $t$, you compute the shortest path from $A$ to $N\_t$ (or from $N\_t$ to $A$ ... :-). Then you remove the last edge on the $N\_t$ end.

There is however one glitch to worry about: no path is allowed to go through a type-node.

One way to ensure that can simply be to put a weight on edges connecting to a type node that is the same for all and has a value greater than the number of nodes in the original graph. If the weight of the minimal path found exceeds that value, it means that there is no path satisfying the query in the original graph. Of course, all other edges have unit weight.

How you find that shortest path is up to you. The literature is full with such algorithms. Just choose one that is adapted to the precise statement of your problem (which is not precise enough in the question) modified as indicated here. The same remark applies to preprocessing optimizations.

Essentially, your problem is reducible to a standard shortest path problem on a weighted graph.

**An alternative solution is to reduce to standard shortest path in a directed graph**. The idea is to keep all edges bidirectional, but use directed edges for type-nodes, either all directed towards their relevant type-nodes, or all directed away from it.

---
Tags: algorithms, graphs, data-structures, search-algorithms, shortest-path
---