# How powerful is a k-stack pushdown automaton with a unary stack alphabet?

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$.

• I've edited your question to try to make it clearer. Check that I didn't mess anything up. For the future: I suggest that you define all acronyms before first use (e.g., what's a UPDA? what's a $k$-UPDA?). Please don't use backticks for emphasis; they are intended only for code. Instead, it's better to use Latex to typeset mathematics in a more readable way. See here for a short introduction. – D.W. Oct 5 '15 at 18:28
• I have done so, and thank you. I am not exactly a master of LaTEX. – TLW Oct 5 '15 at 18:53
• You might also be interested in reversal bound counter automata, which are a limited versions of the machines you describe, with many decidable properties: lsv.ens-cachan.fr/~demri/Ibarra78.pdf – jmite Oct 5 '15 at 20:52

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.