Unification in the Union of Disjoint Equational Theories: Combining Decision Procedures

Most of the work on the combination of unification algorithms for the union of disjoint equational theories has been restricted to algorithms that compute finite complete sets of unifiers.Thus the developed combination methods usually cannot be used to combine decision procedures,i.e., algorithms that just decide solvability of unification problems without computing unifiers.In this paper we describe a combination algorithm for decision procedures that works for arbitrary equational theories, provided that solvability of so–called unification problems with constant restrictions—a slight generalization of unification problems with constants—is decidable for these theories.As a consequence of this new method, we can, for example, show that generalA-unifiability, i.e.,solvability ofA-unification problems with free function symbols, is decidable. HereAstandsfor the equational theory of one associative function symbol.Our method can also be used to combine algorithms that compute finite complete sets of unifiers. Manfred Schmidt–Schauß' combination result, the until now most general result in this direction, can be obtained as a consequence of this fact.We also obtain the new result that unification in the union of disjoint equational theories is finitary, if general unification—i.e., unification of terms with additional free function symbols—is finitary in the single theories.     

Reducing Equational Theories for the Decision of Static Equivalence

Static equivalence is a well established notion of indistinguishability of sequences of terms which is useful in the symbolic analysis of cryptographic protocols. Static equivalence modulo equational theories allows for a more accurate representation of cryptographic primitives by modelling properties of operators by equational axioms. We develop a method that allows us in some cases to simplify the task of deciding static equivalence in a multi-sorted setting, by removing a symbol from the term signature and reducing the problem to several simpler equational theories. We illustrate our technique at hand of bilinear pairings.     

Perfect Bases for Equational Theories

Perfect bases for equational theories are closely related to confluent and finitely terminating term rewrite systems. The two classes have a large overlap, but neither contains the other. The class of perfect bases is recursive. We also investigate a common generalization of both concepts; we call these more general bases normal, and touch the question of their uniqueness. We also give numerous examples.     

General Algorithms for Permutations in Equational Inference

Mechanized systems for equational inference often produce many terms that are permutations of one another. We propose to gain efficiency by dealing with such sets of terms in a uniform manner, by the use of efficient general algorithms on permutation groups. We show how permutation groups arise naturally in equational inference problems, and study some of their properties. We also study some general algorithms for processing permutations and permutation groups, and consider their application to equational reasoning and term-rewriting systems. Finally, we show how these techniques can be incorproated into resolution theorem-proving strategies.     

Single Versus Simultaneous Equational Unification and Equational Unification for Variable-Permuting Theories

A clear distinction is made between the (elementary) unification problem where there is only one pair of terms to be unified, and the simultaneous unification problem, where many such pairs have to be unified simultaneously – it is shown that there exists a finite, depth-reducing, linear, and confluent term-rewriting system R such that the (single) equational unification problem mod R is decidable, while the simultaneous equational unification problem mod R is undecidable. Also a finite set E of variable-permuting equations is constructed such that equational unification is undecidable mod E, thus settling an open problem. The equational matching problem for variable-permuting theories is shown to be PSPACE-complete.     

Simple On-Line Algorithms for the Maximum Disjoint Paths Problem

In this paper we study the classical problem of finding disjoint paths in graphs. This problem has been studied by a number of authors both for specific graphs and general classes of graphs. Whereas for specific graphs many (almost) matching upper and lower bounds are known for the competitiveness of on-line algorithms, not much is known about how well on-line algorithms can perform in the general setting. The best results obtained so far use the expansion of a network to measure the algorithms performance. We use a different parameter called the routing number that, as we will show, allows more precise results than the expansion. It enables us to prove tight upper and lower bounds for deterministic on-line algorithms. The upper bound is obtained by surprisingly simple greedy-like algorithms. Interestingly, our upper bound on the competitive ratio is even better than the best previous approximation ratio for off-line algorithms. Furthermore, we introduce a refined variant of the routing number and show that this variant allows us, for some classes of graphs, to construct on-line algorithms with a competitive ratio significantly below the best possible upper bound that could be obtained using the routing number or the expansion of a network only. We also show that our on-line algorithms can be transformed into efficient algorithms for the more general unsplittable flow problem.     

The Complexity of Counting Problems in Equational Matching

We introduce a class of counting problems that arise naturally in equational matching and investigate their computational complexity. If E is an equational theory, then #E-Matching is the problem of counting the number of most general E-matchers of two given terms. #E-Matching is a well-defined algorithmic problem for every finitary equational theory. Moreover, it captures more accurately the computational difficulties associated with finding minimal complete sets of E-matchers than the corresponding decision problem for E-matching does.In 1979, L. Valiant developed a computational model for measuring the complexity of counting problems and demonstrated the existence of #P-complete problems, i.e., counting problems that are complete for counting non-deterministic Turing machines of polynomial-time complexity. Using the theory of #P-completeness, we analyze the computational complexity of #E-matching for several important equational theories E. We establish that if E is one of the equational theories A, C, AC, I, U, ACI, Set, ACU, or ACIU, then #E-Matching is a #P-complete problem. We also show that there are equational theories, such as the restriction of AC-matching to linear terms, for which the underlying decision matching problem is solvable in polynomial time, while the associated counting matching problem is #P-complete.     

Quantum Algorithms for Matching Problems

We present quantum algorithms for the following matching problems in unweighted and weighted graphs with n vertices and m edges:

On Action Logic: Equational Theories of Action Algebras

Pratt (1991, Proceedings of JELIA’90, Volume 478, pp.97–120) defines action algebras as Kleene algebras withresiduals and action logic as the equational theory of actionalgebras. In contrast to Kleene algebras, action algebras forma (finitely based) variety. Jipsen (2004, Studia Logica, 76,291–303) proposes a Gentzen-style sequent system for actionlogic but leaves it as an open question if this system admitscut-elimination and if action logic is decidable. We show thatJipsen's system does not admit cut-elimination. We prove thatthe equational theory of *-continuous action algebras and thesimple Horn theory of *-continuous Kleene algebras are not recursivelyenumerable and they possess FMP, but action logic does not possessFMP.     

Improved Algorithms for Partial Curve Matching

We revisit the problem of deciding whether a given curve resembles some part of a larger curve under a fixed Fréchet distance, achieving a running time of O(nm), for n and m being the number of segments in the two curves. This improves the long-standing result of Alt and Godau by an O(log(nm)) factor. Our solution is based on constructing a simple data structure which we call free-space map. Using this data structure, we obtain improved algorithms for several variants of the Fréchet distance problem, including the Fréchet distance between two closed curves, and the so-called minimum/maximum walk problems. We also improve the map matching algorithm of Alt et al. for the particular case in which the map is a directed acyclic graph.     

运动估计快速块匹配算法

基于块的运动估计是视频压缩国际标准中广泛采用的关键技术。在对目前运动估计快速块匹配算法研究的基础上,描述了运动估计的原理;揭示了在图像质量、搜索速度和压缩码率等方面提高算法效率时存在的3类主要问题：初始搜索点的选择、匹配准则和搜索策略;分别阐述了目前常用的解决这3类问题的方法,并进行了比较和分析;提出了对运动估计算法的一些展望。     

入侵检测系统中的带权模式匹配算法

入侵检测系统（IDS）需要根据每个模式串的权值,计算给定主串的总权值并反馈给报警系统。传统的模式匹配算法在计算主串权值时效率低。为此,文中在Aho—Corasick算法的基础上,提出了带权模式匹配算法（WPM）及其改进算法（WPME）。算法优化了自动机的建立过程,对自动机每个节点的失配后继指针信息和匹配量信息进行预处理,从而避免了模式匹配阶段在计算主串权值时的回溯操作,降低了算法的时间复杂度。实验表明,改进后的算法具有效率高、匹配精确的特点。     

Revisiting Multiple Pattern Matching Algorithms for Multi-Core Architecture

Due to the huge size of patterns to be searched,multiple pattern searching remains a challenge to several newly-arising applications like network intrusion detection.In this paper,we present an attempt to design efficient multiple pattern searching algorithms on multi-core architectures.We observe an important feature which indicates that the multiple pattern matching time mainly depends on the number and minimal length of patterns.The multi-core algorithm proposed in this paper leverages this feature to decompose pattern set so that the parallel execution time is minimized.We formulate the problem as an optimal decomposition and scheduling of a pattern set,then propose a heuristic algorithm,which takes advantage of dynamic programming and greedy algorithmic techniques,to solve the optimization problem.Experimental results suggest that our decomposition approach can increase the searching speed by more than 200% on a 4-core AMD Barcelona system.     

面向入侵检测的模式匹配算法研究

在入侵检测系统的实现中,关键部分是检测引擎的实现。而在检测引擎的实现中,关键的是数据分析模块。对于基于规则的入侵检测来说,模式匹配算法非常重要,它直接影响到系统的准确性和实时性能。论文主要研究了BruteForce算法,Boyer-Moore算法,Aho-Corasick算法,Set-wiseBoyer-Moore-Horspool算法,Aho-Corasick_Boyer-Moore算法。     

基于语义匹配复杂Web服务的算法研究

目前,Web服务发现机制中以关键词搜索方式进行服务匹配,忽略人类语言的多样性,造成较低的匹配率,同时单个Web服务无法满足客户面向业务过程的商业需求.本文研究一种基于语义匹配复杂Web服务的算法,在服务注册机制中对复杂Web服务匹配进行预处理,Web服务请求到达进行二次匹配,匹配单个Web服务或面向业务过程的一组Web服务.     

Efficient Algorithms for Image Template and Dictionary Matching

Given a large text image and a small template image, the Template Matching Problem is that of finding every location within the text which looks like the pattern. This problem, which has received attention for low-level image processing, has been formalized by defining a distance metric between arrays of pixels and finding all subarrays of the large image which are within some threshold distance of the template. These so-called metric methods tends to be too slow for many applications, since evaluating the distance function can take too much time. We present a method for quickly eliminating most positions of the text from consideration as possible matches. The remaining candidate positions are then evaluated one by one against the template for a match. We are still guaranteed to find all matching positions, and our method gives significant speed-ups. Finally, we consider the problem of matching a dictionary of templates against a text. We present methods which are much faster than matching the templates individually against the input image.     

入侵检测中模式匹配算法的性能分析

模式匹配算法在入侵检测中有着广泛的应用,它直接影响到入侵检测系统的实时性能。论文主要研究了Boyer-Moore算法,Modified Wu—Manber算法,Exclusion—Based算法和Aho—Corasick算法。通过实验对上述四种算法在混合攻击和特定攻击的条件下进行了性能测试,根据实验结果,得出了不同算法的应用范围,为今后入侵检测系统开发者选择模式匹配算法提供了有价值的参考。     

单模式匹配算法研究

本文详细分析几种单模式匹配算法如BF、KMP、BM、QS、HORSPOOL和TUNEDBM。通过上机实验对这些算法的性能进行分析,得出结论在这些单模式匹配算法中TUNEDBM算法是最快的算法。     

组合指纹匹配算法研究

组合不同的指纹匹配算法是提高身份认证识别率的有效手段。文章将指纹图像的细节特征引入到基于Gabor滤波器组的匹配算法中,并提出了一种基于细节特征算法和改进算法的组合匹配算法。该方法首先根据细节特征对输入指纹图像进行旋转平移,然后利用Gabor滤波器组对指纹编码区进行矩形分块编码,最后将匹配结果与基于细节特征匹配算法的匹配数进行组合,得到一个组合匹配数进行决策。通过对FVC2004DB1-A指纹库的实验,结果表明该文提出的组合算法与其它单纯利用细节特征或纹理特征的匹配算法相比较,该文的组合匹配算法具有更高的识别率。     

基于数据模型演化过程中模式匹配算法研究

论文对国内外关于模式匹配的研究进行综合分析,主要从模式匹配的角度对复杂模式匹配过程进行了研究,并着重对结构化的模式匹配进行了研究,对结构相似度和语言相似度进行综合;在语言匹配的基础上,对结构匹配进行分类匹配,采用自顶向下分别从非叶子节点和叶子节点进行模式匹配,非叶子节点匹配结果对叶子节点匹配结果有传递指导作用.该方法是一种利用元素间的结构信息来辅助模式匹配的新方法.最终达到提高模式匹配结果准确率的目的.