Some Observations Concerning Alternating Pushdown Automata with Sublogarithmic Space
スポンサーリンク
概要
- 論文の詳細を見る
This paper first investigates a relationship between inkdot-depth and inkdot-size of inkdot two-way alternating Turing machines and pushdown automata with sublogarithmic space, and shows that there exists a language accepted by a strongly log log n space-bounded alternating pushdown automaton with inkdot-depth 1, but not accepted by any weakly o(log n) space-bounded and d(n) inkdot-size bounded alternating Turing machine, for any function d(n) such that lim_<n→∞> [d(n)・log n/n^<1/2>] = 0. In this paper, we also show that there exists an infinite space hierarchy among two-way alternating push-down automata with sublogarithmic space.
- 社団法人電子情報通信学会の論文
- 1997-12-25
著者
-
ITO Akira
Department of Physics, The Cancer Institute, Japanese Foundation for Cancer Research
-
INOUE Katsushi
Department of Computer Science and Systems Engineering, Faculty of Engineering, Yamaguchi University
-
Inoue Katsushi
The Department Of Computer Science And Systems Engineering Faculty Of Engineering Yamaguchi Universi
-
Inoue Katsushi
Department Of Computer Science And Systems Engineering Faculty Of Engineering Yamaguchi University
-
Inoue K
The Department Of Computer Science And Systems Engineering Faculty Of Engineering Yamaguchi Universi
-
Xu J‐l
Nec Software Ltd.
-
Wang Y
Media And Information Technology Center Yamaguchi University
-
Wang Yue
Faculty Of Engineering Yamaguchi University
-
Wang Yue
Department Of Computer Science University Of Tokyo
-
Xu Jianliang
Department Of Computer Science Ocean University Of China
-
Ito A
The Department Of Computer Science And Systems Engineering Faculty Of Engineering Yamaguchi Universi
-
Ito Akira
Dep. Of Chemical Engineering Fac. Of Engineering Kyushu Univ. 744 Motooka Nishi-ku Fukuoka 819-0395
-
Inoue Katsushi
Department Of Electronics Engineering
-
Xu Jianliang
Department Of Computer Science And Systems Engineering Faculty Of Engineering Yamaguchi University
-
Ito A
Kyorin Pharmaceutical Co. Ltd.
-
Ito Akira
Department Of Biochemistry And Molecular Biology School Of Pharmacy Tokyo University Of Pharmacy And
-
Wang Yue
Department Of Applied Chemistry Beijing Institute Of Petrochemical Technology
関連論文
- Non-closure Property of One-Pebble Turing Machines with Sublogarithmic Space(Discrete Mathematics and Its Applications)
- Dosimetric consideration of individual ^I source strength measurement and a large-scale comparison of that measured with a nominal value in permanent prostate implant brachytherapy
- Preparation of artificial skeletal muscle tissues by a magnetic force-based tissue engineering technique(CELL AND TISSUE ENGINEERING)
- Anti-arthritic Action Mechanisms of Natural Chondroitin Sulfate in Human Articular Chondrocytes and Synovial Fibroblasts
- The Citrus Flavonoid, Nobiletin, Inhibits Peritoneal Dissemination of Human Gastric Carcinoma in SCID Mice
- Nobiletin (citrus flavonoid) inhibits the production of MMP-9 and peritoneal metastasis of gastric carcinoma in SCID mice
- Current Situation of Taeniasis and Cysticercosis in Indonesia
- E-cadherin gene-engineered feeder systems for supporting undifferentiated growth of mouse embryonic stem cells(CELL AND TISSUE ENGINEERING)
- Effects of Liquid Property on Air Entrainment and Oxygen Transfer Rates of a Plunging Jet Reactor
- Maximum Penetration Depth of Air Bubbles Entrained by Vertical Liquid Jet
- Effect of Nozzle Contraction Angle on Air Entrainment Rate of a Vertical Plunging Liquid Jet
- Mag-Seeding of Rat Bone Marrow Stromal Cells into Porous Hydroxyapatite Scaffolds for Bone Tissue Engineering(CELL AND TISSUE ENGINEERING)
- Effective Cell-Seeding Technique Using Magnetite Nanoparticles and Magnetic Force onto Decellularized Blood Vessels for Vascular Tissue Engineering(CELL AND TISSUE ENGINEERING)
- MEK1/2 and PKC β II/ε Are Target Molecules for Nobiletin-Induced Suppression of ProMMP Production and Augmentation of TIMP-1 Production in HT-1080 Cells
- Identification of HLA-A24-Restricted Epitopes with High Affinities to Hsp70 Using Peptide Arrays(METHODS)
- Screening of Anti-Tumor Peptide Vaccines with High Affinity to Hsp70 Using Peptide Array
- 空間量が対数以下に制限された存在(全称)状態のみからなる1-インクドット交代チューリングマシンの閉包性について
- Space hierarchies of three-dimensional turing machines
- Discoordinate Regulation of Expression of Matrix Metalloproteinases and Tissue Inhibitor of Metalloproteinases-3 in Bovine Endometrial Stromal Cells on Type-I Collagen Gel
- Progression of Pericellular Proteolysis by EMMPRIN-bound Active Matrix Metalloproteinase 1 on the Surface of Tumor Cells
- An Antiprogesterone, Onapristone, Enhances the Gene Expression of Promatrix Metatloproteinase 3/Prostromelysin-1 in the Uterine Cervix of Pregnant Rabbit
- Inhibition of AP-1 binding activity and phosphatidylinositol 3-kinase pathway by nobiletin, a polymethoxy flavonoid, results in augmentation of TIMP-1 production and suppression of production of MMPs-1 and -9 in human fibrosarcoma HT-1080 cell
- Involvement of EMMPRIN/CD147 in pericellular proteolysis by augmenting the production of MMP-1 and localization of MMP-1 on tumor cell surface
- Removal of Trichloroethylene from Water by Aeration, Pervaporation and Membrane Distillation
- Separation of Aromatic Hydrocarbons from Gasoline Vapor by Vapor Permeation through Triethylene Glycol Liquid Membrane
- Separation of Benzene/Cyclohexane by Vapor Permeation through Triethylene Glycol Liquid Membrane
- Angiotensin-Converting Enzyme Activity is Involved in the Mechanism of Increased Endogenous Nitric Oxide Synthase Inhibitor in Patients With Type 2 Diabetes Mellitus
- Angiotensin-Converting Enzyme Activity is Involved in the Mechanism of Increased Endogenous Nitric Oxide Synthase Inhibitor in Type II Diabetes Mellitus
- Renin-Angiotensin System is Involved in the Mechanism of Increased Serum Asymmetric Dimethylarginine in Essential Hypertension
- OJ-278 Functional upregulation of bradykinin type-1 receptor in the coronary microciculation in patients with heart failure(Coronary Circulation, Basic/Clinical 3 (IHD) : OJ33)(Oral Presentation (Japanese))
- Inhibition of Rho-Kinase with Fasudil Ameliorates Pacing-Induced Myocardial Ischemia in Patients with Effort Angina
- Incorporation of Capillary-Like Structures into Dermal Cell Sheets Constructed by Magnetic Force-Based Tissue Engineering
- Application of Ultra-Water-Repellent Surface to Cell Culture(CELL AND TISSUE ENGINEERING)
- Heat Immunotherapy Using Magnetic Nanoparticles and Dendritic Cells for T-Lymphoma(MEDICAL BIOTECHNOLOGY, Advances in Biomedical Science and Engineering)
- Screening of Cytokines to Enhance Vaccine Effects of Heat Shock Protein 70-Rich Tumor Cell Lysate(MEDICAL BIOTECHNOLOGY, Advances in Biomedical Science and Engineering)
- Medical Application of Functionalized Magnetic Nanoparticles(Advances in Biomedical Science and Engineering)
- Complete Regression of Mouse Mammary Carcinoma with a Size Greater than 15 mm by Frequent Repeated Hyperthermia Using Magnetite Nanoparticles
- Selective hyperthermia using magnetoliposomes to target cervical lymph node metastasis in a rabbit tongue tumor model
- Proliferation and Stratification of Keratinocyte on Cultured Amniotic Epithelial Cells for Tissue Engineering(MEDICAL BIOTECHNOLOGY)
- Tumor regression by combined immunotherapy and hyperthermia using magnetic nanoparticles in an experimental subcutaneous murine melanoma
- Transglutaminase-Mediated Gelatin Matrices Incorporating Cell Adhesion Factors as a Biomaterial for Tissue Engineering
- Radiation-Inducible TNF-α Gene Expression under Stress-Inducible Promoter gadd 153 for Cancer Therapy
- Bystander-Killing Effect and Cyclic Induction of TNF-α Gene under Heat-Inducible Promoter gadd 153
- Some Properties on Input Head Reversal-Bounded Two-Dimensional Turing Machines (Special Issue on Selected Papers from LA Symposium)
- Self-Verifying Nondeterministic and Las Vegas Multihead Finite Automata (Special Section on Discrete Mathematics and Its Applications)
- A Relationship between Two-Way Deterministic One-Counter Automata and One-Pebble Deterministic Turing Machines with Sublogarithmic Space
- Alternating Rebound Turing Machines (Special Section on Discrete Mathematics and Its Applications)
- Significance of Molecular Diagnosis using Histopathological Specimens in Cestode Zoonoses
- Diphyllobothriasis and sparganosis in Indonesia
- Human Echinococcosis : A Neglected Disease?
- Molecular Characterization of a novel gene encoding an 8-kDa subunit of Antigen B from Echinococcus granulosus genotypes 1 and 6
- A case of intramuscular cysticercosis diagnosed definitively by mitochondrial DNA analysis of extremely calcified cysts
- Echinococcus shiquicus, a new species from the Qinghai-Tibet plateau region of China : Discovery and epidemiological implications
- Challenges for control of taeniasis/cysticercosis in Indonesia
- Taeniasis/cysticercosis in Papua (Irian Jaya), Indonesia
- Genetic variation in Taenia solium
- Usefulness of severe combined immunodeficiency (scid) and inbred mice for studies of cysticercosis and echinococcosis
- Mitochondrial DNA diagnosis for taeniasis and cysticercosis
- Recombinant antigens for serodiagnosis of cysticercosis and echinococcosis
- Recent advances in characterization of Echinococcus antigen B
- IV E10 Therapy for neurocysticercosis "comparison between albendazole and parziquantel" in Wamena Lembah Baliem Jayawijaya Irian Jaya Indonesia
- Construction of Heterotypic Cell Sheets by Magnetic Force-Based 3-D Coculture of HepG2 and NIH3T3 Cells(CELL AND TISSUE ENGINEERING)
- Magnetic Force-Based Cell Patterning Using Arg-Gly-Asp (RGD) Peptide-Conjugated Magnetite Cationic Liposomes(CELL AND TISSUE ENGINEERING)
- Neurocysticercosis case with a single cyst in the brain showing dramatic drop in specific antibody titers within 1 year after curative surgical resection
- Effects of the Mixture Ratio of Amino Acid and Sodium Chloride on the Rejection of Nanofiltration Membranes under Various Operating Conditions
- Some Observations Concerning Alternating Pushdown Automata with Sublogarithmic Space
- On Multi-Inkdot Two-Way Alternating Turing Machines and Pushdown Automata with Sublogarithmic Space and Constant Leaf-Size
- A Note on Alternating Pushdown Automata With Sublogarithmic Space
- Inkdot versus Pebble over Two-Dimensional Languages
- Usefulness of recombinant Em18-ELISA to evaluate efficacy of treatment in patients with alveolar echinococcosis
- AN-P27 Site-specific genetic modification of target cells using an integrase-defective retroviral vector and cre-mediated cassette exchange(Section I Animal and Plant Cell Cultures)
- Human beta defensin-3 engineered keratinocyte sheets constructed by a magnetic force-based tissue engineering technique(CELL AND TISSUE ENGINEERING)
- Enhancement of Cell Function through Heterotypic Cell-Cell Interactions Using E-Cadherin-Expressing NIH3T3 Cells(CELL AND TISSUE ENGINEERING)
- 4-S-Cysteaminylphenol-loaded magnetite cationic liposomes for combination therapy of hyperthermia with chemotherapy against malignant melanoma
- An algorithm for tower of hanoi with four or more poles
- A note on bottom-up pyramid acceptors
- Video file system
- A modified algorithm for taking reciprocal of n-bit integers
- On Simple One-Way Multihead Pushdown Automata
- Sensing Two-Way Three Heads are Better than Two
- Neurocysticercosis as Solitary Parenchymal Lesion Confirmed by Mitochondrial Deoxyribonucleic Acid Sequence Analysis : Case Report
- Growth and Characterization of Anodic Oxidized Films in Pure Water
- Comparison of Yatabe-Guilford Personality Test Results in Retinitis Pigmentosa and Glaucoma Patients
- The Alkylation of Biphenyl over One-Dimensional Twelve-Membered Ring Zeolites : The Influence of Zeolite Structure and Alkylating Agent on the Selectivity for 4,4'-Dialkylbiphenyl
- The Alkylation of Biphenyl over Fourteen-Membered Ring Zeolites : The Influence of Zeolite Structure and Alkylating Agent on the Selectivity for 4,4'-Dialkylbiphenyl
- Shape-Selective Alkylation of Biphenyl over H-[Al]-SSZ-24 Zeolites with AFI Topology
- Giant Adrenal Myelolipoma : Report of a Case
- Correlation of TIMI Frame Counts with Microvascular Constrictive Response to Acetylcholine in Patients with Microvascular Angina(Angina Pectoris, Basic/Clinical 6 (IHD), The 69th Annual Scientific Meeting of the Japanese Circulation Society)
- PE-154 Changing Characteristics of Patients with Vasospastic Angina in the Era of New Calcium Channel Blockers(Preventive Medicine/Epidemiology/Education 1 (H) : PE26)(Poster Session (English))
- FRS-050 Extracorporeal Cardiac Shock Wave Therapy Ameliorates Myocardial Ischemia in Patients with Severe Coronary Artery Disease(New Therapeutic Strategies in Myocardial Infarction (IHD) : FRS6)(Featured Research Session (English))
- Role of Tyrosine Kinases in the Coronary Constrictive Remodeling Induced by Long-Term Treatment with Interleukin-1β in Pigs
- Fluctuations and Phase Transitions Far from Equilibrium : Reductive Perturbation Approach to Chemical Instabilities
- Reductive Perturbation Approach to the Fluctuation
- Evaluation of Em18-, Em16-, Antigen B-Western blots, Em2^-ELISA and four other tests for differential serodiagnosis of alveolar and cystic echinococcosis patients in Poland
- Translational Augmentation of Pro-matrix Metalloproteinase 3 (Prostromelysin 1) and a Tissue Inhibitor of Metalloproteinases (TIMP)-1 mRNAs by Epidermal Growth Factor and Transforming Growth Factor α, but not by Interleukin 1α or 12-O-Tetradecanoylphorbol
- Effects of H_2-Receptor Antagonists on Matrix Metalloproteinases in Rat Gastric Tissues with Acetic Acid-Induced Ulcer
- Taeniasis/cysticercosis and echinococcosis with focus on Asia and the Pacific
- Echinococcus Multilocularis : Why are multidisciplinary and multiscale approaches essential in infectious disease ecology?
- Roles of matrix metalloproteinases and their inhibitors during extracellular matrix remodeling in female reproductive tract
- Melanoma-targeted chemo-thermo-immuno (CTI)-therapy using N-propionyl-4-S-cysteaminylphenol-magnetite nanoparticles elicits CTL response via heat shock protein-peptide complex release