On the Power of Reversals Over the Input Tape of Off-Line Turing Machines

スポンサーリンク

概要

• 論文の詳細を見る

• For reversal complexity on an off-line Turing machine, which is a Turing machine with a read-only two-way input tape except work-tapes, we can consider two kinds of definition; the first one is a definition in which the number of reversals over the input tape is not counted, and the second one is a definition in which it is counted. Unlike time and space complexities, whether or not there is any difference between these two definitions does not seem to be trivial. In this paper, we will show the following results: (1) let S(n) be any function, and R(n) be an (R(n), S(n)) reversal-space constructible function. Then, DRESP_k (R(n), S(n))⫅ IDRESP_<k+2>(R(n)+log(nS(n)), n^2R(n)S(n)), (2) let R(n) and S(n) be any functions. Then, NRESP_k (R(n), S(n)) ⫅ INRESP_<k+1>(R(n), n^2S(n)), and ARESP_k(R(n), S(n))=IARESR_k(R(n), S(n)), where DRESP denotes a deterministic reversal- and space-bounded class under the definition disregarding reversals over the input tape, and IDRESP denotes a deterministic reversal-and space-bounded class under the definition counting it. The suffix k denotes the number of work-tapes. The classes NRESP, INRESP, ARESP and IARESP are also defined similarly for NTMs and ATMs.

• 社団法人電子情報通信学会の論文
• 1996-11-25

著者

• YAMAMOTO Hiroaki

  Department of Astrophysics, Nagoya University

• Yamamoto Hiroaki

  Department Of Astrophysics Nagoya University

• Yamamoto H

  Shinshu Univ. Nagano Jpn

関連論文

• Discovery of Molecular Loop 3 in the Galactic Center : Evidence for a Positive-Velocity Magnetically Floated Loop towards L=355°-359°
• Similarity between the Molecular Loops in the Galactic Center and the Solar Chromospheric Arch Filaments
• A Peculiar Jet and Arc of Molecular Gas toward the Rich and Young Stellar Cluster Westerlund 2 and a TeV Gamma Ray Source
• Aligned Molecular Clouds towards SS 433 and L = 348°.5 : Possible Evidence for a Galactic "Vapor Trail" Created by a Relativistic Jet
• Discovery of Interacting Molecular Gas toward the TeV Gamma-Ray Peak of the SNR G 347.3-0.5
• A Large Scale ^CO (J = 1-0) Survey toward the Chamaeleon Region with NANTEN
• A Large-Scale Study of H^CO^+and C^O (J = 1-0) in Orion B
• A Survey for High-Latitude Molecular Clouds toward Infrared-Excess Clouds with NANTEN
• Temperature and Density in the Foot Points of the Molecular Loops in the Galactic Center ; Analysis of Multi-J Transitions of ^CO (J = 1-0, 3-2, 4-3, 7-6), ^CO (J = 1-0), and C^O (J = 1-0)
• NANTEN Survey of Molecular Clouds toward the Galactic Center ; Association of Compact Astronomical Objects
• Warm and Dense Molecular Gas in the N 159 Region : ^CO J = 4-3 and ^CO J = 3-2 Observations with NANTEN2 and ASTE
• Augmented Chemosensitivity in Black-Eyed White Mitf^ Mice, Lacking Melanocytes
• Location of Catalytic Head Group of 2-Hydroxymethylimidazole・Cu^ Complex on the Micellar Surface of Anionic SDS in the Hydrolysis of p-Nitrophenyl Picolinate
• A genome-wide survey of genes for enzymes involved in pigment synthesis in an ascidian, Ciona intestinalis
• Formation of Galactic Center Magnetic Loops
• Aneurysm in the Pulmonary Trunk Associated With Atrial Septal Defect, a Left Coronary Artery Fistula to the Pulmonary Trunk, and Valvular Pulmonary Stenosis
• Molecular Clouds as Cosmic-Ray Barometers
• Variations of transition zone volume and transition zone index after transureghral needle ablation for symptomatic benign prostatic hyperplasia
• Relative Partial Molar Gibbs Energy of Magnesium Component Substituted into Zinc Site in the Mg-Zn Binary Compounds
• THE ANTISPERMATOGENIC EFFECT AND TOXICITY OF 2,4-DINITRO-6-TERT BUTHYLPHENYL METHANESULFONATE ON SPRAGUE-DAWLEY RAT
• On the Power of Reversals Over the Input Tape of Off-Line Turing Machines
• The Structural Organization of Ascidian Halocynthia roretzi Troponin I Genes
• Standard Gibbs Energy of Formation of Mg_3La Determined by Solution Calorimetry and Heat Capacity Measurement from Near Absolute Zero Kelvin
• Determination of Standard Gibbs Energy of Formation of Al_2Nd by Solution Calorimetry and Heat Capacity Measurement from Near Absolute Zero Kelvin
• Standard Gibbs Energy of Formation of Zn_8La Determined by Solution Calorimetry and Measurement of Heat Capacity from Near Absolute Zero Kelvin
• GENE EXPRESSION PROFILES OF ASCIDIAN PIGMENT CELLS(Genetics)(Proceedings of the Seventy-Third Annual Meeting of the Zoological Society of Japan)
• TUMORIGENESIS AND CYSTIC LESION OF THE LIVER BY N-BIS (2-HYDROXYPROPYL) NITROSAMINE IN DDY MICE
• PE-196 The Effectiveness of Additional Creation of Extensive Inner Low Voltage Region within the Line of Circumferential Pulmonary Vein Ablation(PE033,Arrhythmia, Others (Clinical/Diagnosis/Treatment) 3 (A),Poster Session (English),The 73rd Annual Scienti
• OJ-090 Clinicopathological Studies of Mitochondrial Cardiomyopathy with Special Reference to Predominant Epicardial Involvement Presented by MRI Delayed Images and Autopsies(OJ15,Cardiomyopathy/Hypertrophy (Clinical) (M),Oral Presentation (Japanese),The 7
• OE-071 Significance of Wavefront Phenomenon in Acute Myocardial Infarction Documented by MRI Delayed Image(OE12,ACS/AMI (Clinical/Pathophysiology) (IHD),Oral Presentation (English),The 73rd Annual Scientific Meeting of The Japanese Circulation Society)
• PE-492 Hyperglycemia is More Important than Metabolic Syndrome on the Pathogenesis of Diabetic Coronary Artery Disease(Diabetes/Obesity/Metabolic syndrome-07, The 71st Annual Scientific Meeting of the Japanese Circulation Society)
• PE-194 Role of Insulin Resistance on the Pathogenesis of Diabetic Atherosclerosis(Atherosclerosis, clinical-04, The 71st Annual Scientific Meeting of the Japanese Circulation Society)
• PE-029 Mechanisms of WPW syndrome and short PR syndrome seen in Mitochondrial Cardiomyopathy(Arrhythmia, Diagnosis/Pathophysiology/EPS 6 (A) : PE5)(Poster Session (English))
• An Improved Method to Extract Quasi-Random Sequences from Generalized Semi-Random Sources
• MITF CONTRIBUTES TO THE DENDRICITY OF MELANOBLASTS IN XENOPUS LAEVIS(Developmental Biology,Abstracts of papers presented at the 75^ Annual Meeting of the Zoological Society of Japan)
• FUNCTIONAL ANALYSES OF MITF GENE IN XENOPUS PIGMENT CELLS(Developmental Biology,Abstracts of papers presented at the 74^ Annual Meeting of the Zoological Society of Japan)
• Effects of a Tensor Force on ψ Family in the Charmonium Model. II
• Effects of the Tensor Force on ψ'and χ's in the Charmonium Model
• Modeling the Gamma-Ray Emission Produced by Runaway Cosmic Rays in the Environment of RX J1713.7-3946
• A Detailed Observational Study of Molecular Loops 1 and 2 in the Galactic Center
• Theoretical Study of Resonant Tunneling Transmission Characteristics in Symmetrical Rectangular Quadruple-Barrier Structures with Deep Wells
• OTX2 ACTIVITY SPECIFIES THE OUTER LAYER OF THE OPTIC CUP(Developmental Biology,Abstracts of papers presented at the 75^ Annual Meeting of the Zoological Society of Japan)
• Modeling Implicit Surfaces with Proliferating Sample Points
• P253 PRE-HOSPITAL PHASE PATHOPHYSIOLOGY AND PROGNOSIS OF SUDDEN CARDIAC DEATH AND ACUTE MYOCARDIAL INFARCTION WHO WERE ADMITTED AS CARDIOPULMONARY ARREST
• TRAUMATIC RIGHT-SIDED DIAPHRAGMATIC HERNIA : A CASE REPORT AND REVIEW OF JAPANESE CASES
• New Parametrizations for Q^2-Dependent Parton Distribution Functions. I
• Heat Capacity of La_Sr_XFeO_ from 2K to 1340K
• Preparation of White Heart Malleable Cast Iron in Na_2O-K_2O-SiO_2 Oxide Molten Salt
• Preparation of White Heart Malleable Cast Iron in Na_2O-SiO_2 Oxide Molten Salt
• Real Photon to Neutral Pion Ratios and Photon-Jet Correlations in Quantum Chromodynamics
• Altarelli-Parisi Equation Including Photon
• AMYLOIDOSIS IN ddY MICE PRODUCED BY PAINTING WITH DINITROFLUOROBENZENE
• High Excitation Molecular Gas in the Galactic Center Loops ; ^CO (J=2-1 and J=3-2) Observations
• The Effectiveness of the Ablation Method for Chronic Atrial Fibrillation Extending the Pulmonary Vein Isolation Line into Atrial Septum
• Significance of Termination of Atrial Fibrillation during the Procedure of Catheter Ablation
• Resonant Tunneling Transmission Characteristics and Tunneling Time in Asymmetrical Double-Barrier Structures with Multiple Prewells

もっと見る 閉じる

スポンサーリンク