Wyniki wyszukiwania - BazTech

Ograniczanie wyników

2 Fundamenta Informaticae

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

A Survey of Results on Stateless Multicounter Automata

Ibarra O.H., Egecioglu Ö.

Fundamenta Informaticae

2012

Vol. 116, nr 1-4

129-140

A stateless multicountermachine hasm-counters operating on a one-way input delimited by left and right end markers. A move of the machine depends only on the symbol under the input head and the sign pattern of the counters. An input string is accepted if, when the input head is started on the left end marker with all counters zero, themachine eventually reaches the configurationwhere the input head is on the right end marker with all the counters again zero. We bring together a number of results on stateless multicounter automata of various different types: deterministic, nondeterministic, realtime (the input head moves right at every step), or non-realtime. We investigate realtime and non-realtime machines in both deterministic and nondeterministic cases with respect to the number of counters and reversals. In addition to hierarchy results, we also consider closure properties and the connections to stateless multihead automata.

Hierarchies of Stateless Multicounter 5' → 3' Watson-Crick Automata Languages

Egecioglu Ö., Hegedüs L., Nagy B.

Fundamenta Informaticae

2011

Vol. 110, nr 1-4

111-123

We consider stateless counter machines which mix the features of one-head counter machines and a special type of two-head Watson-Crick automata (WK-automata). Our Watson-Crick counter machines are biologically motivated. They have two heads that read the input starting from the two extremes. The reading process is finished when there are no more symbols between the heads, i.e., every letter of the input is processed by either head. Depending on whether the heads are required to advance at each move, we distinguish between realtime and non-realtime machines. If every counter makes at most k alternations between nondecreasing and decreasing modes in every computation, then the machine is k-reversal. It is reversal bounded if it is k-reversal for some k. In this paper we concentrate on the properties of both deterministic and nondeterministic stateless WK-automata with reversal bounded counters.