Episode #125 of the Stack Overflow podcast is here. We talk Tilde Club and mechanical keyboards. Listen now

# Questions tagged [counter-automata]

The tag has no usage guidance.

10 questions
Filter by
Sorted by
Tagged with
58 views

### Language recongized by a “quasi realtime register machine”?

Counter machines are very powerful. Even two counters suffice for making these Turing complete. But, in simulating a Turing machine the counter machine encodes in its integers a large amount of data. ...
136 views

### Can two-tape read-only Turing machines recognize any recursive language?

Suppose that a $k$-tape read-only Turing machine receives its input on each $k$ tapes. It cannot write on the tapes, but it can move on them in both ways, even move off from the input. So for example, ...
88 views

### Can a det. $k$-counter machine ($k \geq 2$) be simulated by a det. $k'$-counter machine using non-$\epsilon$-moves followed by $\epsilon$-moves?

I have a question concerning deterministic $k$-counter machines, for $k \geq 2$. Recall that in this context, the determinism is expressed by the fact that the machine can never face a choice between ...
156 views

### Can real-time deterministic multicounter automata recognize the marked palindrome language?

Consider the marked palindrome language which is defined as MPAL=$\{ w\#w^r | w \in \{a,b\}^* \}$. It is easy to recognize MPAL using only a single stack. My question is whether MPAL can be ...
237 views

### Halting time of non deterministic machine

Let $K$ be a non deterministic machine. I use Minsky Machine (2 counter automaton) for practical reason in my research, but it could be a turing machine, a register machine, whatever. The Machine ...
326 views

### Can a two counters machine decide $n^2$?

Can a standard two counters ($c_1,c_2$) machine with the following instructions: ...
250 views

### Can one-way alternating automata with one-counter recognize some unary non-regular languages?

One-way alternating pushdown automata (1APDA) can recognize any language in $DTIME(2^{O(n)})$ (Alternation by Chandra, Kozen, and Stockmeyer, 1981). By replacing a pushdown storage of a 1APDA with a ...
97 views

### Are Reversal-bounded Multicounter Machines closed under reversal?

This is a problem I have found very difficult to solve, given how the two different uses of "reversal" confuses search engines. Reversal-bounded multicounter machines are described at length in his ...