A formal-linguistic approach for solving an entertaining task is offered in this paper. The well-known task of the Hanoi towers is discussed in relation to some concepts of formal languages and grammars. A context-fre...A formal-linguistic approach for solving an entertaining task is offered in this paper. The well-known task of the Hanoi towers is discussed in relation to some concepts of formal languages and grammars. A context-free grammar which generates an algorithm for solving this task is described. A deterministic pushdown automation which in its work imitates the work of monks in solving the task of the Hanoi towers is built.展开更多
We consider context-free grammars of the form G = {f → f^b1＋b2＋1g^a1＋a2, g → f^b1 g^a1＋1},where ai and bi are integers sub ject to certain positivity conditions. Such a grammar G gives rise to triangular arrays...We consider context-free grammars of the form G = {f → f^b1＋b2＋1g^a1＋a2, g → f^b1 g^a1＋1},where ai and bi are integers sub ject to certain positivity conditions. Such a grammar G gives rise to triangular arrays {T（n, k）}0≤k≤n satisfying a three-term recurrence relation. Many combinatorial sequences can be generated in this way. Let Tn （x） =∑k=0^n T（n, k）x^k. Based on the differential operator with respect to G, we define a sequence of linear operators Pn such that Tn＋1（x） = Pn（Tn（x））. Applying the characterization of real stability preserving linear operators on the multivariate polynomials due to Borcea and Br？ndén, we obtain a necessary and sufficient condition for the operator Pn to be real stability preserving for any n. As a consequence, we are led to a sufficient condition for the real-rootedness of the polynomials defined by certain triangular arrays, obtained by Wang and Yeh.Moreover, as special cases we obtain grammars that lead to identities involving the Whitney numbers and the Bessel numbers.展开更多
Stochastic context-free grammars （SCFGs） have been applied to predicting RNA secondary structure. The prediction of RNA secondary structure can be facilitated by incorporating with comparative sequence analysis. How...Stochastic context-free grammars （SCFGs） have been applied to predicting RNA secondary structure. The prediction of RNA secondary structure can be facilitated by incorporating with comparative sequence analysis. However, most of existing SCFG-based methods lack explicit phylogenic analysis of homologous RNA sequences, which is probably the reason why these methods are not ideal in practical application. Hence, we present a new SCFG-based method by integrating phylogenic analysis with the newly defined profile SCFG. The method can be summarized as： 1） we define a new profile SCFG, M, to depict consensus secondary structure of multiple RNA sequence alignment; 2） we introduce two distinct hidden Markov models, λ and λ＇, to perform phylogenic analysis of homologous RNA sequences. Here, λ＇ is for non-structural regions of the sequence and λ＇ is for structural regions of the sequence; 3） we merge λ and λ＇ into M to devise a combined model for prediction of RNA secondary structure. We tested our method on data sets constructed from the Rfam database. The sensitivity and specificity of our method are more accurate than those of the predictions by Pfold.展开更多
大规模的用户口令集因可用于评估口令猜测算法的效率、检测现有用户口令保护机制的缺陷等,而广受系统安全研究领域的重视.然而,尽管可以通过一些渠道,譬如网站口令泄露、用户自愿征集或者个别网站出于研究目的的共享等,获取真实的大规...大规模的用户口令集因可用于评估口令猜测算法的效率、检测现有用户口令保护机制的缺陷等,而广受系统安全研究领域的重视.然而,尽管可以通过一些渠道,譬如网站口令泄露、用户自愿征集或者个别网站出于研究目的的共享等,获取真实的大规模用户明文口令对当前研究人员来说仍然非常困难.为应对上述问题,该文提出了一种基于样本的模拟口令集生成算法(Sample Perturbation Based Password Generation,SPPG).该算法利用较容易获得的小规模真实口令样本,通过学习生成概率模型,并产生大规模用户口令集合.为评估这一算法的效能,该文提出了一组模拟口令集质量的检测指标,包括真实口令覆盖率、Zipf分布拟合度等.最后,论文对比了SPPG算法与当前常见的用户口令猜测概率模型,包括概率上下文无关文法和多种马尔科夫模型,在生成用户口令集上的效能差异.结果显示,SPPG算法产生的模拟口令集在各指标下都有更好的表现.平均地,在真实口令覆盖率上,相对上下文无关文法和四阶马尔科夫模型分别提高了9.58%和72.79%,相对三阶和一阶马尔科夫模型分别提高了10.34倍和13.41倍,并且Zipf分布的拟合度保持在0.9及以上的水平.同时,其口令结构分布和特殊模式的使用也更符合真实用户生成口令的情况.展开更多
By proposing tools that help for the accomplishment of tasks in almost all sectors of activities, computer science has revolutionized the world in a general way. Nowadays, it addresses the peculiarities of peoples thr...By proposing tools that help for the accomplishment of tasks in almost all sectors of activities, computer science has revolutionized the world in a general way. Nowadays, it addresses the peculiarities of peoples through their culture in order to produce increasingly easy-to-use software for end users: This is the aim of software localization. Localizing a software consists among other things, in adapting its GUI according to the end user culture. We propose in this paper a generic approach allowing accomplishing this adaptation, even for multi-user applications like gaming applications, collaborative editors, etc. Techniques of functional interpretations of abstracts structures parameterized by algebras, constitute the formal base of our approach.展开更多
Design and construction of an error-free compiler is a difficult and challenging process. The main functionality of a compiler is to translate a source code to an executable machine code correctly and efficiently. In ...Design and construction of an error-free compiler is a difficult and challenging process. The main functionality of a compiler is to translate a source code to an executable machine code correctly and efficiently. In formal verification of software, semantics of a language has more meanings than the syntax. It means source program verification does not give guarantee the generated code is correct. This is because the compiler may lead to an incorrect target program due to bugs in itself. It means verification of a compiler is much more important than verification of a source program. In this paper, we present a new approach by linking context-free grammar and Z notation to construct LR(K) parser. This has several advantages because correctness of the compiler depends on describing rules that must be written in formal languages. First, we have defined grammar then language derivation procedure is given using right-most derivations. Verification of a given language is done by recursive procedures based on the words. Ambiguity of a language is checked and verified. The specification is analyzed and validated using Z/Eves tool. Formal proofs are presented using powerful techniques of reduction and rewriting available in Z/Eves.展开更多
The Dumont differential system on the Jacobi elliptic functions was introduced by Dumont(1979)and was extensively studied by Dumont, Viennot, Flajolet and so on. In this paper, we first present a labeling scheme for t...The Dumont differential system on the Jacobi elliptic functions was introduced by Dumont(1979)and was extensively studied by Dumont, Viennot, Flajolet and so on. In this paper, we first present a labeling scheme for the cycle structure of permutations. We then introduce two types of Jacobi pairs of differential equations. We present a general method to derive the solutions of these differential equations. As applications,we present some characterizations for several permutation statistics.展开更多
文摘A formal-linguistic approach for solving an entertaining task is offered in this paper. The well-known task of the Hanoi towers is discussed in relation to some concepts of formal languages and grammars. A context-free grammar which generates an algorithm for solving this task is described. A deterministic pushdown automation which in its work imitates the work of monks in solving the task of the Hanoi towers is built.
基金Supported by the 973 Projectthe PCSIRT Project+1 种基金the Doctoral Program Fund of the Ministry of Educationthe National Science Foundation of China
文摘We consider context-free grammars of the form G = {f → f^b1＋b2＋1g^a1＋a2, g → f^b1 g^a1＋1},where ai and bi are integers sub ject to certain positivity conditions. Such a grammar G gives rise to triangular arrays {T（n, k）}0≤k≤n satisfying a three-term recurrence relation. Many combinatorial sequences can be generated in this way. Let Tn （x） =∑k=0^n T（n, k）x^k. Based on the differential operator with respect to G, we define a sequence of linear operators Pn such that Tn＋1（x） = Pn（Tn（x））. Applying the characterization of real stability preserving linear operators on the multivariate polynomials due to Borcea and Br？ndén, we obtain a necessary and sufficient condition for the operator Pn to be real stability preserving for any n. As a consequence, we are led to a sufficient condition for the real-rootedness of the polynomials defined by certain triangular arrays, obtained by Wang and Yeh.Moreover, as special cases we obtain grammars that lead to identities involving the Whitney numbers and the Bessel numbers.
基金the National Natural Science Foundation of China under Grant No.60673018
文摘Stochastic context-free grammars （SCFGs） have been applied to predicting RNA secondary structure. The prediction of RNA secondary structure can be facilitated by incorporating with comparative sequence analysis. However, most of existing SCFG-based methods lack explicit phylogenic analysis of homologous RNA sequences, which is probably the reason why these methods are not ideal in practical application. Hence, we present a new SCFG-based method by integrating phylogenic analysis with the newly defined profile SCFG. The method can be summarized as： 1） we define a new profile SCFG, M, to depict consensus secondary structure of multiple RNA sequence alignment; 2） we introduce two distinct hidden Markov models, λ and λ＇, to perform phylogenic analysis of homologous RNA sequences. Here, λ＇ is for non-structural regions of the sequence and λ＇ is for structural regions of the sequence; 3） we merge λ and λ＇ into M to devise a combined model for prediction of RNA secondary structure. We tested our method on data sets constructed from the Rfam database. The sensitivity and specificity of our method are more accurate than those of the predictions by Pfold.
文摘大规模的用户口令集因可用于评估口令猜测算法的效率、检测现有用户口令保护机制的缺陷等,而广受系统安全研究领域的重视.然而,尽管可以通过一些渠道,譬如网站口令泄露、用户自愿征集或者个别网站出于研究目的的共享等,获取真实的大规模用户明文口令对当前研究人员来说仍然非常困难.为应对上述问题,该文提出了一种基于样本的模拟口令集生成算法(Sample Perturbation Based Password Generation,SPPG).该算法利用较容易获得的小规模真实口令样本,通过学习生成概率模型,并产生大规模用户口令集合.为评估这一算法的效能,该文提出了一组模拟口令集质量的检测指标,包括真实口令覆盖率、Zipf分布拟合度等.最后,论文对比了SPPG算法与当前常见的用户口令猜测概率模型,包括概率上下文无关文法和多种马尔科夫模型,在生成用户口令集上的效能差异.结果显示,SPPG算法产生的模拟口令集在各指标下都有更好的表现.平均地,在真实口令覆盖率上,相对上下文无关文法和四阶马尔科夫模型分别提高了9.58%和72.79%,相对三阶和一阶马尔科夫模型分别提高了10.34倍和13.41倍,并且Zipf分布的拟合度保持在0.9及以上的水平.同时,其口令结构分布和特殊模式的使用也更符合真实用户生成口令的情况.
文摘By proposing tools that help for the accomplishment of tasks in almost all sectors of activities, computer science has revolutionized the world in a general way. Nowadays, it addresses the peculiarities of peoples through their culture in order to produce increasingly easy-to-use software for end users: This is the aim of software localization. Localizing a software consists among other things, in adapting its GUI according to the end user culture. We propose in this paper a generic approach allowing accomplishing this adaptation, even for multi-user applications like gaming applications, collaborative editors, etc. Techniques of functional interpretations of abstracts structures parameterized by algebras, constitute the formal base of our approach.
文摘Design and construction of an error-free compiler is a difficult and challenging process. The main functionality of a compiler is to translate a source code to an executable machine code correctly and efficiently. In formal verification of software, semantics of a language has more meanings than the syntax. It means source program verification does not give guarantee the generated code is correct. This is because the compiler may lead to an incorrect target program due to bugs in itself. It means verification of a compiler is much more important than verification of a source program. In this paper, we present a new approach by linking context-free grammar and Z notation to construct LR(K) parser. This has several advantages because correctness of the compiler depends on describing rules that must be written in formal languages. First, we have defined grammar then language derivation procedure is given using right-most derivations. Verification of a given language is done by recursive procedures based on the words. Ambiguity of a language is checked and verified. The specification is analyzed and validated using Z/Eves tool. Formal proofs are presented using powerful techniques of reduction and rewriting available in Z/Eves.
基金supported by National Natural Science Foundation of China(Grant No.11401083)Natural Science Foundation of Hebei Province(Grant No.A2017501007)+1 种基金the Fundamental Research Funds for the Central Universities(Grant No.N152304006)Taiwan “National” Science Council(Grant No.104-2115-M-001-010)
文摘The Dumont differential system on the Jacobi elliptic functions was introduced by Dumont(1979)and was extensively studied by Dumont, Viennot, Flajolet and so on. In this paper, we first present a labeling scheme for the cycle structure of permutations. We then introduce two types of Jacobi pairs of differential equations. We present a general method to derive the solutions of these differential equations. As applications,we present some characterizations for several permutation statistics.
