Regular expression matching is playing an important role in deep inspection. The rapid development of SDN and NFV makes the network more dynamic, bringing serious challenges to traditional deep inspection matching eng...Regular expression matching is playing an important role in deep inspection. The rapid development of SDN and NFV makes the network more dynamic, bringing serious challenges to traditional deep inspection matching engines. However, state-of-theart matching methods often require a significant amount of pre-processing time and hence are not suitable for this fast updating scenario. In this paper, a novel matching engine called BFA is proposed to achieve high-speed regular expression matching with fast pre-processing. Experiments demonstrate that BFA obtains 5 to 20 times more update abilities compared to existing regular expression matching methods, and scales well on multi-core platforms.展开更多
The induced matching cover number of a graph G without isolated vertices, denoted by imc(G),is the minimum integer k such that G has k induced matchings {M1,M2,···,Mk}such that,V(M1)∪V(M2)∪··...The induced matching cover number of a graph G without isolated vertices, denoted by imc(G),is the minimum integer k such that G has k induced matchings {M1,M2,···,Mk}such that,V(M1)∪V(M2)∪···∪V(Mk)covers V(G).This paper shows that,if G is a 3-regular claw-free graph,then imc(G)∈{2,3}.展开更多
A subset of the vertex set of a graph is a feedback vertex set of the graph if the resulting graph is a forest after removed the vertex subset from the graph. A polynomial algorithm for finding a minimum feedback vert...A subset of the vertex set of a graph is a feedback vertex set of the graph if the resulting graph is a forest after removed the vertex subset from the graph. A polynomial algorithm for finding a minimum feedback vertex set of a 3-regular simple graph is provided.展开更多
Due to its importance in security, syntax analysis has found usage in many high-level programming languages. The Lisp language has its share of operations for evaluating regular expressions, but native parsing of Lisp...Due to its importance in security, syntax analysis has found usage in many high-level programming languages. The Lisp language has its share of operations for evaluating regular expressions, but native parsing of Lisp code in this way is unsupported. Matching on lists requires a significantly more complicated model, with a different programmatic approach than that of string matching. This work presents a new automata-based approach centered on a set of functions and macros for identifying sequences of Lisp S-expressions using finite tree automata. The objective is to test that a given list is an element of a given tree language. We use a macro that takes a grammar and generates a function that reads off the leaves of a tree and tries to parse them as a string in a context-free language. The experimental results indicate that this approach is a viable tool for parsing Lisp lists and expressions in the abstract interpretation展开更多
Making exact approximations to solve equations distinguishes applied mathematicians from pure mathematicians, physicists, and engineers. Perturbation problems, both regular and singular, are pervasive in diverse field...Making exact approximations to solve equations distinguishes applied mathematicians from pure mathematicians, physicists, and engineers. Perturbation problems, both regular and singular, are pervasive in diverse fields of applied mathematics and engineering. This research paper provides a comprehensive overview of algebraic methods for solving perturbation problems, featuring a comparative analysis of their strengths and limitations. Serving as a valuable resource for researchers and practitioners, it offers insights and guidance for tackling perturbation problems in various disciplines, facilitating the advancement of applied mathematics and engineering.展开更多
基金supported by the National Key Technology R&D Program of China under Grant No. 2015BAK34B00the National Key Research and Development Program of China under Grant No. 2016YFB1000102
文摘Regular expression matching is playing an important role in deep inspection. The rapid development of SDN and NFV makes the network more dynamic, bringing serious challenges to traditional deep inspection matching engines. However, state-of-theart matching methods often require a significant amount of pre-processing time and hence are not suitable for this fast updating scenario. In this paper, a novel matching engine called BFA is proposed to achieve high-speed regular expression matching with fast pre-processing. Experiments demonstrate that BFA obtains 5 to 20 times more update abilities compared to existing regular expression matching methods, and scales well on multi-core platforms.
基金Supported by the National Natural Science Foundation of China（10771179）
文摘The induced matching cover number of a graph G without isolated vertices, denoted by imc(G),is the minimum integer k such that G has k induced matchings {M1,M2,···,Mk}such that,V(M1)∪V(M2)∪···∪V(Mk)covers V(G).This paper shows that,if G is a 3-regular claw-free graph,then imc(G)∈{2,3}.
文摘A subset of the vertex set of a graph is a feedback vertex set of the graph if the resulting graph is a forest after removed the vertex subset from the graph. A polynomial algorithm for finding a minimum feedback vertex set of a 3-regular simple graph is provided.
文摘Due to its importance in security, syntax analysis has found usage in many high-level programming languages. The Lisp language has its share of operations for evaluating regular expressions, but native parsing of Lisp code in this way is unsupported. Matching on lists requires a significantly more complicated model, with a different programmatic approach than that of string matching. This work presents a new automata-based approach centered on a set of functions and macros for identifying sequences of Lisp S-expressions using finite tree automata. The objective is to test that a given list is an element of a given tree language. We use a macro that takes a grammar and generates a function that reads off the leaves of a tree and tries to parse them as a string in a context-free language. The experimental results indicate that this approach is a viable tool for parsing Lisp lists and expressions in the abstract interpretation
文摘Making exact approximations to solve equations distinguishes applied mathematicians from pure mathematicians, physicists, and engineers. Perturbation problems, both regular and singular, are pervasive in diverse fields of applied mathematics and engineering. This research paper provides a comprehensive overview of algebraic methods for solving perturbation problems, featuring a comparative analysis of their strengths and limitations. Serving as a valuable resource for researchers and practitioners, it offers insights and guidance for tackling perturbation problems in various disciplines, facilitating the advancement of applied mathematics and engineering.
