# Question
Title: Which method is preferred for storing large geometric objects in a quadtree?
When placing geometric objects in a quadtree (or octree), you can place objects that are larger than a single node in a few ways:

1. Placing the object's reference in every leaf for which it is contained
2. Placing the object's reference in the deepest node for which it is fully contained
3. Both #1 and #2

For example:

In this image, you could either place the circle in all four of the leaf nodes (method #1) or in just the root node (method #2) or both (method #3).

For the purposes of querying the quadtree, which method is more commonplace and why?

# Answer
> 8 votes
Assuming you are storing a reference, not the object itself, it may make sense to do this differently depending on your application.

For instance, if you were computing collisions with this (solid) circle and the collision was occurring in the lower left hand corner, it'd be easier if you had access to all geometry in that leaf directly from that leaf (method #3) (without having to traverse the tree upward and determine inherited geometry). But, say you were just using quadtrees for drawing geometry, you'd want to use method #1, because it only makes sense to draw something in the node for which it is fully contained (it would be more difficult to figure out which portion to draw for each leaf node and where).

As for what is more commonplace, my only experience with quadtrees is with writing an n-body simulation where the geometric objects were really just points that had no area, so I can't definitively answer that.

# Answer
> 6 votes
One of the advantages of a Quadtree is that you don't have to split a node into its child nodes if all of the child nodes would contain the same information. This can save you a lot of memory and can make processing faster.

Following this principle, I think it makes more sense to store it only in the root node (method #2). It could save you a lot of memory and I think would also make processing easier. For example, if you tried to find intersections of the circle with a line that goes through three of the leaf nodes, you would either need to compute the intersection separately for each leaf node, or remember that you already intersected with this circle.

On the other hand, if you have objects in leaf nodes, it could help you eliminate false positives (objects that you have to check for intersection, because they are in the correct node, but that don't actually intersect).

So, I think both approaches have their uses and I'm not sure how to choose which one to use.

I probably wouldn't use approach #3, because I don't see any positives about it.

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


# Question
Title: Rice's theorem for non-semantic properties
Rice's theorem tell us that the only *semantic* properties of Turing Machines (i.e. the properties of the function computed by the machine) that we can decide are the two trivial properties (i.e. always true and always false).

But there are other properties of Turing Machines that are not decidable. For example, the property that there is an unreachable state in a given Turing machine is undecidable$^{\dagger}$.

Is there a similar theorem to Rice's theorem that categorizes the decidability of similar properties? I don't have a precise definition. Any known theorem that covers the example I have given would be interesting for me.

$^\dagger$ it is easy to prove that this set is undecidable using Kleene's Recursion/Fixed Point theorems.

# Answer
A general theorem that partially covers the example given is that any $\Sigma^0\_1$-hard property of the machine will be undecidable. The halting problem is $m$-reducible to the state-reachability problem, so that shows the state reducibility problem is $\Sigma^0\_1$-hard.

However, this is not an "if and only if" theorem like Rice's theorem. If every $\Sigma^0\_1$ property of the index of the Turing machine counts as a property of the machine, then there is not going to be a nice characterization, because there is not any nice characterization of which r.e. sets are decidable in terms of the index of the r.e. set.
> 16 votes

---
Tags: computability, undecidability
---


# Question
Title: Language theoretic comparison of LL and LR grammars
People often say that LR(k) parsers are more powerful than LL(k) parsers. These statements are vague most of the time; in particular, should we compare the classes for a fixed $k$ or the union over all $k$? So how is the situation really? In particular, I am interested in how LL(\*) fits in.

As far as I know, the respective sets of grammars LL and LR parsers accept are orthogonal, so let us talk about the languages generated by the respective sets of grammars. Let $LR(k)$ denote the class of languages generated by grammars that can be parsed by an $LR(k)$ parser, and similar for other classes.

I am interested in the following relations:

* $LL(k) \overset{?}{\subseteq} LR(k)$
* $\bigcup\_{i=1}^{\infty} LL(k) \overset{?}{\subseteq} \bigcup\_{i=1}^{\infty} LR(k)$
* $\bigcup\_{i=1}^{\infty} LL(k) \overset{?}{=} LL(\*)$
* $LL(\*) \overset{?}{\circ} \bigcup\_{i=1}^{\infty} LR(k)$

Some of these are probably easy; my goal is to collect a "complete" comparison. References are appreciated.

# Answer
> 69 votes
There are numerous containments known. Let $\subseteq$ denote containment and $\subset$ proper containment. Let $\times$ denote incomparability.

Let $LL = \bigcup\_k LL(k)$, $LR = \bigcup\_k LR(k)$.

## Grammar level

### For LL

* $LL(0) \subset LL(1) \subset LL(2) \subset LL(2) \subset \cdots \subset LL(k) \subset \cdots \subset LL \subset LL(\*)$
* $SLL(1) = LL(1), SLL(k) \subset LL(k), SLL(k+1) \times LL(k)$

Most of these are proven in Properties of deterministic top down grammars by Rosenkrantz and Stearns. $SLL(k+1) \times LL(k)$ is a rather trivial exercise. This presentation by Terence Parr places $LL(\*)$ on slide 13. The paper LL-regular grammars by Jarzabek and Krawczyk show $LL \subset LLR$, and their proof trivially extends to $LL \subset LL(\*)$

### For LR

* $LR(0) \subset SLR(1) \subset LALR(1) \subset LR(1)$
* $SLR(k) \subset LALR(k) \subset LR(k)$
* $SLR(1) \subset SLR(2) \subset \cdots \subset SLR(k)$
* $LALR(1) \subset LALR(2) \subset \cdots \subset LALR(k)$
* $LR(0) \subset LR(1) \subset LR(2) \subset \cdots \subset LR(k) \subset \cdots \subset LR$

These are all simple exercises.

### LL versus LR

* $LL(k) \subset LR(k)$ (Properties of deterministic top down grammars plus any left recursive grammar)
* $LL(k) \times SLR(k), LALR(k), LR(k-1)$ (simple exercise)
* $LL \subset LR$ (any left recursive grammar)
* $LL(\*) \times LR$ (left recursion versus arbitrary lookahead)

## Language level

### For LL

* $LL(0) \subset LL(1) \subset LL(2) \subset \cdots \subset LL(k) \subset \cdots \subset LL \subset LL(\*)$
* $SLL(k) = LL(k)$

Most of these are proven in Properties of deterministic top down grammars. The equivalence problem for LL- and LR-regular grammars by Nijholt makes references to papers showing $LL(k) \subset LL(\*)$. The paper LL-regular grammars by Jarzabek and Krawczyk show $LL \subset LLR$, and their proof trivially extends to $LL \subset LL(\*)$

### For LR

* $LR(0) \subset SLR(1) = LALR(1) = LR(1) = SLR(k) = LALR(k) = LR(k) = LR$

Some of these were proven by Knuth in his paper On the Translation of Languages from Left to Right in which he introduced LR(k), the rest are proven in Transforming LR(k) Grammars to LR(1), SLR(1), and (1,1) Bounded Right-Context Grammars by Mickunas et al.

### LL versus LR

* $LL \subset LR(1)$ (containment follows from the above, $\\{ a^i b^j | i \geq j \\}$ is the canonical example for strict containment)
* $LL(\*) \times LR$ (the language $\\{ a^i b^j | i \geq j \\}$ shows half the claim, and the introduction of The equivalence problem for LL- and LR-regular grammars by Nijholt makes references to papers showing the other half)
* $LR(1) = DCFL$ (see e.g. reference here).

---
Tags: formal-languages, formal-grammars, parsers, reference-question
---


# Question
Title: Clever memory management with constant time operations?
Let's consider a memory segment (whose size can grow or shrink, like a file, when needed) on which you can perform two basic memory allocation operations involving fixed size blocks:

* allocation of one block
* freeing a previously allocated block which is not used anymore.

Also, as a requirement, the memory management system is not allowed to move around currently allocated blocks: their index/address must remain unchanged.

The most naive memory management algorithm would increment a global counter (with initial value 0) and use its new value as an address for the next allocation. However this will never allow to shorten the segment when only a few allocated blocks remain.

Better approach: Keep the counter, but maintain a list of deallocated blocks (which can be done in constant time) and use it as a source for new allocations as long as it's not empty.

What next? Is there something clever that can be done, still with constraints of constant time allocation and deallocation, that would keep the memory segment as short as possible?

(A goal could be to track the currently non-allocated block with the smallest address, but it doesn't seem to be feasible in constant time…)

# Answer
> 11 votes
With fixed-size blocks, what you have described is a free list. This is a very common technique, with the following twist: the list of free blocks is stored in the free blocks themselves. In C code, it would look like this:

```
static void *alloc_ptr = START_OF_BIG_SEGMENT;
static void *free_list_head = NULL;

static void *
allocate(void)
{
    void *x;

    if (free_list_head == NULL) {
        x = alloc_ptr;
        alloc_ptr = (char *)alloc_ptr + SIZE_OF_BLOCK;
    } else {
        x = free_list_head;
        free_list_head = *(void **)free_list_head;
    }
    return x;
}

static void
release(void *x)
{
    *(void **)x = free_list_head;
    free_list_head = x;
}

```

This works well as long as all allocated blocks have the same size, and that size is a multiple of the size of a pointer, so that alignment is preserved. Allocation and deallocation are constant-time (that is, as constant-time as memory accesses and elementary additions -- in a modern computer, a memory access can involve cache misses and even virtual memory, hence disk accesses, so the "constant time" can be quite big). There is no memory overhead (no extra per-block pointers or things like that; the allocated blocks are contiguous). Also, the allocation pointer reaches a given point only if, at one time, that many blocks had to be allocated: since the allocation prefers using the free list, the allocation pointer is increased only if the space below the current pointer is clock full. In that sense, this is an *optimal* technique.

*Decreasing* the allocation pointer after a release can be more complex, since free blocks can be reliably identified only by following the free list, which goes through them in unpredictable order. If decreasing the big segment size when possible is important to you, you could want to use an alternate technique, with more overhead: between any two allocated blocks, you put a "hole". The holes are linked together with a doubly-linked list, in memory order. You need a data format for a hole such that you can locate the hole start address by knowing where it ends, and also the hole size if you know where the hole begins in memory. Then, when you release a block, you create a hole which you merge with the next and the previous holes, rebuilding (still in constant time) the ordered list of all holes. The overhead is then about two pointer-sized words per allocated block; but, at that price, you can reliably detect the occurrence of a "final hole", i.e. an occasion to decrease the big segment size.

There are many possible variations. A good introductory paper is Dynamic Storage Allocation: A Survey and Critical Review by Wilson *et al.*

# Answer
> 4 votes
*This answer is about generic memory management techniques. I missed that the question asks about the case where all blocks have the same size (and are aligned).*

---

The basic strategies you should know are first-fit, next-fit, best-fit, and the buddy system. I wrote a short summary once for a course I taught, I hope it's readable. I point there to a fairly exhaustive survey.

In practice you'll see various modifications of these basic strategies. But none of these is really constant time! I don't think that's possible in the worst case, while using a bounded amount of memory.

# Answer
> 2 votes
You may want to have a look at amortized analysis and in particular dynamic arrays. Even if the operations are not really done in constant time at every step, in the long run it looks like it is the case.

---
Tags: time-complexity, memory-allocation, operating-systems
---


# Question
Title: Algorithm to test whether a binary tree is a search tree and count complete branches
I need to create a recursive algorithm to see if a binary tree is a binary search tree as well as count how many complete branches are there (a parent node with both left and right children nodes) with an assumed global counting variable. This is an assignment for my data structures class.

So far I have

```
void BST(tree T) {
   if (T == null) return
   if ( T.left and T.right) {
      if (T.left.data < T.data or T.right.data > T.data) {
        count = count + 1
        BST(T.left)
        BST(T.right)
      }
   }
}

```

But I can't really figure this one out. I know that this algorithm won't solve the problem because the count will be zero if the second if statement isn't true.

Could anyone help me out on this one?

# Answer
As others have already indicated in comments, you really have two unrelated functions here: testing whether the tree is a search tree, and counting the complete branches. Unless the assignment specifically calls for it, I would write two separate functions.

Let's see abount counting the complete branches first. That means counting the nodes that have both a left child and a right child. Then you need to increment the counter (`count = count + 1`) when both `T.left` and `T.right` are non-null (not `T.left.data` and `T.right.data`: the data doesn't matter for this task).

```
if (T.left and T.right) {
    count = count + 1

```

Furthermore, you need to explore the left subtree even if the right subtree is empty, and you need to explore the right subtree even if the left subtree is empty. So watch where you put the recursive calls.

To test whether the tree is a search tree, you need to inspect the data values. You've already got something close to the right comparison; not quite right. **Write a few example trees with various shapes** (not very big, 2 to 5 nodes) and run your algorithm on them to see what happens.

You still need to find some place to put the result of the validity check. Again, watch where you put the recursive calls (if you only do this part, there are several solutions, but at this stage don't worry if you only see one).

Finally, once you've managed to write both functions separately, and you've tested them on a few examples, put them together carefully (if required by the assignment).
> 10 votes

# Answer
In things like this, it's often easier to think backwards, so first consider what you need. From your description, let's list them:

* Recursion
* Validity
* Count of complete nodes

OK, that's a fairly short list, this should be manageable. Let's start with an empty method and I'll add description of what should be happening.

```
valid_bst () {
}

```

Now validity. How do you check for validity? In chat you said a tree is valid "if ... all left children are less than the parent, and right children are greater than the parent." I'm sure you meant to allow equality as well. That would be `t.left.value <= t.value <= t.right.value`.

```
valid_bst () {
    This node is valid if t.left.value <= t.value <= t.right.value
}

```

But what if one of the children is missing? From what you've said, I believe you know the node is still valid if one is (or both are) missing. Let's add this, restructuring slightly:

```
valid_bst () {
    This node is valid to the left if
        there is no left child or
        it is no greater than the current node.
    This node is valid to the right if
        there is no right child or
        it is no less than the current node.
    This node is valid overall if it is valid to the left and right.
}

```

OK, we now know whether this node is valid. How do we check whether the entire tree is valid? It's not in an array, so we probably can't/don't want to loop over it linearly. Your assignment gives the answer: recursion. But how do we accumulate an answer using recursion? We have access to three pieces of information, whether this node is valid, and the result of calls asking whether the left and right nodes are valid. Obviously the tree is only valid if all three of those are true.

```
valid_bst () {
    This node is valid to the left if
        there is no left child or
        it is no greater than the current node.
    This node is valid to the right if
        there is no right child or
        it is no less than the current node.
    This node is valid overall if it is valid to the left and right.
    Is the left child valid?
    Is the right child valid?
    This tree is only valid if this node and both its children are.
}

```

If you're paying attention, that even tells us what our function needs to return.

Now, how do we integrate the counting? You say what counts ("a parent node with both left and right children nodes"), and that shouldn't be hard to translate into actual code. Check whether that condition is satisfied and increment the counter appropriately. Just remember this has to be somewhere where it will be reached every time it is true.

And of course I've left out some details like the recursion stopping condition and checks for null.
> 7 votes

# Answer
My three comments above are three hints to problems with your code.

1. Unless you have already specifically defined how a compare operator should handle the node data type, most likely comparing two nodes directly won't do what you want. What you probably meant was to compare the fields stored in the nodes, for example `node1.value < node2.value`
2. right now, you're only adding to the count if the third `if` is true, are you sure that's what you meant to do? By the way, you may want to double check that that if statement does what you want.
3. I assume that you want to return true if the tree is a valid BST and false otherwise. Which means that you have to always return true or false in a base case, and you should be returning the results of your recursive calls as well.
> 6 votes

---
Tags: algorithms, recursion, trees
---


# Question
Title: Determining capabilities of a min-heap (or other exotic) state machines
*See the end of this post for some clarification on the definition(s) of min-heap automata.*

One can imagine using a variety of data structures for storing information for use by state machines. For instance, push-down automata store information in a stack, and Turing machines use a tape. State machines using queues, and ones using two multiple stacks or tapes, have been shown to be equivalent in power to Turing machines.

Imagine a min-heap machine. It works exactly like a push-down automaton, with the following exceptions:

1. Instead of getting to look at the last thing you added to the heap, you only get to look at the smallest element (with the ordering defined on a per-machine basis) currently on the heap.
2. Instead of getting to remove the last thing you added to the heap, you only get to remove one of the smallest element (with the ordering defined on a per-machine basis) currently on the heap.
3. Instead of getting to add an element to the top of the heap, you can only add an element to the heap, with its position being determined according to the other elements in the heap (with the ordering defined on a per-machine basis).

This machine can accept all regular languages, simply by not using the heap. It can also accept the language $\displaystyle \\{a^{n}b^{n} \in \\{a, b\\}^{\*} \mid n \ge 0\\}$ by adding $a$'s to the heap, and removing $a$'s from the heap when it reads $b$'s. It can accept a variety of other context-free languages. However, it cannot accept, for instance, $\displaystyle \\{w \in \\{a, b\\}^{\*} \mid w = w^{R}\\}$ (stated without proof). EDIT: or can it? I don't think it can, but I've been surprised before, and I'm sure I'll keep being surprised when my assumptions to keep making of me an... well.

> Can it accept any context-sensitive or Turing-complete languages?

More generally, what research, if any, has been pursued in this direction? What results are there, if any? I am also interested in other varieties of exotic state machines, possibly those using other data structures for storage or various kinds of restrictions on access (e.g., how LBAs are restricted TMs). References are appreciated. I apologize in advance if this question is demonstrating ignorance.

---

**Formal Definition:**

I provide some more detailed definitions of min-heap automata here in order to clarify further discussion in questions which reference this material.

We define a *type-1 nondeterministic min-heap automaton* as a 7-tuple $$(Q, q\_0, A, \Sigma, \Gamma, Z\_0, \delta)$$ where...

1. $Q$ is a finite, non-empty set of states;
2. $q\_0 \in Q$ is the initial state;
3. $A \subseteq Q$ is the set of accepting states;
4. $\Sigma$ is a finite, non-empty input alphabet;
5. $\Gamma$ is a finite, non-empty input alphabet, where the weight of a symbol $\gamma \in \Gamma$, $w(\gamma) \in \mathbb{N}$, is such that $w(\gamma\_1) = w(\gamma\_2) \iff \gamma\_1 = \gamma\_2$;
6. $Z\_0 \notin \Gamma$ is the special bottom-of-the-heap symbol;
7. $\delta : Q \times (\Sigma \cup \\{\epsilon\\}) \times (\Gamma \cup \\{Z\_0\\}) \rightarrow \mathcal{P}({Q \times \Gamma^\*})$ is the transition function.

The transition function works by assuming an initially empty heap consisting of only $Z\_0$. The transition function may add to the heap an arbitrary collection (finite, but possibly empty or with repeats) of elements $\gamma\_1, \gamma\_2, ..., \gamma\_k \in \Gamma$. Alternatively, the transition function may remove an instance of the element $\gamma$ with the lowest weight $w(\gamma)$ of all elements remaining on the heap (i.e., the element on top of the heap). The transition function may only use the top-most (i.e., of minimal weight) symbol instance in determining any given transition.

Further, define a *type-1 deterministic min-heap automaton* to be a type-1 nondeterministic min-heap automaton which satisfies the following property: for all strings $x{\sigma}y \in \Sigma$ such that $|x| = n$ and $\sigma \in \Sigma$, $|\delta^{n+1}(q\_0, x{\sigma}y, Z\_0)| \leq 1$.

Define also a *type-2 nondeterministic min-heap automaton* exactly the same as a type-1 nondeterministic min-heap automaton, except for the following changes:

1. $\Gamma$ is a finite, non-empty input alphabet, where the weight of a symbol $\gamma \in \Gamma$, $w(\gamma) \in \mathbb{N}$, is such that $w(\gamma\_1) = w(\gamma\_2)$ does not necessarily imply $\gamma\_1 = \gamma\_2$; in other words, different heap symbols can have the same weight.
2. When instances of distinct heap symbols with same weight are added to the heap, their relative order is preserved according to a last-in, first-out (LIFO) stack-like ordering.

Thanks to Raphael for pointing out this more natural definition, which captures (and extends) the context-free languages.

---

**Some results demonstrated so far:**

1. Type-1 min-heap automata recognize a set of languages which is neither a subset nor a superset of the context-free languages. \[,\]
2. Type-2 min-heap automata, by their definition, recognize a set of languages which is a proper superset of the context-free languages, as well as a proper superset of the languages accepted by type-1 min-heap automata.
3. Languages accepted by type-1 min-heap automata appear to be closed under union, concatenation, and Kleene star, but not under complementation \[\], intersection, or difference;
4. Languages accepted by type-1 nondeterministic min-heap automata appear to be a proper superset of languages accepted by type-1 deterministic min-heap automata.

There may be a few other results I have missed. More results are (possibly) on the way.

---

**Follow-up Questions**

1. Closure under reversal? -- Open
2. Closure under complementation? -- No!
3. Does nondeterminism increase power? -- Yes?
4. Is $HAL \subsetneq CSL$ for type-2? -- Open
5. Does adding heaps increase power for type-1? -- $HAL^1 \subsetneq HAL^2 = HAL^k$ for $k \> 2$ (?)
6. Does adding a stack increase power for type-1? -- Open

# Answer
> 25 votes
You can recognize the canonical non-context-free (but context-sensitive) language $\\{ a^n b^n c^n\ |\ n \geq 1 \\}$ with this type of state machine. The crux is that you add tokens to the heap for every $a$ character, and while parsing the $b$ characters, you add 'larger' tokens to the heap, so they only end up at the bottom of the heap when you have parsed all the $b$ characters.

Heap symbols are $a$ and $b$, where $a \< b$. We consume all the $a$ symbols on the input and add $a$ symbols to the heap. If we encounter a $b$, we switch strategies: for every $b$ we encounter subsequently we remove an $a$ from the heap and add a $b$ to the heap. When we encounter a $c$ we should have run out of $a$s to remove, and then for every $c$ in the remaining input we remove a $b$ from the heap. If the heap is empty at the end, the string is in the language. Obviously, we reject if something goes wrong.

***Update:***

The language $EPAL = \\{ ww^R | w \in \\{a, b\\}^\* \\}$ can not be recognized by min-heap automata. Suppose that we do have a min-heap automaton that can recognize $EPAL$. We look at the 'state' the automaton is in after reading $w$ (the first part of the input, so $w^R$ is next). The only state we have are the contents of the heap and the particular state of the automaton it is in. This means that after recognizing $w$, this 'state' needs to hold enough information to match $w^R$.

In particular, in order to do this, there must be $2^n$ possible different 'state's (where $n = |w|$), as there are $2^n$ possible words consisting of $a$ and $b$ characters. As there are only a finite number of states and only a finite number of heap characters, this implies that there exists some word $w$ for which the heap contains an exponential number of some heap character, say $x$.

We first prove the theorem for deterministic min-heap automata, and then extend this proof to non-deterministic min-heap automata. In particular, deterministic automata that recognize some language will not put themselves in an infinite loop, which is a useful property.

We shall prove that the heap can only contain at most a number of heap tokens that is linear in the number of characters read from the input. This immediately rules out that $x$ appears an exponential number of times on the heap, which completes the proof that $EPAL$ can not be recognized by min-heap automata.

Because we only have a finite number of states in our automaton and because a deterministic automaton will not put itself into an infinite loop, on reading an input signal it will add at most a constant number of heap characters onto the heap. Similarly, on consuming some heap symbol $y$, it can only add at most a constant number of heap characters that are strictly larger than $y$ and it can only decrease the number of $y$ symbols on the stack (otherwise we get an infinite loop).

Consuming heap symbols may therefore cause an (enormous) buildup of larger heap symbols, but as there are only a constant number of different types of heap symbols, this is only a constant number not dependent on $n$. This implies that the number of heap symbols is at most some (large) constant times the number of input symbols read so far. This completes the proof for the deterministic case.

In the non-deterministic case, the proof is similar, but a bit trickier: instead of adding at most some constant number of heap tokens to the heap, it adds some arbitrary number of heap tokens to the heap. However, the crucial point is that this number does not depend on $n$. In particular, if we can non-deterministically get exactly the right heap symbols on the heap after recognizing $w$ (right for recognizing $w^R$), we can also non-deterministically choose the heap symbols that match some other word $w'$, and thereby recognize $w w'^R$, thus contradicting that the min-heap automaton recognizes exactly $EPAL$.

***Update 3:*** I'll make the last argument (about non-determinism) rigorous. By the above argument, there must exist an infinite set of words $W \subseteq \\{a,b\\}^\*$ such that for every $w \in W$, after recognizing $w$, the heap contains $\omega(|w|)$ elements (note that we can talk about $O(f(|w|))$ as we have an infinite set of words). As we cannot get that many elements on the heap through deterministic means, we must have had some form of a loop in which we first non-deterministically chose to add more elements to the heap (without consuming input), and later chose to exit this loop, and we must have traversed this loop $\omega(1)$ times.

Take the set of all such loops used by $W$. As there are only $O(1)$ states, the size of this set is $O(1)$, and the set of all its subsets is also $O(1)$. Now note that the 'deterministic' part of the execution paths can only contribute to $O(|w|)$ of the tokens, which means that a lot of the exponential number of different words must have execution paths whose 'deterministic' parts contribute the same tokens to the heap. In particular, the only way to get more tokens is to take the loops we identified above.

Combining these observations, this means that there must be two distinct words in $W$, $w\_1$ and $w\_2$ say, whose 'deterministic' part of the execution paths contribute the same tokens to the heap, and that are differentiated by taking some subset of the loops above a different number of times, but that use the same subset of loops (remember there are only $O(1)$ of these loops).

We can now show that $w\_1 w\_2$ can also be recognized by the min-heap automaton: we follow the execution path for $w\_1$ as above, but we traverse the loops the same number of times the execution path for $w\_2$ traverses them. This fills the min-heap with tokens such that $w\_2$ is accepted as suffix, thus completing the proof.

***Update 2:***

It just occurred to me that the above means that we can simulate a deterministic min-heap automaton using only logarithmic space: we keep a counter for every type of character in the min-heap. As shown above, this counter will at most be $O(n)$, and hence can be stored using only $O(\log n)$ space (as there are only a constant number of these counters). This gives us:

> $\mathrm{DHAL} \subset \mathrm{L}$
>
> $\mathrm{HAL} \subset \mathrm{NL}$

where $\mathrm{DHAL}$ is the set of languages recognized by some deterministic min-heap automaton.

# Answer
> 19 votes
Here is what we (believe to) know:

* $\mathrm{HAL} \setminus \mathrm{CFL} \neq \emptyset$ (type-1, type-2)
* $\mathrm{CFL} \setminus \mathrm{HAL} \neq \emptyset$ (type-1)
* $\mathrm{CFL} \subseteq \mathrm{HAL}$ (type-2, by definition)
* $\mathrm{CSL} \setminus \mathrm{HAL} \neq \emptyset$ (type-1, type-2)

See details and some other notes below.

---

### $\mathrm{HAL} \setminus \mathrm{CFL} \neq \emptyset$

*This part of the answer relates to both type-1 and type-2.*

A min-heap automaton (HA) with finite, totally ordered heap alphabet accepts $L = \\{ a^nb^nc^n \mid n \in \mathbb{N} \\} \in \mathrm{CSL} \setminus \mathrm{CFL}$.

Assumptions: Similar to PDA, our transition function consumes the top most heap symbol and writes back an arbitrary number of heap symbols. The heap initially contains a distinguished symbol $\\$$ which is larger than all other heap symbols.

Let $A = (Q,\Sigma\_I, \Sigma\_H, \rightarrow, q\_0, Q\_F)$ a min-heap automaton with

* $Q = \\{q\_0, q\_1, q\_2, q\_f\\}$ the set of states
* $\Sigma\_I = \\{a,b,c\\}$ the input alphabet.
* $\Sigma\_H = {a,b,\\$}$ the heap alphabet with ordering $a \lt b \lt \\$$.
* $Q\_F = \\{q\_f\\}$
* $\rightarrow\ \subseteq (Q \times \Sigma\_I \times \Sigma\_H) \times (Q \times \Sigma\_H^\*)$ with
    + $(q\_0,a,\sigma) \rightarrow (q\_0, a\sigma)$ for all $\sigma \in \Sigma\_H$
    + $(q\_0,b,a) \rightarrow (q\_1,b)$
    + $(q\_1,b,a) \rightarrow (q\_1,b)$
    + $(q\_1,c,b) \rightarrow (q\_2,\varepsilon)$
    + $(q\_2,c,b) \rightarrow (q\_2, \varepsilon)$
    + $(q\_2,c,\\$) \rightarrow (q\_f, \varepsilon)$

The automaton writes one $a$ to the heap for every $a$ in the input. When a $b$ occurs, it consumes as many $b$ as there have been $a$, writing a $b$ to the heap for every found $b$. This does not disturb counting because the heap conveniently keeps $a$ on the top. Only after all $a$ are taken from the heap are $c$ accepted; only after as many $c$ as $b$ (and therewith as $a$) are found, does $A$ accept with empty heap and final state.

Therefore, $\cal{L}(A) = L$.

---

### $\mathrm{CFL} \setminus \mathrm{HAL} \neq \emptyset$

*This part of the answer relates only to type-1.*

Consider $\mathrm{EPAL} = \\{ww^R \mid w \in \\{a,b\\}\\}$ the set of even palindromes and assume there is HA $A$ with $\cal{L}(A) = L$.

Conjecture: we find $w\_1, w\_2 \in \\{a,b\\}^\*$ with $w\_1 \neq w\_2$ and $|w\_1| = |w\_2|$ such that $A$ is in the same state and has the same heap content after reading $w\_1$ and $w\_2$, respectively. As $A$ accepts both $w\_1w\_1^R$ and $w\_2w\_2^R$, it therefore also accepts $w\_1w\_2^R \notin \mathrm{EPAL}$ (and $w\_2w\_1^R$), which is a contradiction to $\cal{L}(A) = \mathrm{EPAL}$.

---

### $\mathrm{CSL} \setminus \mathrm{HAL} \neq \emptyset$

*This part of the answer relates to both type-1 and type-2.*

The same reasoning we used on $\mathrm{EPAL}$ (for type-1) can be used to show that the context-sensitive language $\\{ww \mid w \in \\{a,b\\}^\*\\}$ is not in $\mathrm{HAL}$.

---

### $\mathrm{HAL} \overset{?}{\subseteq} \mathrm{CSL}$

*This is still open for both type-1 and type-2.*

---

### Further Factoids

HA seem to be orthogonal to a subset of the mildly context-senstive languages accepted by Embedded Pushdown Automata: While HA can simulate a bounded number of stacked stacks, they can not simulate arbitrarily many (as EPA can). However, HA can access the top symbols of stacks currently not on the top (which EPA can not).

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


# Question
Title: Recursive definitions over an inductive type with nested components
Consider an inductive type which has some recursive occurrences in a nested, but strictly positive location. For example, trees with finite branching with nodes using a generic list data structure to store the children.

```
Inductive LTree : Set := Node : list LTree -> LTree.

```

The naive way of defining a recursive function over these trees by recursing over trees and lists of trees does not work. Here's an example with the `size` function that computes the number of nodes.

```
Fixpoint size (t : LTree) : nat := match t with Node l => 1 + (size_l l) end
with size_l (l : list LTree) : nat := match l with
    | nil => 0
    | cons h r => size h + size_l r
  end.

```

This definition is ill-formed (error message excerpted):

```
Error:
Recursive definition of size_l is ill-formed.
Recursive call to size has principal argument equal to
"h" instead of "r".

```

Why is the definition ill-formed, even though `r` is clearly a subterm of `l`? Is there a way to define recursive functions on such a data structure?

---

If you aren't fluent in Coq syntax: `LTree` is an inductive type corresponding to the following grammar.

$$\begin{align} \mathtt{LTree} ::= & \\ \vert & \mathtt{list}(\mathtt{LTree}) \\ \end{align}$$

We attempt to define the `size` function by induction over trees and lists. In OCaml, that would be:

```
type t = Node of t list
let rec size = function Node l -> 1 + size_l l
and size_l = function [] -> 0
                    | h::r -> size h + size_l r

```

# Answer
> 16 votes
### What works

If you nest the definition of the fixpoint on lists inside the definition of the fixpoint on trees, the result is well-typed. This is a general principle when you have nested recursion in an inductive type, i.e. when the recursion goes through a constructor like `list`.

```
Fixpoint size (t : LTree) : nat :=
  let size_l := (fix size_l (l : list LTree) : nat :=
                  match l with
                    | nil => 0
                    | h::r => size h + size_l r
                  end) in
  match t with Node l =>
    1 + size_l l
  end.

```

Or if you prefer to write this more tersely:

```
Fixpoint size (t : LTree) : nat :=
  match t with Node l =>
    1 + (fix size_l (l : list LTree) : nat :=
          match l with
            | nil => 0
            | h::r => size h + size_l r
          end) l
  end.

```

(I have no idea who I heard it from first; this was certainly discovered independently many times.)

### A general recursion predicate

More generally, you can define the “proper” induction principle on `LTree` manually. The automatically generated induction principle `LTree_rect` omits the hypothesis on the list, because the induction principle generator only understand non-nested strictly positive occurences of the inductive type.

```
LTree_rect =
fun (P : LTree -> Type) (f : forall l : list LTree, P (Node l)) (l : LTree) =>
match l as l0 return (P l0) with
| Node x => f x
end
     : forall P : LTree -> Type,
       (forall l : list LTree, P (Node l)) -> forall l : LTree, P l

```

Let's add the induction hypothesis on lists. To fulfill it in the recursive call, we call the list induction principle and pass it the tree induction principle on the smaller tree inside the list.

```
Fixpoint LTree_rect_nest (P : LTree -> Type) (Q : list LTree -> Type)
                         (f : forall l, Q l -> P (Node l))
                         (g : Q nil) (h : forall t l, P t -> Q l -> Q (cons t l))
                         (t : LTree) :=
  match t as t0 return (P t0) with
    | Node l => f l (list_rect Q g (fun u r => h u r (LTree_rect_nest P Q f g h u)) l)
  end.

```

### Why

The answer to why lies in the precise rules for accepting recursive functions. These rules are perforce subtle, because there is a delicate balance between allowing complex cases (such as this one, with nested recursion in the datatype) and unsoundness. The Coq reference manual introduces the language (the calculus of inductive constructions, which is the proof language of Coq), mostly with formally precise definitions, but if you want the exact rules regarding induction and coinduction you'll need go to the research papers, on this topic Eduardo Giménez's \[1\].

Starting with the Coq manual, in the notation of the `Fix` rule, we have the fixpoint definition of $\mathsf{Fix} f\_i \\, \\{ f\_1 : A\_1 := t\_1 \\; ; \\;\\; f\_2 : A\_2 := t\_2 \\}$ where:

$$\begin{align\*} \Gamma\_1 &= (x : \mathtt{LTree}) & A\_1 &= \mathrm{nat} & t\_1 &= \mathsf{case}(x, \mathtt{LTree}, \lambda y. g\_1 (f\_2 y)) \\ \Gamma\_2 &= (l : \mathtt{list}\\;\mathtt{LTree}) & A\_2 &= \mathrm{nat} & t\_2 &= \mathsf{case}(l, \mathtt{list \\: LTree}, \lambda h \\: r. g\_2 (f\_1 h) (f\_2 r)) \\ \end{align\*}$$

In order for the fixpoint definition to be accepted, “if $f\_j$ occurs \[in $t\_i$\] then … the argument should be syntactically recognized as structurally smaller than \[the argument passed to $f\_i$\]” (simplifying because the functions have a single argument). Here, we need to check that

* $i=1$, $j=2$: `l` must be structurally smaller than `t` in `size`, ok.
* $i=2$, $j=1$: `h` must be structurally smaller than `l` in `size_l`, looks ok but isn't!
* $i=2$, $j=2$: `r` must be structurally smaller than `l` in `size_l`, ok.

The reason why `h` is not structurally smaller than `l` according to the Coq interpreter is not clear to me. As far as I understand from discussions on the Coq-club list \[1\] \[2\], this is a restriction in the interpreter, which could in principle be lifted, but very carefully to avoid introducing an inconsistency.

### References

Cocorico, the nonterminating Coq wiki: Mutual Induction

Coq-Club mailing list:

The Coq Development Team. *The Coq Proof Assistant: Reference Manual*. Version 8.3 (2010). \[web\] ch. 4.

Eduardo Giménez. *Codifying guarded definitions with recursive schemes*. In *Types'94: Types for Proofs and Programs*, LNCS 996. Springer-Verlag, 1994. doi:10.1007/3-540-60579-7\_3 \[Springer\]

Eduardo Giménez. *Structural Recursive Definitions in Type Theory*. In *ICALP'98: Proceedings of the 25th International Colloquium on Automata, Languages and Programming. Springer-Verlag, 1998.* \[PDF\]

# Answer
> 7 votes
This is obviously a problem specific to Coq since I believe there are nicer ways to get around it with some other proof assistants (I'm looking at Agda)

At first I thought `r` was not recognized as structurally smaller because the structure is only about the inductive definition currently handled by `Fixpoint`: so this is not a `LTree` subterm even if it is a `list` subterm.

But if you expand the processing of the list, then it works:

```
Fixpoint size t :=
  match t with
  | Node l => S
     ((fix size_l l :=
     match l with
     | nil => 0
     | cons t l => size_l l + size t
     end) l)
 end.

```

Or since the auxiliary function already exists in the standard library:

```
Require Import List.

Fixpoint size t :=
  match t with
  | Node l => S (fold_left (fun a t => a + size t) l 0)
  end.

```

To be honest I'm not sure why those are accepted by Coq, but I'm sure glad they are.

There is also a solution that works more often and not only for lists: defining a self-contained inductive type. In this case you can define your `size` function manually. (with two fixpoints)

```
Inductive LTree : Set :=
  | Node : list_LTree -> LTree
with list_LTree : Set :=
  | LTree_nil : list_LTree
  | LTree_cons : LTree -> list_LTree -> list_LTree.

```

Note that if you have problems for more complex inductive definitions, you can use a size-decreasing argument. That is possible but cumbersome for this problem (and I would dare to say for most problems)

---
Tags: logic, coq, type-theory, recursion, proof-assistants
---


# Question
Title: What is the significance of context-sensitive (Type 1) languages?
Seeing that in the Chomsky Hierarchy Type 3 languages can be recognised by a state machine with no external memory (i.e., a finite automaton), Type 2 by a state machine with a *single* stack (i.e. a push-down automaton) and Type 0 by a state machine with *two* stacks (or, equivalently, a tape, as is the case for Turing Machines), how do Type 1 languages fit into this picture? And what advantages does it bring to determine that a language is not only Type 0 but Type 1?

# Answer
The context-sensitive languages are exactly the languages that can be recognized by a Turing machine using linear space and non-determinism. You can simulate such a Turing machine using exponential time, so you can recognize any such language in exponential time. Do note that the problem of recognizing some context-sensitive languages is $PSPACE$-complete, which means we're pretty sure you can't do better than exponential time.

Comparing this to type 0 languages, this means you can at least say *something* about how long it takes to recognize the language. A type 0 language may not even be decidable: the language of all Turing machines that halt is a type 0 language, but as recognizing this language is exactly the halting problem, it is not decidable.

Context-sensitive grammars are not very useful in practice. Context-**free** grammars are intuitive to work with, but as the examples on Wikipedia show, context-**sensitive** grammars very quickly become rather messy. Programs using polynomial space are much more easily designed (and the $PSPACE$-completeness guarantees the existence of some equivalent CSG that is only polynomially larger than the space usage of your algorithm).

The reason for their existence is that they form a very natural extension of context-free grammars (you allow context to determine which productions are valid). This will probably have inspired Chomsky to define them and name them the type 1 languages. Remember that this definition was made before computers became as fast as they are today: it's more of interest to formal language theorists than for programmers.

Unrestricted grammars get even weirder: there's no longer a notion of 'expanding' a nonterminal and replacing it with a production, possibly depending on context. You're allowed to freely modify the context as well. This makes unrestricted grammars even less intuitive to work with: programs are equivalent and a lot more intuitive.
> 20 votes

# Answer
Generally speaking, you usually want to know the smaller class to which a given language $L$ belongs. This is because smaller classes can be recognized/accepted/generated by simpler mechanisms (automata, grammars, regular expressions, etc.), which is desirable.

For example, the class of regular languages has *good* closure properties, and given a DFA $\mathcal{A}$ you can test in linear time that a word belongs to $L(\mathcal{A})$. In contrast, with a Turing machine you need linear time just to read the output, which usually happens **before** it actually starts processing.

In short, for smaller classes you need less computational power to solve the problem of deciding whether a word belongs to the language.

According to Wikipedia, Chomsky defined context-sensitive grammars (i.e. Type 1) to describe the syntax of natural languages. This is a bit different than with other classes of languages, which were introduced to describe families of strings that were used in mathematics (e.g. the syntax of arithmetic formulae) instead of natural languages (e.g. the syntax of a gramatically-correct sentence in English).
> 10 votes

# Answer
In context-free languages, at any point of the input parsing, the automaton is in a state defined by its stack. Each production has the same behaviour in consuming the input regardless of where it is used.

This leads to the interesting property that each production generates a sub-language of the one generated by the ones that are deeper in the stack and thus for each pair A and B of productions generated and consumed on any particular input we have three possible cases:

* a: The input consumed by A is completely contained in the input consumed by B; or
* b: The input consumed by A completely contains the input consumed by B; or
* c: The input consumed by A is completely disjoint from the input consumed by B.

This implies that the following never happens:

* d: The input consumed by A partially overlaps the input consumed by B.

Contrasting to that, in context-sensitive languages, the behaviour of each production depends on where it is used, so the input consumed in a production is not a sub-language of the ones deeper in the stack (in fact, processing it with a stack would not work). And we have that possibility d may happen.

In the real world, a case where a context-sensitive language would make sense is something like denoting \<b\>bold text\</b\>, \<i\>italic text\</i\> and \<u\>underlined text\</u\> with these html tags and let them overlap, like "This is a \<u\>text with \<i\>mixed\</u\> overlapping tags\</i\>." Observe that to parse that and find if all the starting tags match the ending tags, a PDA won't do because it is not context-free, but an LBA will easily do.
> 8 votes

# Answer
## Closure Properties

Of all language classes from the Chomsky hierarchy, only regular and context-sensitive languages are closed under **complementation**. Hence this is a sort of unique feature of context-sensitive languages.

In contrast to context-free languages, CS are also closed under intersection and shuffle product.
> 7 votes

# Answer
Any language that is type 1 can be recognized by a Turing machine that only uses linear space (so-called linear bounded automata).
> 6 votes

# Answer
Type 1 languages can be decided by linear bounded automata, which are non-deterministic Turing machines that may only use a portion of the tape whose size is linear to the input size.
> 5 votes

# Answer
The Chomsky hierarchy classifies grammars more than languages. However it was not designed to have something to do with the number of tapes a automaton should have to recognize it, as you suggested for Type 2 and 3, even if there is a kind of Turing machine that does that for Type-1 grammars.

You should also note that the languages of Type-0 grammars are not all recognized by a Turing machine, but they only can be enumerated by such a machine: Type-0 means recursively enumerable, and Turing machines only recognize recursive languages.
> 4 votes

# Answer
Modern programming language use context-sensitive features all the time; they fall into a subset that can efficiently be decided.

Examples are name and type analysis and type inference.
> 4 votes

# Answer
Many others have mentioned that Type-1 languages are those that can be recognised by linear bounded automata. The halting problem is decidable for linear bounded automata, which in turn means many other properties that are computationally undecidable for languages recognised by Turning Machines are decidable for Type-1 languages.

Admittedly the proof that the halting problem is decidable for linear bounded automata relies on the fact that with a finite amount of tape they can only enter a finite number of states, so if they don't halt within that many steps you know they're looping and won't ever halt. This proof technically applies to all actual computers (which also have finite memory), but that isn't of any practical benefit in solving the halting problem for the programs that run on them.
> 3 votes

---
Tags: formal-languages, applied-theory, computability, automata, formal-grammars
---


# Question
Title: How does one know which notation of time complexity analysis to use?
In most introductory algorithm classes, notations like $O$ (Big O) and $\Theta$ are introduced, and a student would typically learn to use one of these to find the time complexity.

However, there are other notations, such as $o$, $\Omega$ and $\omega$. Are there any specific scenarios where one notation would be preferable to another?

# Answer
> 86 votes
You are referring to the Landau notation. They are not different symbols for the same thing but have entirely different meanings. Which one is "preferable" depends entirely on the desired statement.

$f \in \cal{O}(g)$ means that $f$ grows at most as fast as $g$, asymptotically and up to a constant factor; think of it as a $\leq$. $f \in o(g)$ is the stricter form, i.e. $\<$.

$f \in \Omega(g)$ has the symmetric meaning: $f$ grows at least as fast as $g$. $\omega$ is its stricter cousin. You can see that $f \in \Omega(g)$ is equivalent to $g \in \cal{O}(f)$.

$f \in \Theta(g)$ means that $f$ grows about as fast as $g$; formally $f \in \cal{O}(g) \cap \Omega(g)$. $f \sim g$ (asymptotic equality) is its stronger form. We often mean $\Theta$ when we use $\cal{O}$.

Note how $\cal{O}(g)$ and its siblings are *function classes*. It is important to be very aware of this and their precise definitions -- which can differ depending on who is talking -- when doing "arithmetics" with them.

When proving things, take care to work with your precise definition. There are many definitions for Landau symbols around (all with the same basic intuition), some of which are equivalent on some sets on functions but not on others.

Suggested reading:

If you are interested in using Landau notation in a rigorous and sound manner, you may be interested in recent work by Rutanen et al. \[1\]. They formulate necessary and sufficient criteria for asymptotic notation as we use them in algorithmics, show that the common definition fails to meet them and provide a (the, in fact) workable definition.

---

1. A general definition of the O-notation for algorithm analysis by K. Rutanen et al. (2015)

# Answer
> 47 votes
### Big O: upper bound

“Big O” ($O$) is by far the most common one. When you analyse the complexity of an algorithm, most of the time, what matters is to have some upper bound on how fast the run time¹ grows when the size of the input grows. Basically we want to know that running the algorithm isn't going to take “too long”. We can't express this in actual time units (seconds), because that would depend on the precise implementation (the way the program is written, how good the compiler is, how fast the machine's processor is, …). So we evaluate what doesn't depend on such details, which is how much longer it takes to run the algorithm when we feed it bigger input. And we mainly care when we can be sure that the program is done, so we usually want to know that it will take such-and-such amount of time or less.

To say that an algorithm has a run time of $O(f(n))$ for an input size $n$ means that there exists some constant $K$ such that the algorithm completes in at most $K \\, f(n)$ steps, i.e. the running time of the algorithm grows at most as fast as $f$ (up to a scaling factor). Noting $T(n)$ the run time of the algorithm for input size $n$, $O(n)$ informally means that $T(n) \le f(n)$ up to some scaling factor.

### Lower bound

Sometimes, it is useful to have more information than an upper bound. $\Omega$ is the converse of $O$: it expresses that a function grows at least as fast as another. $T(n) = \Omega(g(n))$ means that $T(N) \ge K' g(n)$ for some constant $K'$, or to put it informally, $T(n) \ge g(n)$ up to some scaling factor.

When the running time of the algorithm can be determined precisely, $\Theta$ combines $O$ and $\Omega$: it expresses that the rate of growth of a function is known, up to a scaling factor. $T(n) = \Theta(h(n))$ means that $K h(n) \ge T(n) \ge K' h(n)$ for some constants $K$ and $K'$. Informally speaking, $T(n) \approx h(n)$ up to some scaling factor.

### Further considerations

The “little” $o$ and $\omega$ are used far less often in complexity analysis. Little $o$ is stronger than big $O$; where $O$ indicates a growth that is no faster, $o$ indicates that the growth is strictly slower. Conversely, $\omega$ indicates a strictly faster growth.

I've been slightly informal in the discussion above. Wikipedia has formall definitions and a more mathematical approach.

Keep in mind that the use of the equal sign in $T(n) = O(f(n))$ and the like is a misnomer. Strictly speaking, $O(f(n))$ is a set of functions of the variable $n$, and we should write $T \in O(f)$.

### Example: some sorting algorithms

As this is rather dry, let me give an example. Most sorting algorithms have a quadratic worst case run time, i.e. for an input of size $n$, the run time of the algorithm is $O(n^2)$. For example, selection sort has an $O(n^2)$ run time, because selecting the $k$th element requires $n-k$ comparisons, for a total of $n(n-1)/2$ comparisons. In fact, the number of comparisons is always exactly $n(n-1)/2$, which grows as $n^2$. So we can be more precise about the time complexity of selection sort: it is $\Theta(n^2)$.

Now take merge sort. Merge sort is also quadratic ($O(n^2)$). This is true, but not very precise. Merge sort in fact has a running time of $O(n \\: \mathrm{lg}(n))$ in the worst case. Like selection sort, merge sort's work flow is essentially independent of the shape of the input, and its running time is always $n \\: \mathrm{lg}(n)$ up to a constant multiplicative factor, i.e. it is $\Theta(n \\: \mathrm{lg}(n))$.

Next, consider quicksort. Quicksort is more complex. It is certainly $O(n^2)$. Furthermore, the worst case of quicksort is quadratic: the *worst case* is $\Theta(n^2)$. However, the best case of quicksort (when the input is already sorted) is linear: the best we can say for a lower bound to quicksort in general is $\Omega(n)$. I won't repeat the proof here, but the *average* complexity of quicksort (the average taken over all possible permutations of the input) is $\Theta(n \\: \mathrm{lg}(n))$.

There are general results on the complexity of sorting algorithms in common settings. Assume that a sorting algorithm can only compare two elements at a time, with a yes-or-no result (either $x \le y$ or $x \> y$). Then it is obvious that any sorting algorithm's running time is always $\Omega(n)$ (where $n$ is the number of elements to sort), because the algorithm has to compare every element at least once to know where it will fit. This lower bound can be met, for example, if the input is already sorted and the algorithm merely compares each element with the next one and keeps them in order (that's $n-1$ comparisons). What is less obvious is that the *maximum* running time is necessarily $\Omega(n \\: \mathrm{lg}(n))$. It's possible that the algorithm will sometimes make fewer comparisons, but there has to be some constant $K$ such that for any input size $n$, there is at least one input on which the algorithm makes more than $K n \mathrm{lg}(n)$ comparisons. The idea of the proof is to build the decision tree of the algorithm, i.e. to follow the decisions the algorithm takes from the result of each comparison. Since each comparison returns a yes-or-no result, the decision tree is a binary tree. There are $n!$ possible permutations of the input, and the algorithm needs to distinguish between all of them, so the size of the decision tree is $n!$. Since the tree is a binary tree, it takes a depth of $\Theta(\mathrm{lg}(n!)) = \Theta(n\\:\mathrm{lg}(n))$ to fit all these nodes. The depth is the maximum number of decisions that the algorithm takes, so running the algorithm involves at least this many comparisons: the maximum running time is $\Omega(n \\: \mathrm{lg}(n))$.

¹ <sub> Or other resource consumption such as memory space. In this answer, I only consider running time. </sub>

# Answer
> 19 votes
Typically $O$ is used for stating upper-bounds (an estimate from above), while $\Omega$ is used to state lower-bounds (an estimate from below), and $\Theta$ is used when they match, in which case you can use $\Theta$ in place of them (usually) to state the result.

---
Tags: algorithms, terminology, asymptotics, landau-notation, reference-question
---


# Question
Title: How fundamental are matroids and greedoids in algorithm design?
Initially, matroids were introduced to generalize the notions of linear independence of a collection of subsets $E$ over some ground set $I$. Certain problems that contain this structure permit greedy algorithms to find optimal solutions. The concept of greedoids was later introduced to generalize this structure to capture more problems that allow for optimal solutions to be found by greedy methods.

How often do these structures arise in algorithm design?

Furthermore, more often than not a greedy algorithm will not be able to fully capture what is necessary to find optimal solutions, but may still find very good approximate solutions (Bin Packing, for example). Given that, is there a way to measure how "close" a problem is to a greedoid or matroid?

# Answer
> 19 votes
It's difficult to answer the question "how often". But as with all "underlying structures" the benefit comes from recognizing that the underlying problem one is trying to solve has a matroid (or greedoid) structure. It's not just matroid problems. The matroid intersection problem has a specific model (bipartite matching).

Nick Harvey did his Ph.D thesis fairly recently on algorithms for matroid problems and also looked at submodular function optimization (which generalizes matroid problems). Reading the introduction and background to the thesis might be helpful.

---
Tags: algorithms, optimization, combinatorics, greedy-algorithms, matroids
---


# Question
Title: What Is The Complexity of Implementing a Particle Filter?
In a video discussing the merits of particle filters for localization, it was implied that there is some ambiguity about the complexity cost of particle filter implementations. Is this correct? Could someone explain this?

# Answer
> 5 votes
It appears that the speaker feels that there isn't a definitive complexity analysis yet for the technique. This could be due to a couple of factors.

1. The analysis is hard, and no one has figured it out yet.
2. The technique has multiple different appropriate implementations, based on the problem context.

I'd bet on the second option, particularly in light of the speaker's comment that the technique may not be appropriate for higher dimension parameter spaces. Keep in mind that the video did not present an algorithm, it presented a very high-level discussion of a technique.

---
Tags: computational-geometry, knowledge-representation, reasoning, statistics
---


# Question
Title: Analyzing load balancing schemes to minimize overall execution time
Suppose that a certain parallel application uses a master-slave design to process a large number of workloads. Each workload takes some number of cycles to complete; the number of cycles any given workload will take is given by a known random variable $X$. Assume that there are $n$ such workloads and $m$ equivalent slaves (processing nodes). Naturally, a more general version of this question addresses the case of slaves of differing capabilities, but we ignore this for now.

The master cannot process workloads, but can distribute workloads to slave nodes and monitor progress of slave nodes. Specifically, the master can perform the following actions:

1. Instantaneously begin processing of any $k$ workloads on any free node.
2. Instantaneously receive confirmation of the completion by a node of a previously initiated batch of $k$ workloads.
3. At any point in time, and instantaneously, determine the state of all nodes (free or busy) as well as the number of workloads completed and the number of workloads remaining.

For simplicity's sake, assume $k$ divides $n$.

There are at least two categories of load balancing strategies for minimizing the total execution time of all workloads using all slaves (to clarify, I'm talking about the makespan or wall-clock time, not the aggregate process time, which is independent of the load-balancing strategy being used under the simplifying assumptions being made in this question): static and dynamic. In a static scheme, all placement decisions are made at time $t = 0$. In a dynamic scheme, the master can make placement decisions using information about the progress being made by some slaves, and as such, better utilization can be attained (in practice, there are overheads associated with dynamic scheduling as compared to static scheduling, but we ignore these). Now for some questions:

1. Is there a better way to statically schedule workloads than to divide batches of $k$ workloads among the $m$ slaves as evenly as possible (we can also assume, for simplicity's sake, that $m$ divides $n/k$, so batches could be statically scheduled completely evenly)? If so, how?
2. Using the best static scheduling policy, what should the mean and standard deviation be for the total execution time, in terms of the mean $\mu$ and standard deviation $\sigma$ of $X$?

A simple dynamic load balancer might schedule $i$ batches of $k$ workloads to each slave initially, and then, when nodes complete the initial $i$ batches, schedule an additional batch of $k$ workloads to each slave on a first-come, first-served basis. So if two slave nodes are initially scheduled 2 batches of 2 workloads each, and the first slave finishes its two batches, an additional batch is scheduled to the first slave, while the second slave continues working. If the first slave finishes the new batch before the second batch finishes its initial work, the master will continue scheduling to the first slave. Only when the second slave completes executing its work will it be issued a new batch of workloads. Example:

```
         DYNAMIC           STATIC
         POLICY            POLICY

     slave1  slave2    slave1  slave2
     ------  ------    ------  ------

t<0    --      --        --      --

t<1  batch1  batch3    batch1  batch3
     batch2  batch4    batch2  batch4
                       batch5  batch7
                       batch6  batch8

t=1    --    batch3    batch5  batch3
             batch4    batch6  batch4
                               batch7
                               batch8

t<2  batch5  batch3    batch5  batch3
             batch4    batch6  batch4
                               batch7
                               batch8

t=2    --    batch4    batch6  batch4
                               batch7
                               batch8

t<3  batch6  batch4    batch6  batch4
                               batch7
                               batch8

t=3    --      --        --    batch7
                               batch8

t<4  batch7  batch8      --    batch7
                               batch8

t=4    --      --        --    batch8

t<5      -DONE-          --    batch8

t=5                      --      --

t < 6                      -DONE-

```

For clarification, batches 1 and 2 take 1/2 second each to be processed, batch 3 takes 2 seconds to be processed, and batches 4-8 take 1 second each to be processed. This information is not known a-priori; in the static scheme, all jobs are distributed at t=0, whereas in the dynamic scheme, distribution can take into account what the actual runtimes of the jobs "turned out" to be. We notice that the static scheme takes one second longer than the dynamic scheme, with slave1 working 3 seconds and slave2 working 5 seconds. In the dynamic scheme, both slaves work for the full 4 seconds.

Now for the question that motivated writing this:

1. Using the dynamic load balancing policy described above, what should the mean and standard deviation be for the total execution time, in terms of the mean $\mu$ and standard deviation $\sigma$ of $X$?

Interested readers have my assurances that this isn't homework, although it probably isn't much harder than what one might expect to get as homework in certain courses. Given that, if anyone objects to this being asked and demands that I show some work, I will be happy to oblige (although I don't know when I'll have time in the near future). This question is actually based on some work that I never got around to doing a semester or two ago, and empirical results were where we left it. Thanks for help and/or effort, I'll be interested to see what you guys put together.

# Answer
Update:

For the new version where you try to minimize the makespan, your static schedule still has the optimal expected value.

Let $M$ be the random variable for the makespan. Let $F\_i$ be the time slave $i$ is finished. We then have that $M = \max\_i(X\_i)$. Let $c\_i$ be the number of jobs allocated to slave $i$. Then we have that $X\_i = \sum\_{i=1}^{c\_i} X = c\_i X$.

If $F\_i(x)$ is the cumulative probability distribution function for $X$, then $P(M \< m) $ $ = P(\max\_i(X\_i) \< m) $ $ = \prod\_i P(X\_i \< m) $ $ = \prod\_i P(c\_i X \< m) $ $ = \prod\_i P(X \< \frac{m}{c\_i}) $ $ = \prod\_i F(\frac{m}{c\_i})$ is the cumulative probability distribution function for $M$. This means that $EM = \int\_{-\infty}^{\infty} x (\prod\_i F(\frac{x}{c\_i}))' dx$ and $stddev(M) = \sqrt{\int\_{-\infty}^{\infty} (x - EM)^2 (\prod\_i F(\frac{x}{c\_i}))' dx}$, as normal.

Minimizing $EM$ amounts to minimizing $\prod\_i F(\frac{x}{c\_i})$, which means we want to keep all $c\_i$s equally low (as $F$ is monotonically increasing and between 0 and 1). This means we should equally distribute all tasks among the slaves, which is exactly what your static schedule achieves.
> 5 votes

---
Tags: scheduling, distributed-systems, parallel-computing
---


# Question
Title: Is there any nongeneral CFG parsing algorithm that recognises EPAL?
EPAL, the language of even palindromes, is defined as the language generated by the following unambiguous context-free grammar:

> $S \rightarrow a a$
>
> $S \rightarrow b b$
>
> $S \rightarrow a S a$
>
> $S \rightarrow b S b$

EPAL is the 'bane' of many parsing algorithms: I have yet to encounter any parsing algorithm for unambiguous CFGs that can parse any grammar describing the language. It is often used to show that there are unambiguous CFGs that cannot be parsed by a particular parser. This inspired my question:

> Is there some parsing algorithm accepting only unambiguous CFGs that works on EPAL?

Of course, one can design an ad-hoc two-pass parser for the grammar that parses the language in linear time. I'm interested in parsing methods that have not been designed specifically with EPAL in mind.

# Answer
Consider the following sketch of a parsing strategy at your own risk.

Instead of reading the input only from one end, we read from both sides and look for matching rules. We can do this in recursive descent style; in a call to $A()$, find prefix $w$ and suffix $v$ to the input such that there is a rule $A \to wBv$, descend to $B()$ on the remaining word. If there is no matching rule, reject the word.

This algorithm parses all linear, unambiguous grammars. It takes linear time if all rule pairs $A \to wBv$ and $A \to w'B'v'$ have $w \not\equiv\_p w'$ or $v \not\equiv\_s v'$¹. This includes EPAL. Otherwise we need to look ahead so we might take $\Theta(n^2)$ time.

The idea does not work for non-linear grammars at all. Linear but ambiguous grammars can in general not be parsed without backtracking (for negative inputs at least).

---

1. $w \not\equiv\_p v$ means here that $w \not\sqsubseteq v$ and $v \not\sqsubseteq w$, i.e. neither word is a prefix of the other. $\not\equiv\_s$ is similar for suffixes.
> 14 votes

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


# Question
Title: Natural candidates for the hierarchy inside NPI
Let's assume that $\mathsf{P} \neq \mathsf{NP}$. $\mathsf{NPI}$ is the class of problems in $\mathsf{NP}$ which are neither in $\mathsf{P}$ nor in $\mathsf{NP}$-hard. You can find a list of problems conjectured to be $\mathsf{NPI}$ here.

Ladner's theorem tells us that if $\mathsf{NP}\neq\mathsf{P}$ then there is an infinite hierarchy of $\mathsf{NPI}$ problems, i.e. there are $\mathsf{NPI}$ problems which are harder than other $\mathsf{NPI}$ problems.

> I am looking for candidates of such problems, i.e. I am interested in pairs of problems
> \- $A,B \in \mathsf{NP}$,
> \- $A$ and $B$ are conjectured to be $\mathsf{NPI}$,
> \- $A$ is known to reduce to $B$,
> \- but there are no known reductions from $B$ to $A$.

Even better if there are arguments for supporting these, e.g. there are results that $B$ does not reduce to $A$ assuming some conjectures in complexity theory or cryptography.

Are there any *natural* examples of such problems?

Example: Graph Isomorphism problem and Integer Factorization problem are conjectured to be in $\mathsf{NPI}$ and there are argument supporting these conjectures. Are there any decision problems harder than these two but not known to be $\mathsf{NP}$-hard?

# Answer
I've found a nice problem called *ModularFactorial*. Take as input two $n$-digit integers $x$ and $y$, and output $x! \mod y$. This problem is at least as hard as *Factoring* and not know to be hard for **FNP**. The reference is the recent (and beautiful) book by Cristopher Moore and Stephan Mertens The Nature of Computation, page 79.
> 5 votes

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


# Question
Title: Is this finite graph problem decidable? What factors make a problem decidable?
I want to know if the following problem is decidable and how to find out. Every problem I see I can say "yes" or "no" to it, so are most problems and algorithms decidable except a few (which is provided here)?

> Input: A directed and finite graph $G$, with $v$ and $u$ as vertices
> Question: Does a path in $G$ with $u$ as initial vertex and $v$ as final vertex exist?

# Answer
Any problem that requires only examining a finite amount of data is decidable, because there is an algorithm that consists of enumerating all the potential solutions. It may be ridiculously slow, but that's not relevant: if there is an algorithm, it's decidable.

The problem you state assumes a finite graph, which strongly hints that it's decidable. Strictly speaking, you need to look a bit further. The problem is a property on the paths in the graph, and there is sometimes an infinite number of paths, when the graph contains a cycle (you can loop around this cycle as many times as you like). However, it's easy to turn the problem to a finite problem: if there is any path beginning with $u$ and ending with $v$ that includes a cycle, then you can cut out all the cycles in that path, and you have a new solution which does not include a cycle. Since there is a finite number of paths that do not involve a cycle (if the graph has $k$ edges, there are at most $k!$ paths that do not use the same edge more than once), the problem of finding a path from $u$ to $v$ is finitary, hence decidable.

Incidentally, this property is called connectivity.

This approach is a common one, called reduction. Given a problem which is not straightforward, we reduced it to a problem we knew how to solve.

It is often difficult to prove that a problem is undecidable. To prove that a problem is decidable, all we need to do is exhibit an algorithm that decides it. To prove that a problem is undecidable, we need to prove that no algorithm can exist. There are a few well-known undecidable problems. In practice, most of the time, when we prove that a problem is undecidable, we show that there is a well-known undecidable problem that reduces to our problem. Since an algorithm for our problem would solve the well-known undecidable problem, our problem must also be undecidable.

You can't really say that “most” problems are decidable or “most” problems are undecidable. In some theoretical sense, almost all problems are undecidable, but we have a strong tendency to tackle “interesting” problems, and those are more likely to have a solution.
> 19 votes

# Answer
The problem is trivially decidable, as pointed out by Gilles in a comment. As for your other question...

> are most problems and algorithms decidable except a few (which is provided here)?

Nope. Actually, *most* problems are undecidable. In fact, there are uncountably many problems (languages), but there are only countable many Turing Machines, which means there are at most countable many decidable problems.
> 15 votes

# Answer
Yes, this is decidable, because you can do an exhaustive search of all possible paths. There is no need to look at any paths that repeat a vertex, since the "detour" could be skipped. But the length of any non-repetitive path is bounded by the size of the graph, which is finite, and so there are only finitely many such paths, which can be checked one by one.

What is not decidable is the following: given an infinite graph $G$ and two vertices $a$ and $b$, decide whether there is a path from $a$ to $b$. This is not decidable if the graph is given as an oracle and is also not decidable if the graph is given via a program that computes it.
> 8 votes

# Answer
There is no method that tells you whether a specific problem is decidable or not. With time, you might get a good "hunch" whether or not a specific problem is decidable.

What I usually do is the following:

1. try to solve the problem. That is, try to think of a computer program that solves the given problem. For your suggested problem - a very simple program will just check any possible path and thus will always succeed to find it (if it exists), or tell you no path exists otherwise.
2. formulate the problem clearly. Many problems are just too vague, but when written clearly it is very easy to see if decidable or not (by comparing to other problems, known to be un/decidable, or by using known methods like Rice's theorem)
3. If (2) didn't work but you still believe the problem is undecidable, try to prove it by reduction from an undecidable problem (Halting problem (or its complement) works for many cases).

Almost always, when trying to do step (1) for an undecidable problem, you will need your program to check **infinite** number of things. This is usually a sign that the problem is not decidable.
> 7 votes

---
Tags: algorithms, computability, graphs, undecidability
---


# Question
Title: How to determine if a database schema violates one of the less known normal forms?
In database normalization, 1NF (no multivalued attributes), 2NF (all non-PK attributes depending only on PK attributes) and 3NF (all non-PK attributes depending on all of the PK attributes) are widely known. The 4NF (no part of the PK depending on other part of the PK) is less known, but still reasonably known.

Much less known are the 5NF, 6NF and the intermediates EKNF (Elementary Key normal form), BCNF (Boyce-Codd normal form - 3.5) and DKNF (Domain/Key normal form - 5.5). What exactly are that? Given a database schema, how do I determine if any table violates one of these much less knows normal forms?

# Answer
> 3 votes
From Wikipedia:

> 1NF: The table faithfully represents a relation and has no repeating groups.
>
> 2NF: Non-prime attributes are non functionally dependent on a proper subset of a candidate key.
>
> 3NF: Non-prime attributes are non-transitively dependent on every candidate key in the table.
>
> BCNF: Every non-trivial functional dependency is a dependency on a superkey.
>
> 4NF: Every non-trivial multivalued dependency in the table is a dependency on a superkey.
>
> 5NF: Every non-trivial join dependency in the table is implied by the superkeys of the table.
>
> DKNF: Every constraint in the table is a logical consequence of the table's domain and key constraints.

Please let me know which, if any, of these requires further explanation. Each provides a means of checking whether a table is in the normal form.

EDIT: Again from Wikipedia:

> A join dependency is a constraint on the set of legal relations over a database scheme. A table $T$ is subject to a join dependency if $T$ can always be recreated by joining multiple tables each having a subset of the attributes of $T$. If one of the tables in the join has all the attributes of the table $T$, the join dependency is called trivial.
>
> The join dependency plays an important role in the Fifth normal form, also known as project-join normal form, because it can be proven that if you decompose a scheme $R$ in tables $R\_1$ to $R\_n$, the decomposition will be a lossless-join decomposition if you restrict the legal relations on $R$ to a join dependency on $R$ called $\*(R\_1,R\_2,...R\_n)$.

In other words, if a constraint on your table $T$ is that `T = R JOIN S` for some tables $R$ and $S$, then $T$ has a join dependency $\*(R, S)$.

---
Tags: database-theory, databases
---


# Question
Title: A sufficient and necessary condition about regularity of a language
> Which of the following statements is correct?
>
> 1. sufficient and necessary conditions about regularity of a language exist but not discovered yet.
> 2. There's no sufficient and necessary condition about regularity of a language.
> 3. Pumping lemma is a necessary condition for non-regularity of a language.
> 4. Pumping lemma is a sufficient condition for non-regularity of a language.

I know #(4) is correct and #(3) is false because "the converse of this statement is not true: a language that satisfies these conditions may still be non-regular", but what can be said about (1) and (2)?

# Answer
> 20 votes
Here are some necessary and sufficient conditions for a language to be regular.

**Theorem.** Let $L\subseteq\Sigma^\*$. The following conditions are equivalent:

* $L$ is generated by a regular expression (i.e., the definition of regular language).
* $L$ is recognized by a nondeterministic finite automaton (Kleene).
* $L$ is recognized by a nondeterministic finite automaton without $\varepsilon$-transitions.
* $L$ is recognized by a deterministic finite automaton (Scott and Rabin).
* $L$ is generated by a grammar $(N,\Sigma,P,S)$, where $N$ is a finite subset of $\Sigma^\*$ (Frazier and Page).
* $L$ is generated by a left (resp. right) regular context-free grammar.
* The index of the Nerode relation $\equiv\_L$ is finite (Anil Nerode, *Linear automaton transformations*, 1958). This is widely (and incorrectly) known as the Myhill-Nerode theorem. $\equiv\_L$ is the relation used to build the minimal DFA of a regular language.
* The index of the Myhill relation $\sim\_L$ is finite (John Myhill, *Finite Automata and the Representation of Events*, 1957). $\sim\_L$ is the relation used to build the syntactic monoid of an arbitrary language.
* The syntactic monoid of $L$ is finite (consequence of Myhill's result). We note here that the syntactic monoid, apart from being defined by using relation $\sim\_L$, can be defined as a minimal monoid (in size) that recognizes $L$ as a preimage of a homomorphism.
* $L$ can be recognized by a read-only Turing Machine (trivial).
* $L$ can be defined by a formula in Monadic second-order logic over strings (Büchi).

If a language does *not* satisfy the conditions of the pumping lemma for regular languages, then it is *not* regular. This means pumping lemma is a sufficient condition for the *non-regularity* of a language.

In summary, statements 1, 2 and 3 are false, while statement 4 is true, as you mentioned.

# Answer
> 10 votes
It is sufficient (and necessary) to show the existence of a DFA, NFA or regular expression to prove that a language is regular, which refutes (1) and (2). To show that a language is not regular it is needed to show that a DFA, NFA or regular expression does not exists.

The pumping lemma is a useful tool to show (possibly by contradiction) that a language is not regular, by showing that no DFA exists.

# Answer
> 7 votes
The condition 'there exists a regular expression that generates exactly $L$' is a necessary and sufficient condition for the regularity of a language $L$, by grace of being its definition.

This condition doesn't exactly make it easy to prove non-regularity of a language though. I'm not aware of any conditions that are easy to check that always prove non-regularity of a non-regular language.

There are two more 'tests' that can prove the non-regularity of a language (though they may not work): you can try to give some regular language such that their union/intersection/difference/concatenation/quotient is non-regular (there are more operations like this), and you can try to count how many words it generates and check if it contradicts the expression for the number of words in a regular language (as can be found on the Wikipedia page you linked).

# Answer
> 7 votes
There is this wonderful connection between formal language theory and formal power series proofed by Chomsky and Schützenberger \[CS63\]. In the form found in \[SS78\] Chap. II, Theorem 5.1

Let $L$ be a regular language and $\mathbb{K}$ a semiring. Then $\mathrm{char}(L)$ is $\mathbb{K}$-rational.

So if you look at the characteristic series $\mathrm{char}(L)$ of a language and it turns out not to be rational, it can’t be a regular language. So you don’t have to use the pumping lemma all the time. With the help of computer algebra systems such a check is not too hard to do.

\[SS78\] Arto Salomaa and Matti Soittola. Automata-Theoretic Aspects of Formal Power Series. Springer-Verlag, New York, 1978.

\[CS63\] Noam Chomsky and Marcel P. Schützenberger. The algebraic theory of context-free languages. In P. Braffort and D. Hirschberg, editors, Computer Programming and Formal Languages, pages 118–161. North Holland, 1963.

# Answer
> 5 votes
By the Myhill-Nerode theorem, a language is regular iff there are finitely many equivalence classes of the indistinguishability relation $I\_{L}$. Two strings $x$ and $y$ are said to be indistinguishable, written $x I\_{L} y$, iff:

1. For all strings $z\_{x}$ such that $xz\_{x} \in L$, also $yz\_{x} \in L$.
2. For all strings $z\_{y}$ such that $yz\_{y} \in L$, also $xz\_{y} \in L$.

Intuitively, this corresponds to the idea that there are finitely many states in the state machine. In fact, the number of distinct equivalence classes under the $I\_{L}$ relation is precisely the number of states in a minimal DFA for $L$.

Myhill-Nerode is especially useful because you can construct positive proofs (the language is regular) and negative proofs (the language isn't regular) using the same framework: the relation $I\_{L}$.

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


# Question
Title: What are the possible sets of word lengths in a regular language?
Given a language $L$, define the length set of $L$ as the set of lengths of words in $L$: $$\mathrm{LS}(L) = \\{|u| \mid u \in L \\}$$

Which sets of integers can be the length set of a regular language?

# Answer
> 15 votes
First, an observation which is not crucial but convenient: the set $\mathscr{S}$ of sets of integers that are $LS(L)$ for some regular language $L$ on a non-empty alphabet $\mathscr{A}$ does not depend on the choice of alphabet. To see that, consider a finite automaton that recognizes $L$; the lengths of the words that are in $L$ are the lengths of the paths on the automaton seen as an unlabeled graph from the start state to any accept state. In particular, you can relabel every arrow to $a$ and get a regular language with the same length set over the alphabet $\\{a\\}$. Conversely, if $L$ is a regular language over a one-element alphabet, it can be trivially injected into a larger alphabet, and the result is still a regular language.

Therefore we are looking for the possible length sets for words over a singleton alphabet. On a singleton alphabet, the language is the length set written out in unary: $\mathrm{LS}(L) = \\{n\in\mathbb{N} \mid a^n \in L\\}$. Such languages are called unary languages.

Let $L$ be a regular language, and consider a deterministic finite automaton (DFA) that recognizes $L$. The set of lengths of words of $L$ is the set of lengths of paths in the DFA seen as a directed graph that start on the start state and end in one of the accept states. A DFA on a one-element alphabet is pretty tame (NFAs would be wilder): it's either a finite list or a circular list. If the list is finite, number the states from $0$ to $h$ following the list order; if it's circular, number the states from $0$ to $h$ following the head of the list, and $h$ to $h+r$ along the loop.

Let $F$ be the set of indices of accept states up to $h$, and $G$ be the set of indices of accept states from $h$ to $h+r$. Then

$$\mathrm{LS}(L) = F \cup \\{ k \\, r + x \mid x \in G, k\in\mathbb{N} \\}$$

Conversely, let $h$ and $r$ be two integers and $F$ and $G$ be two finite sets of integers such that $\forall x \in F, x \le h$ and $\forall x \in G, h \le x \le h+r$. Then the set $L\_{F,G,r} = \\{ a^{k\\,r+x} \mid x\in G, k\in\mathbb{N} \\}$ is a regular language: it is the language recognized by the DFA described above. A regular expression that describes this language is $a^F \mid a^{G} (a^r)^\*$.

To summarize in English, **the length sets of regular languages are the sets of integers that are periodic¹ above a certain value**.

¹ <sub> To hang on to a well-established notion, *periodic* means the characteristic function of the set (which is a function $\mathbb{N}\to\\{\mathtt{false},\mathtt{true}\\}$ which we lift to a function $\mathbb{Z}\to\\{\mathtt{false},\mathtt{true}\\}$) is periodic. Periodic above a certain value means that the function restricted to $\[h,+\infty\[$ can be prolonged into a periodic function. </sub>

# Answer
> 6 votes
Any finite subset $\\{\ell\_1,\ldots,\ell\_n\\}\subset\mathbb{N}$ can be the lenght-set of a regular language $L$, since you can take a unary alphabet $\\{0\\}$ and define $L$ as $\\{0^{\ell\_1},\ldots,0^{\ell\_n}\\}$ (this includes the empty language and $\\{\varepsilon\\}$).

Now for the infinite sets. I'll give a short analysis, though the final answer might not be explicit enough. I won't elaborate unless you ask me to, because I think it's intuitive and because I don't have much time now.

Let $r\_1,r\_2$ be regular expressions generating languages $L\_1$ and $L\_2$, respectively. It is (sort of) easy to see that

* $\mathsf{LS}(L(r\_1+r\_2))=\mathsf{LS}(L\_1\cup L\_2)=\mathsf{LS}(L\_1)\cup\mathsf{LS}(L\_2)$.
* $\mathsf{LS}(L(r\_1r\_2))=\mathsf{LS}(L\_1L\_2)=\\{\ell\_1+\ell\_2:\ell\_1\in\mathsf{LS}(L\_1),\ell\_2\in\mathsf{LS}(L\_2)\\}$. This is denoted $\mathsf{LS}(L\_1)+\mathsf{LS}(L\_2)$.
* $$\mathsf{LS}(L(r\_1^\*))=\\{0\\}\cup\bigcup\_{n\geq 1}\Big\\{\sum\_{i=1}^n\ell\_i:(\ell\_1,\ldots,\ell\_n)\in\big(\mathsf{LS}(L\_1)\big)^n\Big\\}.$$

Thus, the possible sets of integers that can be the length-set of a regular language are the ones that are finite subsets of $\mathbb{N}$ or that can be built by taking finite subsets $S\_1,S\_2$ of $\mathbb{N}$ and using the previous formulas a finite number of times.

Here, we are using that regular languages are built, by definition, by applying the rules for constructing a regular expression a finite number of times. Note that we can start with any finite subset of $\mathbb{N}$, even though in regular expressions we start with words of length 0 and 1 only as the base case. This is easily justified by the fact that all (finite) words are (finite) concatenations of the symbols of the alphabet.

# Answer
> 3 votes
According to the pumping lemma for regular languages, there exists an $n$ such that a string $x$ of length at least equal to $n$ can be written in the following form: $$x = uvw$$ Where the following three conditions hold: $$|uv| \< n$$ $$|v| \> 0$$ $$uv^{k}w \in L$$

This gives us one test for sets: a set cannot be the length set of a regular language unless all its elements can be expressed as some arbitrary set of integers no greater than a fixed $n$, plus some multiple of an undetermined value $m$ (the length of $v$), plus some arbitrary finite value.

In other words, it looks like the possible sets of language lengths for regular languages is the closure with respect to set union (as discussed under EDIT and EDIT2, thanks to commenters) of sets described as follows: $$\\{a + bn | n \in \mathbb{N}\\} \cup S$$ For fixed $a, b \in \mathbb{N}$ and all finite sets $S$, by the pumping lemma for regular languages (thanks to Gilles for pointing out a silly mistake in my original version, whereby I was defining the set $\mathbb{N}$).

EDIT: A little more discussion. Certainly all finite sets of integers are length sets. Also, the union of two length sets must also be a length set, as must be the complement of any length set (hence intersection, hence difference). The reason for this is that the regular languages are closed under these operations. Therefore, the answer I give above is (possibly) incomplete; in reality, any union of such sets is also the length set of some regular language (note that I have abandoned requiring intersection, complement, difference, etc., since these are covered by the fact that regular languages are closed under these properties, as discussed in EDIT3; I think that only union is actually necessary, even if the others are right, which might not be the case).

EDIT2: Even more discussion. The answer I give is basically where you'd end up if you took Janoma's answer a little further; the $bn$ part comes from the Kleene star, the $a$ comes from concatenation, and the discussion of union, intersection, difference and complement come from the + of regular expressions (as well as other closure properties of regular languages) provable starting from automata).

EDIT3: In light of Janoma's comment, let's forget closure properties of language length sets that I discuss in the first EDIT. Since the regular languages have these closure properties, and since every regular language has a DFA, it follows that the pumping lemma for regular languages applies to all unions, intersections, complements, and differences of regular languages, and we'll leave it at that; no need to even consider any of these, except union, which I still think might be necessary to make my original (modified, thanks to input from Gilles) correct. So, my final answer is this: what I say in the original version, plus the closure of language length sets with respect to set union.

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


# Question
Title: Is there a "natural" undecidable language?
Is there any "natural" language which is undecidable?

by "natural" I mean a language defined directly by properties of strings, and not via machines and their equivalent. In other words, if the language looks like $$ L = \\{ \langle M \rangle \mid \ldots \\}$$ where $M$ is a TM, DFA (or regular-exp), PDA (or grammar), etc.., then $L$ **is not** natural. However $L = \\{xy \ldots \mid x \text{ is a prefix of y} \ldots \\}$ is natural.

# Answer
Since you wanted "strings", I mention the classic one: Post Correspondence Problem.
> 24 votes

# Answer
There are many examples but here are a few:

* The set of true sentences in the language of arithmetic is undecidable.
* The set of provable sentences in set theory (ZFC) is undecidable.
* The set of Diophantine equations which have solutions is undecidable.
> 21 votes

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