Questions tagged [counter-automata]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
17
votes
2answers
438 views

Unary languages recognized by two-way deterministic counter automata

2dca's (two-way deterministic one-counter automata) (Petersen, 1994) can recognize the following unary language: \begin{equation} \mathtt{POWER} = \lbrace 0^{2^n} \mid n \geq 0 \rbrace. \end{...
14
votes
1answer
349 views

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

Can a standard two counters ($c_1,c_2$) machine with the following instructions: ...
11
votes
1answer
259 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 ...
11
votes
0answers
158 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, ...
8
votes
1answer
321 views

Two way deterministic multihead counter automata or logspace TM with counter

Is that known something about languages recognized by two-way deterministic multihead counter automaton or logspace TM with counter (equivalent model)? This class called Aux2DC in my advisor's paper. ...
6
votes
1answer
238 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 ...
5
votes
2answers
160 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 ...
2
votes
1answer
91 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 ...
2
votes
1answer
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 ...
0
votes
0answers
60 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. ...