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:
- 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"?
- 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?
- Is there a $k$ such that you can simulate a TM with a $k$-UPDA without exponential overhead?
- 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$.
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. $\endgroup$