The tag has no wiki summary.

learn more… | top users | synonyms

6
votes
1answer
196 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 ...
14
votes
1answer
240 views

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

Can a standard two counters ($c_1,c_2$) machine with the following instructions: ...
10
votes
1answer
175 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 ...
2
votes
1answer
77 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 ...
6
votes
1answer
177 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. ...
17
votes
2answers
371 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. ...