A Note on Reversal Complexities of Real-Time Counter Machines

Hiroshi MATSUNO  Katsushi INOUE  Itsuo TAKANAMI  Hiroshi TANIGUCHI  

Publication
IEICE TRANSACTIONS (1976-1990)   Vol.E69   No.8   pp.838-839
Publication Date: 1986/08/25
Online ISSN: 
DOI: 
Print ISSN: 0000-0000
Type of Manuscript: LETTER
Category: Automata and Languages
Keyword: 


Full Text: PDF>>
Buy this Article




Summary: 
This paper gives a hierarchical property on the number of reversals of real-time counter machines. That is, we show that for any k1, a real-time counter machine with 2k+1 reversals is more powerful than one with k reversals.