Vectorial languages and linear temporal logic

Determining for a given deterministic complete automaton the sequence of visited states while reading a given word is the core of important problems with automata-based solutions, such as approximate string matching. The main difficulty is to do this computation efficiently. Considering words as vectors and working on them using vectorial operations allows to solve the problem faster than using local operations.

In this paper, we show first that the set of vectorial operations needed by an algorithm representing a given automaton depends on the language accepted by the automaton. We give precise characterizations for star-free, solvable and regular languages using vectorial algorithms. We also study classes of languages associated with restricted sets of vectorial operations and relate them with languages defined by fragments of linear temporal logic.

Finally, we consider the converse problem of constructing an automaton from a given vectorial algorithm. As a byproduct, we show that the satisfiability problem for some extensions of LTL characterizing solvable and regular languages is PSPACE-complete.     

Fast approximate matching of words against a dictionary

A new algorithm for string edit distance computation is given. The algorithm assumes that one of the two strings to be compared is a dictionary entry that is known a priori. This dictionary word is converted in an off-line phase into a deterministic finite state automaton. Given an input string and the automaton derived from the dictionary word, the computation of the edit distance between the two strings corresponds to a traversal of the states of the automaton. This procedure needs time which is only linear in the length of the input string. It is independent of the length of the dictionary word. Given not only one butN different dictionary words, their corresponding automata can be combined into a single deterministic finite state automaton. Thus the computation of the edit distance between the input word and each dictionary entry, and the determination of the nearest neighbor in the dictionary need time that is only linear in the length of the input string. However, the number os states of the automation is exponential.     

双向AC算法及其在入侵检测系统中应用

在经典的多模式字符串匹配算法-AC算法的基础上,提出了双向AC算法.该算法在预处理阶段构造正向和反向两个有限状态自动机,匹配时使用正向有限自动机从文本串中间位置向右扫描,同时依据反向有限状态自动机从中间位置向左扫描.将该算法应用于开放源码的入侵检测系统Snort中,实验结果表明较BM算法、WM算法和AC算法本算法有更好...     

Deciding unique decodability of bigram counts via finite automata

We revisit the problem of deciding by means of a finite automaton whether a string is uniquely decodable from its bigram counts. An efficient algorithm for constructing a polynomial-size Nondeterministic Finite Automaton (NFA) that decides unique decodability is given. This NFA may be simulated efficiently in time and space. Conversely, we show that the minimum deterministic finite automaton for deciding unique decodability has exponentially many states in alphabet size, and compute the correct order of magnitude of the exponent.     

Finite time analysis of the pursuit algorithm for learning automata

The problem of analyzing the finite time behavior of learning automata is considered. This problem involves the finite time analysis of the learning algorithm used by the learning automaton and is important in determining the rate of convergence of the automaton. In this paper, a general framework for analyzing the finite time behavior of the automaton learning algorithms is proposed. Using this framework, the finite time analysis of the Pursuit Algorithm is presented. We have considered both continuous and discretized forms of the pursuit algorithm. Based on the results of the analysis, we compare the rates of convergence of these two versions of the pursuit algorithm. At the end of the paper, we also compare our framework with that of Probably Approximately Correct (PAC) learning.     

关于同步部分规约的有限自动机的优化问题的近似难度

自动机是可同步的是指它具有满足以下性质的同步字:不论自动机当前所处的状态,以同步字为输入执行后它一定会到达某个特定状态。同步自动机问题的核心是计算最短同步字。聚焦于这一核心问题,文中就一类称为部分规约的确定的有限自动机的最短同步字问题,研究了近似计算这类自动机的最短同步字的复杂性,即近似计算它的难度,该工作有助于其近似算法的分析与设计。通过建立由两个优化问题(MAX SAT问题以及MAX FA-INT问题)到最短同步字长度计算这一问题(即Shortest-Syn)的归约,利用与概率可检验证明(Probabilistically Checkable Proofs,PCP)定理和概率可检验辩论(Probabilistically Checkable Debate,PCD)定理有关的若干结果证明了文中的主要结论:对于部分规约的确定的有限自动机,在某个近似因子内Shortest-Syn的近似难度是NP-难的和PSPACE-难的,除非NP和PSPACE分别坍塌到P。     

On regular tree languages and deterministic pushdown automata

The theory of formal string languages and of formal tree languages are both important parts of the theory of formal languages. Regular tree languages are recognized by finite tree automata. Trees in their postfix notation can be seen as strings. This paper presents a simple transformation from any given (bottom-up) finite tree automaton recognizing a regular tree language to a deterministic pushdown automaton accepting the same tree language in postfix notation. The resulting deterministic pushdown automaton can be implemented easily by an existing parser generator because it is constructed for an LR(0) grammar, and its size directly corresponds to the size of the deterministic finite tree automaton. The class of regular tree languages in postfix notation is a proper subclass of deterministic context-free string languages. Moreover, the class of tree languages which are in their postfix notation deterministic context-free string languages is a proper superclass of the class of regular tree languages.     

Computing Automatic Coset Systems and Subgroup Presentations

The concept of an automatic group can be generalized to a group that is automatic with respect to a specified subgroup. This means that there is a finite state automaton that recognizes a unique word in each coset of the subgroup, and others that essentially recognize the permutation action on these cosets induced by multiplying by a group generator. These automata make it possible to enumerate coset representatives as words in the generators, and to solve the generalized word problem for the subgroup efficiently. Algorithms to construct these automata have been described previously by Redfern. Here we describe improved versions, together with implementation details and some examples of successful calculations. A related algorithm to compute a finite presentation of the subgroup is also described.     

Derivatives of tree sets with applications to grammatical inference

Tree automata generalize the notion of a finite automaton working on strings to that of a finite automaton operating on trees. Most results for finite automata have been extended to tree automata. In this paper we introduce tree derivatives which extend the concept of Brzozowski's string derivatives. We use tree derivatives for minimizing and characterizing tree automata. Tree derivatives are used as a basis of inference of tree automata from finite samples of trees. Our method compares tree derivative sets and infers a tree automaton based on the amount of overlap between the derivative sets. Several of the limitations present in the tree inference techniques by Brayer and Fu and Edwards, Gonzalez, and Thomason are not imposed by our algorithm.     

String execution time for finite languages: Max is easy, min is hard

In performance evaluation or supervisory control, we often encounter problems of determining the maximum or minimum string execution time for a finite language when estimating the worst-case or best-case performance. It has been shown in the literature that the time complexity for computing the maximum string execution time for a finite language is polynomial with respect to the size of an automaton recognizer of that language and the dimension of the corresponding resource matrices. In this paper we provide a more efficient algorithm to compute such maximum string execution time. Then we show that it is NP-complete to determine the minimum string execution time.     

Malicious Omissions and Errors in Answers to Membership Queries

We consider two issues in polynomial-time exact learning of concepts using membership and equivalence queries: (1) errors or omissions in answers to membership queries, and (2) learning finite variants of concepts drawn from a learnable class.To study (1), we introduce two new kinds of membership queries: limited membership queries and malicious membership queries. Each is allowed to give incorrect responses on a maliciously chosen set of strings in the domain. Instead of answering correctly about a string, a limited membership query may give a special I don't know answer, while a malicious membership query may give the wrong answer. A new parameter Lis used to bound the length of an encoding of the set of strings that receive such incorrect answers. Equivalence queries are answered correctly, and learning algorithms are allowed time polynomial in the usual parameters and L. Any class of concepts learnable in polynomial time using equivalence and malicious membership queries is learnable in polynomial time using equivalence and limited membership queries; the converse is an open problem. For the classes of monotone monomials and monotone k-term DNF formulas, we present polynomial-time learning algorithms using limited membership queries alone. We present polynomial-time learning algorithms for the class of monotone DNF formulas using equivalence and limited membership queries, and using equivalence and malicious membership queries.To study (2), we consider classes of concepts that are polynomially closed under finite exceptions and a natural operation to add exception tables to a class of concepts. Applying this operation, we obtain the class of monotone DNF formulas with finite exceptions. We give a polynomial-time algorithm to learn the class of monotone DNF formulas with finite exceptions using equivalence and membership queries. We also give a general transformation showing that any class of concepts that is polynomially closed under finite exceptions and is learnable in polynomial time using standard membership and equivalence queries is also polynomial-time learnable using malicious membership and equivalence queries. Corollaries include the polynomial-time learnability of the following classes using malicious membership and equivalence queries: deterministic finite acceptors, boolean decision trees, and monotone DNF formulas with finite exceptions.     

Recognition of noisy subsequences using constrained edit distances

Let X* be any unknown word from a finite dictionary H. Let U be any arbitrary subsequence of X*. We consider the problem of estimating X* by processing Y, which is a noisy version of U. We do this by defining the constrained edit distance between XH and Y subject to any arbitrary edit constraint involving the number and type of edit operations to be performed. An algorithm to compute this constrained edit distance has been presented. Although in general the algorithm has a cubic time complexity, within the framework of our solution the algorithm possesses a quadratic time complexity. Recognition using the constrained edit distance as a criterion demonstrates remarkable accuracy. Experimental results which involve strings of lengths between 40 and 80 and which contain an average of 26.547 errors per string demonstrate that the scheme has about 99.5 percent accuracy.     

On groups whose word problem is solved by a˜counter automaton

We prove that a group G has a word problem that is accepted by a deterministic counter automaton with a weak inverse property if and only if G is virtually abelian. We extend this result to larger classes of groups by considering a generalization of finite state automata, counter automata and pushdown automata. Natural corollaries of our general result include a restricted version of Herbst's classification of groups for which the word problem is a one counter language and a new classification of automata that accept context-free word problems.     

Distance automata having large finite distance or finite ambiguity

A distance automaton is a (nondeterministic finite) automaton which is equipped with a nonnegative cost function on its transitions. The distance of a word recognized by such a machine quantifies the expenses associated with the recognition of this word. The distance of a distance automaton is the maximal distance of a word recognized by this machine or is infinite, depending on whether or not a maximum exists. We present distance automata havingn states and distance 2 ⁿ – 2. As a by-product we obtain regular languages having exponential finite order. Given a finitely ambiguous distance automaton withn states, we show that either its distance is at most 3 ⁿ – 1, or the growth of the distance in this machine is linear in the input length. The infinite distance problem for these distance automata is NP-hard and solvable in polynomial space. The infinite-order problem for regular languages is PSPACE-complete.A preliminary version of this article appeared in theProceedings of the 15th Symposium on Mathematical Foundations of Computer Science, 1990.     

自动机算法在文本不精确匹配中的应用

论文从实用的角度,着重研究了有限自动机算法在文本的不精确匹配中的应用,提出了一种用于中文精确匹配的自动机的构建思想,两种用于中文同音字匹配的自动机的构建思想,以及利用自动机的原理去除无用字符对文本匹配的干扰的方法。编程实现了上述三种自动机算法并对其作了测试,给出了三种算法各自的性能测试数据。     

Query Learning of Regular Tree Languages: How to Avoid Dead States

We generalize an inference algorithm by Angluin, that learns a regular string language from a "minimally adequate teacher", to regular tree languages. The (deterministic bottom-up) finite tree automaton constructed by the learning algorithm is the minimal partial one recognizing the unknown language. This improves a similar algorithm proposed by Sakakibara by avoiding dead states both in the resulting automaton and the learning phase, which also leads to a considerable improvement with respect to efficiency.     

An improved algorithm for determinization of weighted and fuzzy automata

For a given weighted finite automaton over a strong bimonoid we construct its reduced Nerode automaton, which is crisp-deterministic and equivalent to the original weighted automaton with respect to the initial algebra semantics. We show that the reduced Nerode automaton is even smaller than the Nerode automaton, which was previously used in determinization related to this semantics. We determine necessary and sufficient conditions under which the reduced Nerode automaton is finite and provide an efficient algorithm which computes the reduced Nerode automaton whenever it is finite. In determinization of weighted finite automata over semirings and fuzzy finite automata over lattice-ordered monoids this algorithm gives smaller crisp-deterministic automata than any other known determinization algorithm.     

Engineering order‐preserving pattern matching with SIMD parallelism

The order‐preserving pattern matching problem has gained attention in recent years. It consists in finding all substrings in the text, which have the same length and relative order as the input pattern. Typically, the text and the pattern consist of numbers. Since recent times, there has been a tendency to utilize the ability of the word RAM model to increase the efficiency of string matching algorithms. This model works on computer words, reading and processing blocks of characters at once, so that usual arithmetic and logic operations on words can be performed in one unit of time. In this paper, we present a fast order‐preserving pattern matching algorithm, which uses specialized word‐size packed string matching instructions, grounded on the single instruction multiple data instruction set architecture. We show with experimental results that the new proposed algorithm is more efficient than the previous solutions. ©2016 The Authors. Software: Practice and Experience Published by John Wiley & Sons Ltd.     

On finite automata with limited nondeterminism

We develop a new algorithm for determining if a given nondeterministic finite automaton is limited in nondeterminism. From this, we show that the number of nondeterministic moves of a finite automaton, if limited, is bounded by where is the number of states. If the finite automaton is over a one-letter alphabet, using Gohon's result the number of nondeterministic moves, if limited, is less than . In both cases, we present families of finite automata demonstrating that the upper bounds obtained are almost tight. We also show that the limitedness problem of the number of nondeterministic moves of finite automata is PSPACE-hard. Since the problem is already known to be in PSPACE, it is therefore PSPACE-complete. Received: 14 June 1994 / 3 December 1997