Properties of NLC Graph Languages squeezed with Bipartite Graphs
スポンサーリンク
概要
- 論文の詳細を見る
グラフ文法Gとグラフ理論的性質ψについて,L_ψ(G)をψで圧縮された言語L(G),すなわちL_ψ(G)=L(G)∩L(ψ)であるとする.本文では2部グラフで圧縮されたNLC,B-NLC,NU-NLC言語の閉包性,所属やその他の決定的性質などの言語理論的性質を示した.それによってNLC言語の族は2部グラフによる圧縮については閉じてないことがわかる.また,各NLC(B-NLC)文法Gについて,2部グラフで圧縮された言語L_<bip>(G)はPSPACE(NP)であり,L_<bip>(G')がPSPACE-完全(NP-完全)であるNLC(B-NLC)文法G'が存在することを示し,さらに各NU-NLC文法GについてL(G)の中の全ての完全2部グラフの集合はNSPACE(logn)であることを示す.
- 一般社団法人情報処理学会の論文
- 1995-07-20
著者
-
Lee Dong
Department Of Biotechnology College Of Natural Science Dongguk University
-
Lee D
Korea Advanced Inst. Sci. Technol.(kaist) Kor
-
Lee Dong
Department Of Aerospace Engineering Chonbuk National University
関連論文
- Proteomic Analysis of Bronchoalveolar Lavage Fluid Obtained from Rats Exposed to Formaldehyde
- Characteristics of Multi-Stage Porous Plate Precipitator with Water Spray System
- Multiple myeloma in Korea : past, present, and future perspectives. Experience of the Korean Multiple Myeloma Working Party
- Parietal Lobe Epilepsy : The Semiology, Yield of Diagnostic Workup, and Surgical Outcome
- FDG-PET Images Quantified by Probabilistic Atlas of Brain and Surgical Prognosis of Temporal Lobe Epilepsy
- Binocularity and spatial frequency dependence of calcarine activation in two types of amblyopia
- Clinical course of non-severe aplastic anemia in adults
- 970. 韓国 Youngwol からのオルドビス紀 (Llanvirnian) 層孔虫
- Antimutagenicity and Cytotoxicity of the Constituents from the Aerial Parts of Rumex acetosa(Pharmacognosy)
- Two-Level Anterior Lumbar Interbody Fusion With Percutaneous Pedicle Screw Fixation : A Minimum 3-Year Follow-up Study
- The clinical impact of ^F-FDG PET in papillary thyroid carcinoma with a negative ^I whole body scan : a single-center study of 108 patients
- Correlation between serum CEA level and metabolic volume as determined by FDG PET in postoperative patients with recurrent colorectal cancer
- Non-A type nucleophosmin 1 gene mutation predicts poor clinical outcome in de novo adult acute myeloid leukemia : differential clinical importance of NPM1 mutation according to subtype
- Bacterial DNA Containing Methylated CpG Motifs Retains Immunostimulatory Activity in Synergy with Modified Lipopolysaccharides
- Enzyme Replacement Therapy in a Case of Atypical Infantile Onset Pompe Disease
- CW-270033, a Novel Pyrrolidinyl-thio Carbapenem, Has Potent Antimicrobial Activity in Vitro and in Vivo(Miscellaneous)
- Antimutagenic Constituents from the Thorns of Gleditsia sinensis
- Inhibitory Effects of the Essential Oil from SuHeXiang Wan on the Central Nervous System after Inhalation (Pharmacology)
- Effect of Carbon and Sulfur in Continuously Cast Strand on Longitudinal Surface Cracks
- Inhibitory Effects of the Fragrance Inhalation of Essential Oil from Acorus gramineus on Central Nervous System
- Modulation of Radioligand Binding to the GABA_A-benzodiazepine Receptor Complex by a New Component from Cyperus Rotundus
- Extramedullary Relapse Confirmed by Fluorescence In Situ Hybridization Study of an Ear Mass in Acute Promyelocytic Leukemia
- Residual Stress Behavior of Polyimide Thin Films : Effect of Precursors
- Infrared plus visible light and heat from natural sunlight participate in the expression of MMPs and type I procollagen as well as infiltration of inflammatory cell in human skin in vivo
- Occipital Lobe Epilepsy : Clinical Characteristics, Surgical Outcome, and Role of Diagnostic Modalities
- Cancer screening using ^F-FDG PET/CT in Korean asymptomatic volunteers : a preliminary report
- Maximal safe dose of I-131 after failure of standard fixed dose therapy in patients with differentiated thyroid carcinoma
- Comparison of FDG-PET findings of brain metastasis from non-small-cell lung cancer and small-cell lung cancer
- Superiority of HMPAO Ictal SPECT to ECD Ictal SPECT in Localizing the Epileptogenic Zone
- Diagnostic Performance of [^F]FDG-PET and Ictal [^Tc]-HMPAO SPECT in Occipital Lobe Epilepsy
- The effect of tumor size on F-18-labeled fluorodeoxyglucose and fluoroerythronitroimidazole uptake in a murine sarcoma model
- Bone Scan Appearance of Renal Osteodystrophy in Diabetic Chronic Renal Failure Patients
- Time-Course Changes of Hormones and Cytokines by Lipopolysaccharide and Its Relation with Anorexia
- Detection of the BCR-ABL Gene by Interphase Fluorescence In Situ Hybridization (iFISH) in Chronic Myelogenous Leukemia Patients after Hemopoietic Stem Cell Transplantation: The Feasibility of iFISH Monitoring of Therapeutic Response in Peripheral Blood
- Antimutagenic Activity of 5α-Cholest-7-en-3β-ol, a New Component from the Starfish Asterina pectinifera
- The molecular basis of phenylketonuria in Koreans
- IS-2 The effects of leptin on in vitro development of mouse embryos(Group1 Reproduction1,International Session)
- Comparison of the efficacy and safety of different formulations of omeprazole-based triple therapies in the treatment of Helicobacter pylori-positive peptic ulcer
- Ion chromatography detector based on solid-state ion-selective electrode array
- A Case of Acral Melanocytic Hyperplasia : A Unique Pigmented Lesion Mimicking Acral Lentiginous Melanoma In situ
- Enzyme-Linked Competitive Binding Assays Based on the Biotin/Avidin Interaction
- Synthesis of multi-walled carbon nanotubes using Co-Fe-Mo/Al_2O_3 catalytic powders in a fluidized bed reactor
- Identification and functional analysis of cystathionine beta-synthase gene mutations in patients with homocystinuria
- Prediction of Furnace Heat Transfer and Its Influence on the Steel Slab Heating and Skid Mark Formation in a Reheating Furnace
- Modified Kinetic Model for Dichloropropanol Synthesis from Glycerin And Anhydrous Hcl at High Pressure
- P-2 A Study for Root Shape and Welding Procedure of Welded Joint with Backing Strip(Poster Session,SIMAP'88 Proceedings of International Symposium on Strategy of Innovation in Materials Processing-New Challenge for the 21st Century-)
- Serum Cystatin C Is Related to Pulse Wave Velocity Even in Subjects with Normal Serum Creatinine
- Can γ-Glutamyltransferase be an Additional Marker of Arterial Stiffness?
- S-Phase Accumulation of Candida albicans by Anticandidal Effect of Amentoflavone Isolated from Selaginella tamariscina(Medicinal Chemistry)
- Systemic Plasmacytosis : A Case which Improved with Melphalan
- Decoder-Type Gate Driver Circuits Fabricated with Amorphous Silicon Thin-Film Transistors for Active Matrix Displays
- Effect of Anthropometric Features on the Severity of Lumbar Disk Herniation
- A stability analysis of tandem offloading systems at sea
- Solitary Milialike Idiopathic Calcinosis Cutis : A Case Unassociated with Down Syndrome
- Variation of Facial Psysiological Parameters According to Mental Stress
- Inactivation of the PTEN gene protein product is associated with the invasiveness and metastasis, but not angiogenesis, of breast cancer
- An Experimental Study of Thermal-hydraulic Phenomena in the Downcomer with a Direct Vessel Injection System of APR1400 during the LBLOCA Reflood Phase
- Assessment of an Ultrasonic Sensor and a Capacitance Probe for Measurement of Two-phase Mixture Level
- Fabrication of W_2NiB_2-Ni Borides Cermets
- Induction of Apoptosis by Cordyceps militaris through Activation of Caspase-3 in Leukemia HL-60 Cells(Molecular and Cell Biology)
- Induction of Apoptosis by Disturbing Mitochondrial-Membrane Potential and Cleaving PARP in Jurkat T Cells through Treatment with Acetoxyscirpenol Mycotoxins(Molecular and Cell Biology)
- Extraforaminal Lumbar Synovial Cyst Causing Sudden Foot Drop
- Erythema Induratum with Pulmonary Tuberculosis : Report of Three Cases
- Effective Screening Medium for the Biodegradation of Oleic Acid by Aspergillus niger
- The Molecular Basis of Phenylketonuria in Koreans
- Ambient Dependence of Photoluminescence for ZnO Nanocrystalline Films Synthesized in a Sonochemical Method
- Risk Factors for Perioperative Cardiac Complications After Lumbar Fusion Surgery
- Electrical Characteristics of TiSi2 Nanocrystal Nonvolatile Memory with Barrier-Engineered Tunnel Layer
- Chromatin-based regulation of cytokine transcription in T_h2 cells and mast cells
- Adjacent Segment Disease After Interbody Fusion and Pedicle Screw Fixations for Isolated L4-L5 Spondylolisthesis : A Minimum Five-Year Follow-up
- Handover Control Method Using Resource Reservation in Mobile Multimedia Networks
- Simultaneous quantification of rosiglitazone and its two major metabolites, N-desmethyl and p-hydroxy rosiglitazone in human plasma by liquid chromatography/tandem mass spectrometry : Application to a pharmacokinetic study
- Inflammatory Nodules of the Lower Legs : A Clinical and Histological Analysis of 134 Cases in Korea
- Drug-eluting stent in malignant biliary obstruction
- Efficient Generation of Cube-on-Face Crystallographic Texture in Iron and its Alloys
- The c.3040C > T mutation in COL1A1 is recurrent in Korean patients with infantile cortical hyperostosis (Caffey disease)
- In Vitro Antimicrobial Activity and the Mode of Action of Indole-3-Carbinol against Human Pathogenic Microorganisms(Microbiology)
- Capillary gas chromatographic determination of proteins and biological amino acids as N(O)-tert.-butyldimethylsilyl derivatives
- SUPINE POSITION ENDOSCOPIC RETROGRADE CHOLANGIOPANCREATOGRAPHY IN A PATIENT WITH SITUS AMBIGUOUS WITH POLYSPLENIA
- ALTERNATIVE METHODS IN THE ENDOSCOPIC MANAGEMENT OF DIFFICULT COMMON BILE DUCT STONES
- Mechanism of Decreased Susceptibility for Gram-negative Bacteria and Synergistic Effect with Ampicillin of Indole-3-carbinol(Microbiology)
- The Combination Effect of Korean Red Ginseng Saponins with Kanamycin and Cefotaxime against Methicillin-Resistant Staphylococcus aureus(Microbiology)
- Drying Characteristics of Fine Powders in an Inert Medium Circulating Fluidized Bed
- Models for Minimum Liquid Fluidization Velocity of Gas-Liquid Fluidized Beds
- Properties of NLC Graph Languages squeezed with Bipartite Graphs
- Analysis of Deep-Level Defects on Proton Implanted Polycrystalline Silicon Thin Films Using Photoinduced Current Transient Spectroscopy
- Folliculosebaceous cystic hamartoma on the nipple
- Modified Kinetic Model for Dichloropropanol Synthesis from Glycerin and Anhydrous HCl at High Pressure
- Properties of Rigid Polyurethane Foams with Blowing Agents and Catalysts
- Antimicrobial resistance in community-acquired urinary tract infections : results from the Korean Antimicrobial Resistance Monitoring System
- Current Screening Status for Inherited Metabolic Diseases by Tandem Mass Spectrometry in South Korea
- In Vitro Candidacidal Action of Korean Red Ginseng Saponins against Candida albicans(Microbiology)
- Learning Curve for Percutaneous Endoscopic Lumbar Discectomy
- Multi-Valued Planar Hall Resistance Manipulated by Current Induced Magnetic Field in Fe Films Grown on GaAs(001) Substrates
- Nystagmus caused by epidural fentanyl
- Hemodynamic improvement of anterior cerebral artery territory perfusion induced by bifrontal encephalo(periosteal)synangiosis in pediatric patients with moyamoya disease : a study with brain perfusion SPECT
- Three-Dimensional Monte Carlo Simulation of the Electrical Conductivity of Carbon Nanotube/Polymer Composites
- Prevalence of sexually transmitted infections and sexual behavior of young adults and middle-aged people presenting to health examination centers in Korea
- Persistently low intact parathyroid hormone levels predict a progression of aortic arch calcification in incident hemodialysis patients
- Mutation spectrum of and founder effects affecting the PTS gene in East Asian populations