Theory of one-tape linear-time Turing machines

A theory of one-tape two-way one-head off-line linear-time Turing machines is essentially different from its polynomial-time counterpart since these machines are closely related to finite state automata. This paper discusses structural-complexity issues of one-tape Turing machines of various types (deterministic, nondeterministic, reversible, alternating, probabilistic, counting, and quantum Turing machines) that halt in linear time, where the running time of a machine is defined as the length of any longest computation path. We explore structural properties of one-tape linear-time Turing machines and clarify how the machines’ resources affect their computational patterns and power.     

Preparation of novel porous solids from alumina-pillared fluorine micas by acid-treatment

New porous solids from alumina-pillared fluorine micas (APMs), which were obtained from synthetic Na-tetrasilicic fluorine mica [NaMg_2.5Si₄O₁₀F₂], were prepared by sulfuric acid-treatment under mild conditions at 25 °C. The products were investigated by XRD, ICP, SEM, TEM and N₂ adsorption–desorption isotherm at 77 K. XRD measurements indicated that the interlayer pillared structure having a large basal spacing collapsed during the early stages of the acid-treatment. ICP analyses indicated that Al³⁺ and Mg²⁺ ions were leached out from the pillared micas during the acid-treatment. The pore properties of the leached products were found to differ from those of the mother pillared micas: the acid leaching of the pillared micas leads to the formation of mesopores around 3.2 nm in diameter. The correlation between the change in pore properties and cation elution behavior suggests that the mesopore formation results from the leaching of Mg²⁺ ions from the octahedral sheet of the pillared micas. The leached products thus obtained retained the flaky morphology of the mother pillared micas. These results show that the mild acid-treatment using APMs provides a novel route for obtaining unique mesopore solids having the large particle sizes of the mother micas.     

Clinical study on mechanism of Pneumocystis carinii pneumonia by polymerase chain reaction

Pneumocystis carinii is a human respiratory pathogen which causes fatal pneumonia in patients under immunosuppressed or immune deficient conditions. Recent work have documented the usefulness of the polymerase chain reaction (PCR) method in the detection of P. carinii from clinical samples. Therefore, we described our experience in using PCR method in the detection of P. carinii from respiratory samples. In our study, bronchial washing or BALF were good for diagnosis of P. carinii pneumonia (PCP) by PCR. However, PCR method in the detection of P. carinii from swab or sputum was too sensitive because small numbers of P. carinii organisms might be insignificant in causing the disease. It might reveal colonization or asymptomatic carrier state in the upper respiratory tract. Therefore, our result suggested that colonization or asymptomatic carrier state in the upper respiratory tract could eventually evolve into PCP. This would also facilitate basic progress in the pathology or epidemiology of P. carinii infection. In addition, an usefulness of prophylactic therapy for PCP was documented by PCR.     

Evaluation of PCR for detection of DNA specific for Aspergillus species in sera of patients with various forms of pulmonary aspergillosis

Pulmonary aspergillosis is classified into invasive, saprophytic, and allergic forms. In this study, we evaluated the usefulness of PCR for differentiating between different forms of aspergillosis or in monitoring disease activity during treatment by detecting DNA specific for Aspergillus species in the serum. Nested PCR was used to detect Aspergillus DNA in the sera of 30 patients with various forms of pulmonary aspergillosis. The results were compared with those of latex agglutination tests for detecting galactomannan antigen. We also examined the serial changes in the results of nested PCR during and after treatment of a subgroup of patients with invasive pulmonary aspergillosis with amphotericin B. The highest proportion of positive nested PCR results were in patients with invasive aspergillosis (10 of 12; 83%), while patients with pulmonary aspergilloma had the lowest frequency of positive tests (1 of 9; 11%). These results suggested that the sensitivity of the nested PCR depends on the extent of invasion by Aspergillus species. Serial assays showed that the results of nested PCR became negative shortly after commencement of antifungal treatment and that such changes did not correlate with clinical responsiveness to treatment. Our results indicate the potential usefulness of nested PCR with serum samples for the diagnosis of invasive aspergillosis and the detection of a shift in the status of infection from a noninvasive type to invasive aspergillosis. However, the results of the nested PCR did not correlate with the response to antifungal treatment.     

Correction to: The impact of time windows constraints on metaheuristics implementation: a study for the Discrete and Dynamic Berth Allocation Problem

Applied Intelligence - A Correction to this paper has been published: https://doi.org10.1007/s10489-021-02571-4     

Pressureless Sintering of Carbon Nanofibre/SiC Composites and Their Properties

To enhance the fracture toughness of silicon carbide (SiC) ceramics and prevent the generation of cracks and chippings in the SiC ceramics during machining process, carbon nanofibres (CNFs) were compounded with SiC. The densification and microstructure development of the CNFs/SiC composites pressureless sintered in Ar atmosphere were investigated. The fracture toughness of SiC ceramics was enhanced by the addition of 1–3 wt% CNFs, which resulted from the pullout and/or bridging effect of CNFs bonded much more closely with SiC. The addition of 3 wt% CNFs prevented the chippings from generating in the composite during precision machining process.     

Preparation and luminescent properties of Eu-doped transparent mica glass–ceramics

Eu-doped transparent mica glass–ceramics were prepared, the influence of Eu-doping on the crystallization of the parent glasses was investigated and the luminescent properties of the parent glasses and the glass–ceramics were estimated. A small additive amount of Eu element was very effective in preparing transparent mica glass–ceramics. However, the excess addition led to the coarsening of phase separation in the glass phase and the separation of unidentified crystal phases and β-eucryptite during heating of the parent glasses, which caused white opaque at lower heating temperatures. When mica crystals were separated, Eu ions entered the interlayers of mica crystals. The observed emission and excitation spectra showed that parts of Eu³⁺ ions which were added as Eu₂O₃ were reduced to Eu²⁺ ions during melting of the starting materials and heating the parent glasses in air and the energy transfer from Eu²⁺ to Eu³⁺ ions occurred.     

Species Identification and PCR-RFLP Analysis of Cytochrome b Gene in Cod Fish (Order Gadiformes) Products

ABSTRACT: Polymerase chain reaction-restriction fragment length polymorphism (PCR-RFLP) profiles using the PCR product tRNA^Glu-cytochrome b of 9 standard cod fish, all of which are imported into Japan under the name "cod fish," were investigated as a means of rapid species identification of imported cod fish products. Endonuclease digestion using 4 restriction enzymes ( Alu I, Fok I, Mbo I, and Mse I) generated different digestion patterns for the standards, enabling species identification in imported cod fish products by comparison to the standards'RFLP profiles. Additionally, we conducted a more strict check by phylogenetic analysis on imported cod fish products with 13 standards (including 4 additional cod species from GenBank) using the mitochondrial cytochrome b gene (385 nt). Consequently, it was found that the PCR-RFLP method was sufficient for rapidly screening cod products, and in cases that require conclusive identification, phylogenetic analysis was the most suitable.     

Constant-space quantum interactive proofs against multiple provers

We present upper and lower bounds of the computational complexity of the two-way communication model of multiple-prover quantum interactive proof systems whose verifiers are limited to measure-many two-way quantum finite automata. We prove that (i) the languages recognized by those multiple-prover systems running in expected polynomial time are exactly the ones in NEXP, the nondeterministic exponential-time complexity class, (ii) if we further require verifiers to be one-way quantum finite automata, then their associated proof systems recognize context-free languages but not beyond languages in NE, the nondeterministic linear exponential-time complexity class, and moreover, (iii) when no time bound is imposed, the proof systems become as powerful as Turing machines. The first two results answer affirmatively an open question, posed by Nishimura and Yamakami [J. Comput. System Sci. 75 (2009) 255–269], of whether multiple-prover quantum interactive proof systems are more powerful than single-prover ones. Our proofs are simple and intuitive, although they heavily rely on an earlier result on multiple-prover classical interactive proof systems of Feige and Shamir [J. Comput. System Sci. 44 (1992) 259–271].     

Computational Indistinguishability Between Quantum States and Its Cryptographic Application

We introduce a computational problem of distinguishing between two specific quantum states as a new cryptographic problem to design a quantum cryptographic scheme that is “secure” against any polynomial-time quantum adversary. Our problem, QSCD_ff, is to distinguish between two types of random coset states with a hidden permutation over the symmetric group of finite degree. This naturally generalizes the commonly-used distinction problem between two probability distributions in computational cryptography. As our major contribution, we show that QSCD_ff has three properties of cryptographic interest: (i) QSCD_ff has a trapdoor; (ii) the average-case hardness of QSCD_ff coincides with its worst-case hardness; and (iii) QSCD_ff is computationally at least as hard as the graph automorphism problem in the worst case. These cryptographic properties enable us to construct a quantum public-key cryptosystem which is likely to withstand any chosen plaintext attack of a polynomial-time quantum adversary. We further discuss a generalization of QSCD_ff, called QSCD_cyc, and introduce a multi-bit encryption scheme that relies on similar cryptographic properties of QSCD_cyc.