Name
Abstract | ||
|---|---|---|
Among the many models of language acceptors that have been studied in the literature are multihead finite automata (finite automata with multiple one-way input heads) and 1-reversal counter machines (finite automata with multiple counters, where each counter can only "reverse" once, i.e., once a counter decrements, it can no longer increment). The devices can be deterministic or nondeterministic and can be augmented with a pushdown stack. We investigate the relative computational power of these machines. Our results (where C1 and C2 are classes of machines) are of the following types: 1. Machines in C1 and C2 are incomparable. 2. Machines in C1 are strictly weaker than machines in C2. In obtaining results of these types, we use counting and "cut-and-paste" arguments as well as an interesting technique that shows that if a language were accepted by a device in a given class, then all recursively enumerable languages would be decidable. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1016/j.tcs.2012.04.002 | Theor. Comput. Sci. |
Keywords | Field | DocType |
bounded language,finite automaton,multiple one-way input head,multihead finite automaton,1-reversal counter machine,interesting technique,deterministic counter machine,multihead automaton,counter machine,following type,recursively enumerable language,multiple counter,language acceptors,counter decrement,one-reversal counter machine,language acceptor,non-deterministic counter machine,one-way multihead finite automaton,finite automata | Discrete mathematics,Quantum finite automata,Automata theory,Mobile automaton,Nondeterministic algorithm,Nested word,Computer science,Deterministic finite automaton,Recursively enumerable language,Finite-state machine,Theoretical computer science | Journal |
Volume | ISSN | Citations |
454 | 0302-9743 | 4 |
PageRank | References | Authors |
0.44 | 18 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ehsan Chiniforooshan | 1 | 118 | 16.38 |
| Mark Daley | 2 | 166 | 22.18 |
| Oscar H. Ibarra | 3 | 377 | 59.46 |
| Lila Kari | 4 | 1123 | 124.45 |
| Shinnosuke Seki | 5 | 189 | 29.78 |