Linked Questions

7
votes
3answers
5k views

Why do pushdown automata use a stack?

I'm taking a computer theory class and my professor told us that a pushdown automaton cannot use data structures other than a stack (like a queue or multiple stacks). Why is that?
7
votes
2answers
793 views

Is a stack machine with a forward read iterator Turing complete?

It is well known that a machine with a single stack as only unlimited storage is not Turing complete, if it can only read from the top of the stack. I want a machine which is (slightly) more powerful ...
3
votes
1answer
3k views

How can one simulate a PDA with a FIFO queue PDA?

I'm trying to figure out how a pushdown automata (PDA), which we know uses a stack (LIFO) can be simulated by a queue (FIFO). I understand that in a regular PDA, we only have access to the top most ...
15
votes
1answer
1k views

Computational power of deterministic versus nondeterministic min-heap automata

This is a follow-up question of this one. In a previous question about exotic state machines, Alex ten Brink and Raphael addressed the computational capabilities of a peculiar kind of state machine: ...
16
votes
1answer
534 views

Proving closure under reversal of languages accepted by min-heap automata

This is a follow-up question of this one. In a previous question about exotic state machines, Alex ten Brink and Raphael addressed the computational capabilities of a peculiar kind of state machine: ...
10
votes
1answer
654 views

How to prove that ε-loops are not necessary in PDAs?

In the context of our investigation of heap automata, I would like to prove that a particular variant can not accept non-context-sensitive languages. As we have no equivalent grammar model, I need a ...
8
votes
1answer
593 views

Proving closure under complementation of languages accepted by min-heap automata

This is a follow-up question of this one. In a previous question about exotic state machines, Alex ten Brink and Raphael addressed the computational capabilities of a peculiar kind of state machine: ...
5
votes
2answers
189 views

Computational power of nondeterministic type-1 min-heap automata with multiple heaps

I have asked a series of questions concerning capabilities of a certain class of exotic automata which I have called min-heap automata; the original question, and links to others, can be found here. ...
4
votes
1answer
201 views

Are there grammar classes between Chomsky level 1 and 2?

Are there any grammar classes which are true subsets of Chomsky level 2 but not equal to level 1?
4
votes
1answer
143 views

Power of nondeterministic type-1 min-heap automaton with both a heap and a stack

I have asked a series of questions concerning capabilities of a certain class of exotic automata which I have called min-heap automata; the original question, and links to others, can be found here. ...
4
votes
0answers
102 views

Computational power of nondeterministic type-2 min-heap automata

I have asked a series of questions concerning capabilities of a certain class of exotic automata which I have called min-heap automata; the original question, and links to others, can be found here. ...