A Note on Leaf Reduction Theorem for Reversal and Leaf-Bounded Alternating Turing Machines
スポンサーリンク
概要
- 論文の詳細を見る
There have been several studies related to a reduction of the amount of computational resources used by Turing machines. As consequences, "linear speed-up theorem", "tape compression theorem", and "reversal reduction theorem" have been obtained. In this paper, we consider reversal-and leaf-bounded alternating Turing machines, and then show that the number of leaves can be reduced by a constant factor without increasing the number of reversals. Thus our results say that a constant factor on the leaf complexity does not affect the power of reversal- and leaf-bounded alternating Turing machines.
- 一般社団法人電子情報通信学会の論文
- 1993-10-25
著者
-
Miyazaki Takashi
Department Of Animal Science Faculty Of Bioresources Mie University
-
Yamamoto Hiroaki
Faculty Of Engineering Shinshu University
-
Miyazaki Takashi
Department Of Electrical Engineering Nagano National College Of Technology
関連論文
- Radiofrequency Energy Induced Ventricular Fibrillation in a Case of Idiopathic Premature Ventricular Contraction Originating from the Left Ventricular Papillary Muscle
- Combination treatment of tribochemical treatment and phosphoric acid ester monomer of zirconia ceramics enhances the bonding durability of resin-based luting cements
- An Evaluation of the Bending Properties of Glass Fiber Reinforced Plastic Post Materials by a Cantilever Test
- CAD/CAM All Ceramic Dental Restorations on Implants : A Panacea or a Challenge?
- Efficacy of experimental dual-cure resin cement for orthodontic direct bond system
- Properties of a gypsum-bonded magnesia investment using a K_2SO_4 solution for titanium casting
- A Gypsum-Bonded Magnesia Investment is Available for Titanium Casting
- The Possibility of Fabricating Co-Cr Casting Plates by Using a Heat-Shock Method with Conventional Phosphate-Bonded Investments
- Two-stage Heat-Shock Procedure Can Fabricate Sound Co-Cr Casting Denture Plates by Using Conventional Phosphate-Bonded Investments
- Fabrication of Nanometer-Scale Pattern Using Current-Controlled Scanning Probe Lithography
- Tail-suspension Induces Altered Expression of GAPDH and ZAKI-4β mRNAs in Rat Hindlimbs : Implication for Disuse Muscle Atrophy
- Experimental Binder-free Investments Reused to Cast Dental Precious Alloys
- Effect of Varying HAP/TCP Ratios in Tape-cast Biphasic Calcium Phosphate Ceramics on Response in vitro
- Experimental Paste-paste Type Phosphate-bonded Investment with Colloidal Silica Solution
- Effect of Sintering on the Marginal and Internal Fit of CAD/CAM-fabricated Zirconia Frameworks
- Bonding Strength of Resin Cement to Silicate Glass Ceramics for Dental CAD/CAM Systems is Enhanced by Combination Treatment of the Bonding Surface
- Current Status and Future Prospects of a Dental CAD/CAM System Used in Crown-bridge Restorations
- Fracture Toughness Measurement of Dental Ceramics Using the Indentation Fracture Method with Different Formulas
- Recycling of Used Commercial Phosphate-bonded Investments with Additional Mono-ammonium Phosphate
- Machining Accuracy of CAD/CAM Ceramic Crowns Fabricated with Repeated Machining Using the Same Diamond Bur
- Durability of Tungsten Carbide Burs for the Fabrication of Titanium Crowns using Dental CAD/CAM
- Characterization of InGaAs Phosphidized by a Plasma Process
- Investigation of Linearity of Photoacoustic Characteristics on Semiconductors Measured by Michelson Interferometry : Photoacoustic Spectroscopy
- Electric Field Effect on Subband State Transitions Peaks in the Photoluminescence from a GaAlAs Quantum Well Structure
- Measurement of the Degree of Cure for Resin-Modified Glass Ionomer Cements by IR Spectroscopic Analysis
- Durability of Resin-Modified Glass Ionomer Cements after Long Term Water Immersion
- Resin Content in Cement Liquids of Resin-Modified Glass Ionomers
- Dentinal Tubule Densities in Human and Bovine Coronal Dentin
- Chemical Analysis of Coronal and Radicular Dentin using Fourier Transform Infrared Spectroscopy
- Comparison of nanohardness between coronal and radicular intertubular dentin
- Durability of Diamond Burs for the Fabrication of Ceramic Crowns Using Dental CAD/CAM
- The mechanical properties of dental thermoplastic materials in a simulated intraoral environment
- STRUCTURE AND DEVELOPMENTAL EXPRESSION PROFILES OF CHICKEN GHRELIN GENE
- IB-19 The changes of intercellular gap junction in rat parotid gland by clipping and reopening of parotid duct(THE 46TH ANNUAL MEETING OF THE JAPAN SOCIETY OF HISTOCHEMISTRY AND CYTOCHEMISTRY)
- Factors Affecting the Bonding of Silicoater MD System for Resin Veneering to Cp Titanium
- A Fully Photoreversible Supramolecular Polymer Having a Diarylethene Photoswitch
- Experimental Ammonia-free Phosphate-bonded Investments Using Mg(H_2PO_4)_2
- Labor Reduction for Mold Preparation of a Commercial Titanium Cast Denture System Using a Heat-shock Method
- Altered bone turnover in chlorpromazine-challenged rats and its effect on 1α-hydroxyvitamin D_3 administration in vivo
- Non-Kramer's Doublet Ground State in PrPtBi
- Vibrio Vulnificus-necrotizing Fasciitisin Patient with Cirrhosis
- Micro-CT Based Quantitative Evaluation of In Vivo Bone Regeneration with Collagen-based Biomaterials
- MOLECULAR CHARACTERIZATION OF CHICKEN GROWTH HORMONE SECRETAGOGUE RECEPTOR
- Plasma interleukin-8 levels are increased by hemodialysis using regenerated cellulose.
- Tensile Strength and Durability of Bovine Dentin
- Serous cystadenocarcinoma of the pancreas with liver metastases
- Novel fabrication method for zirconia restorations : Bonding strength of machinable ceramic to zirconia with resin cements
- Bit-Parallel Algorithms for Translating Regular Expressions into NFAs(Automata,Foundations of Computer Science)
- Colloidal β-Tricalcium Phosphate Prepared by Discharge in a Modified Body Fluid Facilitates Synthesis of Collagen Composites
- Investigation of the Sol-Gel Process with Experimental Paste-Type Dental Phosphate-bonded Investments
- Soda-lime glass as a binder in reusable experimental investment for dental castings
- Effects of pre-meal versus post-meal administration of miglitol on plasma glucagon-like peptide-1 and glucose-dependent insulinotropic polypeptide levels in healthy men
- A Note on Leaf Reduction Theorem for Reversal and Leaf-Bounded Alternating Turing Machines
- Micro-CT evaluation of in vivo osteogenesis at implants processed by wire-type electric discharge machining
- Effects of miglitol, sitagliptin or their combination on plasma glucose, insulin and incretin levels in non-diabetic men
- Fatigue and Fracture Observations of Radicular Dentin
- Enhanced osteoblast response to electrical discharge machining surface
- Production of a calcium silicate cement material from alginate impression material
- Effects of a convenient silica-coating treatment on shear bond strengths of porcelain veneers on zirconia-based ceramics
- Properties of experimental titanium cast investment mixing with water reducing agent solution
- Fabrication of a Nanogap on a Metal Nanowire Using Scanning Probe Lithography
- Nanoscale Electrical Properties of Molecular Films in the Vicinity of Platinum Ultrathin Film Electrode
- One-bottle silane coupling agent containing 4-META
- A Resected Case of Pancreatic Metastasis from Primary Renal Cell Carcinoma.
- D-4-1 Searching an Encrypted XML Document Using Keywords
- Pseudomyxoma Peritonei. A Report of Three Cases and a Review of Published Reports.:A Report of Three Cases and a Review of Published Reports
- Nonfunctioning Islet Cell Carcinoma. A Twenty-One Years Survival Case after Distal Pancreatectomy.:A Twenty-One Years Survival Case after Distal Pancreatectomy
- Fabrication of Nanogap Electrodes Using Ultrathin Metal Film
- Jejunal Varices as a Cause of Massive Gastrointestinal Bleeding. A Case Report.:A Case Report
- One-bottle silane coupling agent containing 4-META