[Solved]: How powerful is a k-stack pushdown automaton with a unary stack alphabet?

Problem Detail: 

I'm interested in pushdown automata with a unary stack alphabet: let's call them UPDA's. Define a $k$-UPDA to be a pushdown automaton with $k$ stacks, each with a unary stack alphabet.

I've figured out that a $k$-UPDA is at least as powerful as a $(k-1)$-PDA (see proof at the end). This implies that a $k$-UPDA is equivalent in power to a Turing machine when $k \ge 3$ (as it is at least as powerful as a Turing machine when $k \ge 3$, as you can simulate a TM with a 2-PDA, and by the Church-Turing thesis, no more powerful).

A 1-UPDA is more powerful than a NFA/DFA, as a 1-UPDA can recognize, for instance, the language $\{0^n1^n:n \in \mathbb{N}\}$. But, at the same time I suspect (although I do not know) that a 1-UPDA is less powerful than a 1-PDA.

My questions are as follows:

1. What is the complexity class recognized by a 1-UPDA? Or at the very least, are there better bounds than "more powerful than a NFA/DFA and no more powerful than a 1-PDA"?
2. What is the complexity class recognized by a 2-UPDA? Or at the very least, are there better bounds than "at least as powerful than a 1-PDA and no more powerful than a 2-PDA"? In particular, is a 2-UPDA more powerful than a 1-PDA?
3. Is there a $k$ such that you can simulate a TM with a $k$-UPDA without exponential overhead?
4. Is there a standard name for a UPDA?

---

Proof that a $k$-UPDA can simulate a $(k-1)$-PDA: use one stack for scratch space. You emulate a stack alphabet of $m$ symbols with a unary number, base $m$. To push a number $x$ to a stack, you multiply the number of elements in the stack by $m$ and then push $x$ more symbols. (You also need to check for if the stack is empty, but that is simple enough.) To pop a number, you modulo the stack by $m$ for the number to pop, and divide the number of symbols in the stack by $m$.

Asked By : TLW

Answered By : Hendrik Jan

Such automata are called counter-automata. Each counter holds a natural number, which can be tested for zero. (So your UPDA has a single stack symbol plus a way to recognize the empty stack.)

Two push-downs are Turing complete, i.e., they can compute any Turing computable function. Basically, because two stacks can simulate a queue. So you have proved yourself that 3-UPDA is Turing complete. But actually two counters are enough. The trick is to code two numbers $(i,j)$ into a single number $2^i 3^j$ and doing your own construction again.

The family of languages is called one-counter languages, which have some fame in formal language theory. I browsed my own old answers and found: Which languages are recognized by one-counter machines?

Also: The simulation of TM's by counter automata is explained in the old textbook by Hopcroft and Ullman (Intro to Automata Theory, Languages, ...) in two steps. First using four counters and coding the contents of (half of) a working tape of a TM by a single number. The result is attributed to Minsky (1961).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/47902

3.2K people like this

 Download Related Notes/Documents