4
$\begingroup$

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

Improve this question
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – D.W. ♦
    Oct 5, 2015 at 18:28
  • $\begingroup$ I have done so, and thank you. I am not exactly a master of LaTEX. $\endgroup$
    – TLW
    Oct 5, 2015 at 18:53
  • 1
    $\begingroup$ 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 $\endgroup$
    – jmite
    Oct 5, 2015 at 20:52

1 Answer 1

Reset to default
4
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thank you very much! That's a very neat trick indeed. I'll have to sit down sometime I have some more time and work it out, but I see the general idea at least. This answers the second part of my question. Do you know about what can and cannot be simulated by a 1-counter automaton? Or the third part of my question? $\endgroup$
    – TLW
    Oct 5, 2015 at 20:44
  • $\begingroup$ Why do you think the overhead is exponential? $\endgroup$
    – Hendrik Jan
    Oct 6, 2015 at 0:51
  • $\begingroup$ For instance, if a binary TM writes a one then moves right for N moves, you push a value N times onto the left stack of the stack machine emulating it, which means you multiply your initial value of 1 in the first counter by 2, N times, in the counter machine emulating the stack machine, so you get a value of 2^N at the end in the left counter. And a counter machine can only increment by 1 - so it must increment (at least) 2^N times. (For the two-counter machine this case is even worse - doubly-exponential!) $\endgroup$
    – TLW
    Oct 8, 2015 at 20:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.