Electronic Resource
Springer
Acta informatica
17 (1982), S. 63-67
ISSN:
1432-0525
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Notes:
Summary Let L b = {w 1 *...* w 2b ¦w i is in {0,1}* and w i = w 2b+1−i for 1≦i≦2b for b≧1. We show that the language L b is not recognizable by any nondeterministic one-way k-head stack-counter automata if $$b 〉 \left( {\begin{array}{*{20}c} k \\ 2 \\ \end{array} } \right)$$ . As a corollary, we show that k+1 heads are better than k for one-way multihead stack-counter automata.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF00262976
Permalink
|
Location |
Call Number |
Expected |
Availability |