-
88The equivalence of theories that characterize ALogTimeArchive for Mathematical Logic 48 (6): 523-549. 2009.A number of theories have been developed to characterize ALogTime (or uniform NC 1, or just NC 1), the class of languages accepted by alternating logtime Turing machines, in the same way that Buss’s theory ${{\bf S}^{1}_{2}}$ characterizes polytime functions. Among these, ALV′ (by Clote) is particularly interesting because it is developed based on Barrington’s theorem that the word problem for the permutation group S 5 is complete for ALogTime. On the other hand, ALV (by Clote), T 0 NC 0 (by Clo…Read more
-
23The provably total NP search problems of weak second order bounded arithmeticAnnals of Pure and Applied Logic 162 (6): 419-446. 2011.We define a new NP search problem, the “local improvement” principle, about labellings of an acyclic, bounded-degree graph. We show that, provably in , it characterizes the consequences of and that natural restrictions of it characterize the consequences of and of the bounded arithmetic hierarchy. We also show that over V0 it characterizes the consequences of V1 and hence that, in some sense, a miniaturized version of the principle gives a new characterization of the consequences of . Throughout…Read more
-
20Simulating non-prenex cuts in quantified propositional calculusMathematical Logic Quarterly 57 (5): 524-532. 2011.We show that the quantified propositional proof systems Gi are polynomially equivalent to their restricted versions that require all cut formulas to be prenex Σqi . Previously this was known only for the treelike systems G*i. © 2011 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim
-
10Application of PCR-DGGE method for identification of nematode communities in pepper growing soilJournal of Vietnamese Environment 7 (1): 9-14. 2016.Soil nematodes play an important role in indication for assessing soil environments and ecosystems. Previous studies of nematode community analyses based on molecular identification have shown to be useful for assessing soil environments. Here we applied PCR-DGGE method for molecular analysis of five soil nematode communities collected from four provinces in Southeastern Vietnam based on SSU gene. By sequencing DNA bands derived from S5 community sample, our data show 15 species containing soil …Read more