Search

Model abstraction for finite state automata is helpful for decreasing computational complexity and improving comprehensibility for the verification and control synthesis of discrete-event systems (DES). Supremal quasi-congruence equivalence is an effective method for reducing the state space of DES and its effective algorithms based on graph theory have been developed. In this paper, a new method is proposed to convert the supremal quasi-congruence computation into a binary linear programming problem which can be solved by many powerful integer linear programming and satisfiability (SAT) solvers. Partitioning states to cosets is considered as allocating states to an unknown number of cosets and the requirement of finding the coarsest quasi-congruence is equivalent to using the least number of cosets. The novelty of this paper is to solve the optimal partitioning problem as an optimal state-to-coset allocation problem. The task of finding the coarsest quasi-congruence is equivalent to the objective of finding the least number of cosets. Then the problem can be solved by optimization methods, which are respectively implemented by mixed integer linear programming (MILP) in MATLAB and binary linear programming (BLP) in CPLEX. To reduce the computation time, the translation process is first optimized by introducing fewer decision variables and simplifying constraints in the programming problem. Second, the translation process formulates a few techniques of converting logic constraints on finite automata into binary linear constraints. These techniques will be helpful for other researchers exploiting integer linear programming and SAT solvers for solving partitioning or grouping problems. Third, the computational efficiency and correctness of the proposed method are verified by two different solvers. The proposed model abstraction approach is applied to simplify the large-scale supervisor model of a manufacturing system with five automated guided vehicles. The proposed method is not only a new solution for the coarsest quasi-congruence computation, but also provides us a more intuitive understanding of the quasi-congruence relation in the supervisory control theory. A future research direction is to apply more computationally efficient solvers to compute the optimal state-to-coset allocation problem. [ABSTRACT FROM AUTHOR]

Afflictions, or predispositions to have particular disorders in an animal are often caused by specific genes. However, some of these conditions could be avoided using genetic alterations during the breeding process. A good example is brachycephaly in dogs, which, in many cases, causes dyspnoea. In this research paper, we focused on using Finite Deterministic Automata for pattern recognition in dog genes in order to improve the breathing problems of French bulldogs, and other brachycephalic breeds. [ABSTRACT FROM AUTHOR]

The main goal of the paper is to contribute to the agenda of developing an algorithmic model for crystallization and measuring the complexity of crystals by constructing embeddings of 3D parallelohedra into a primitive cubic network (pcu net). It is proved that any parallelohedron P as well as tiling by P, except the rhombic dodecahedron, can be embedded into the 3D pcu net. It is proved that for the rhombic dodecahedron embedding into the 3D pcu net does not exist; however, embedding into the 4D pcu net exists. The question of how many ways the embedding of a parallelohedron can be constructed is answered. For each parallelohedron, the deterministic finite automaton is developed which models the growth of the crystalline structure with the same combinatorial type as the given parallelohedron. [ABSTRACT FROM AUTHOR]

Huffman [Huffman (1952)] encoding is one of the most known compression algorithms. In its basic use, only one encoding is given for the same letter in text to compress. In this paper, a text compression algorithm that is based on Huffman encoding is proposed. Huffman encoding is used to give different encodings for the same letter depending on the prefix preceding it in the word. A deterministic finite automaton (DFA) that recognizes the words of the text is constructed. This DFA records the frequencies for letters that label the transitions. Every state will correspond to one of the prefixes of the words of the text. For every state, a different Huffman encoding is defined for the letters that label the transitions leaving that state. These Huffman encodings are then used to encode the letters of the words in the text. This algorithm was implemented and experimental study showed significant reduction in compression ratio over the basic Huffman encoding. However, more time is needed to construct these codes. [ABSTRACT FROM AUTHOR]

This paper deals with the application of Brzozowski's minimization procedure to fuzzy finite automata with truth-values in a complete residuated (zero-divisor-free) lattice. For a given fuzzy finite automaton $\mathcal{A}$ , the procedure computes the automaton $d(r(d(r(\mathcal{A})))$ , where $d(\mathcal{A})$ is a (fuzzy) determinization of $\mathcal{A}$ , and $r(\mathcal{A})$ is the reverse automaton of $\mathcal{A}$. It is observed that the size of the resulting automaton is strongly dependent on the determinization method used in the procedure. Consequently, this paper studies necessary and sufficient conditions for obtaining minimal fuzzy deterministic finite automata via Brzozowski's procedure. The study is accomplished for determinization methods based on a generalized notion of accessible fuzzy subset construction. The obtained conditions determine that Brzozowski's procedure returns a minimal fuzzy deterministic finite automaton when the determinization method does not produce proportional fuzzy states. This is the reason to obtain minimal fuzzy deterministic finite automata using Brzozowski's procedure for fuzzy finite automata with truth-values in the product-structure when the determinization method is the method based on factorization of fuzzy states. [ABSTRACT FROM AUTHOR]

In this paper, we introduce and study notions like statedistinguishability, input-distinguishability and output completeness of states of a crisp deterministic fuzzy automaton. We show th a t for each crisp deterministic fuzzy automaton there corresponds a unique (up to isomorphism), equivalent distinguished crisp deterministic fuzzy automaton. Finally, we introduce two axioms related to output completeness of states and discuss the interrelationship between them. [ABSTRACT FROM AUTHOR]

Obtaining a minimal automaton is a fundamental issue in the theory and practical implementation of deterministic finite automatons (DFAs). A minimization algorithm is presented in this paper that consists of two main phases. In the first phase, the backward depth information is built, and the state set of the DFA is partitioned into many blocks. In the second phase, the state set is refined using a hash table. The minimization algorithm has a lower time complexity O(n) than a naive comparison of transitions O(n2). Few states need to be refined by the hash table, because most states have been partitioned by the backward depth information in the coarse partition. This method achieves greater generality than previous methods because building the backward depth information is independent of the topological complexity of the DFA. The proposed algorithm can be applied not only to the minimization of acyclic automata or simple cyclic automata, but also to automata with high topological complexity. Overall, the proposal has three advantages: lower time complexity, greater generality, and scalability. A comparison to Hopcroft’s algorithm demonstrates experimentally that the algorithm runs faster than traditional algorithms. [ABSTRACT FROM AUTHOR]

We propose to use algorithms for learning deterministic finite automata (DFA), such as Angluin's L algorithm, for learning a DFA that describes the possible scenarios under which a given program error occurs. The alphabet of this automaton is given by the user (for instance, a subset of the function call sites or branches), and hence the automaton describes a user-defined abstraction of those scenarios. More generally, the same technique can be used for visualising the behavior of a program or parts thereof. It can also be used for visually comparing different versions of a program (by presenting an automaton for the behavior in the symmetric difference between them), and for assisting in merging several development branches. We present experiments that demonstrate the power of an abstract visual representation of errors and of program segments, accessible via the project's web page. In addition, our experiments in this paper demonstrate that such automata can be learned efficiently over real-world programs. We also present lazy learning, which is a method for reducing the number of membership queries while using L, and demonstrate its effectiveness on standard benchmarks. [ABSTRACT FROM AUTHOR]

Background and Purpose: In a complex strictly hierarchical organizational structure, undesired oscillations may occur, which have not yet been adequately addressed. Therefore, parameter values, which define fluctuations and transitions from one state to another, need to be optimized to prevent oscillations and to keep parameter values between lower and upper bounds. The objective was to develop a simulation model of hierarchical organizational structure as a web application to help in solving the aforementioned problem. Design/Methodology/Approach: The hierarchical structure was modeled according to the principles of System Dynamics. The problem of the undesired oscillatory behavior was addressed with deterministic finite automata, while the flow parameter values were optimized with genetic algorithms. These principles were implemented as a web application with JavaScript/ECMAScript. Results: Genetic algorithms were tested against well-known instances of problems for which the optimal analytical values were found. Deterministic finite automata was verified and validated via a three-state hierarchical organizational model, successfully preventing the oscillatory behavior of the structure. Conclusion: The results indicate that the hierarchical organizational model, genetic algorithms and deterministic finite automata have been successfully implemented with JavaScript as a web application that can be used on mobile devices. The objective of the paper was to optimize the flow parameter values in the hierarchical organizational model with genetic algorithms and finite automata. The web application was successfully used on a three-state hierarchical organizational structure, where the optimal flow parameter values were determined and undesired oscillatory behavior was prevented. Therefore, we have provided a decision support system for determination of quality restructuring strategies. [ABSTRACT FROM AUTHOR]

Purpose – This paper aims to compete and detect suspicious transactions that can lead to detecting money laundering cases. Design/methodology/approach – This paper presents a plan-based framework for anti-money laundering systems (PBAMLS). Such a framework is novel and consists of two phases, in addition to several supporting modules. The first phase, the monitoring phase, utilizes an automata approach as a formalism to detect probable money laundering. The detection process is based on a money laundering deterministic finite automaton that has been obtained from the corresponding regular expressions which specify different money laundering processes. The second phase is STRIPS-based planning phase that aims at strengthening the belief in the probable problems discovered in the first (monitoring) phase. In addition, PBAMLS contains several supporting modules for data collection and mediation, link analysis and risk scoring. To assess the applicability of PBAMLS, it has been tested using different cases studies. Findings – This framework provides a clear shift of anti-money laundering systems (AML) from depending heuristic and human expertise to making use of a rigorous formalism to accomplish concrete decisions. It minimizes the possibilities of false positive alarms and increases the certainty in decision-making. Practical implications – This framework enhances the detection of money laundering cases. It also minimizes the number of false-positive alarms that waste the investigators’ efforts and time; it decreases the efforts presented by the investigators. Originality/value – This work proposes PBAMLS as a novel plan-based framework for AML systems. [ABSTRACT FROM AUTHOR]

Polynomial-time P systems with active membranes characterise PSPACE by exploiting membranes nested to a polynomial depth, which may be subject to membrane division rules. When only elementary (leaf) membrane division rules are allowed, the computing power decreases to PPP = P#P, the class of problems solvable in polynomial time by deterministic Turing machines equipped with oracles for counting (or majority) problems. In this paper we investigate a variant of intermediate power, limiting membrane nesting (hence membrane division) to constant depth, and we prove that the resulting P systems can solve all problems in the counting hierarchy CH, which is located between PPP and PSPACE. In particular, for each integer k ≥⃒ 0 we provide a lower bound to the computing power of P systems of depth k. [ABSTRACT FROM AUTHOR]

Regular expression (RE) matching is a core component of deep packet inspection in modern networking and security devices. In this paper, we propose the first hardware-based RE matching approach that uses ternary content addressable memory (TCAM), which is available as off-the-shelf chips and has been widely deployed in modern networking devices for tasks such as packet classification. We propose three novel techniques to reduce TCAM space and improve RE matching speed: transition sharing, table consolidation, and variable striding. We tested our techniques on eight real-world RE sets, and our results show that small TCAMs can be used to store large deterministic finite automata (DFAs) and achieve potentially high RE matching throughput. For space, we can store each of the corresponding eight DFAs with 25\,000 states in a 0.59-Mb TCAM chip. Using a different TCAM encoding scheme that facilitates processing multiple characters per transition, we can achieve potential RE matching throughput of 10–19 Gb/s for each of the eight DFAs using only a single 2.36-Mb TCAM chip. [ABSTRACT FROM AUTHOR]

The paper gives a summary of the existing results about algorithmic analysis of probabilistic pushdown automata and their subclasses. [ABSTRACT FROM AUTHOR]

It is known that poly-time constant-space quantum Turing machines (QTMs) and logarithmic-space probabilistic Turing machines (PTMs) recognize uncountably many languages with bounded error (A.C. Cem Say and A. Yakaryılmaz, Magic coins are useful for small-space quantum machines. Quant. Inf. Comput.17 (2017) 1027–1043). In this paper, we investigate more restricted cases for both models to recognize uncountably many languages with bounded error. We show that double logarithmic space is enough for PTMs on unary languages in sweeping reading mode or logarithmic space for one-way head. On unary languages, for quantum models, we obtain middle logarithmic space for counter machines. For binary languages, arbitrary small non-constant space is enough for PTMs even using only counter as memory. For counter machines, when restricted to polynomial time, we can obtain the same result for linear space. For constant-space QTMs, we obtain the result for a restricted sweeping head, known as restarting realtime. [ABSTRACT FROM AUTHOR]

Rational relations are binary relations of finite words that are realised by non-deterministic finite state transducers (NFT). A multi-sequential relation is a rational relation which is equal to a finite union of (graphs) of partial sequential functions, i.e. functions realised by input-deterministic transducers. The particular case of multi-sequential functions was studied by Choffrut and Schützenberger who proved that given a rational function (as a transducer), it is decidable whether it is multi-sequential. Their procedure is based on an effective characterisation of unambiguous transducers that do not define multi-sequential functions, that we call the fork property. In this paper, we show that the fork property also characterises the class of transducers that do not define multi-sequential relations. Moreover, we prove that the fork property can be decided in PTime. This leads to a PTime procedure which, given a transducer, decides whether it defines a multi-sequential relation. [ABSTRACT FROM AUTHOR]

The existence of a substantial gap between deterministic and nondeterministic two-way automata is one of the most famous open problems in automata theory. This problem is also related to the fundamental DLOG vs. NLOG question. An exponential gap between the number of states of two-way nondeterministic automata (2 NFAS) and their deterministic counterparts (2 DFAS) has been proved only for some restrictions of 2 DFAS up to now. It seems that the hardness of this problem lies in the fact that, when trying to prove lower bounds, we must consider every possible automaton, without imposing any particular structure or meaning to the states, while when designing a specific automaton, we always assign an unambiguous interpretation to the states. In an attempt to capture the concept of meaning of states, a new model of two-way automata, namely reasonable automaton ( RA), was introduced in [6]. In a RA, each state is associated with a logical formula expressing some properties of the input word, and transitions are designed to maintain consistency within this setting. In this paper we extend the study, started in [6], of the descriptional complexity of RAS solving the liveness problem, showing several lower and upper bounds with respect to the logic used for describing the meaning of the individual states. [ABSTRACT FROM AUTHOR]

Regular expressions with shuffle operators are widely used in diverse fields of computer science. The work presented here investigates the shuffling of regular expressions and their conversion into non-deterministic finite automata. The aim of the paper is to design a novel algorithm for constructing ε-free non-deterministic finite automata from the shuffling of regular expressions. Non-deterministic finite automata generated using the proposed approach requires, in the worst case, 2m+s+1 states. This is a significant improvement over other existing approaches in the literature, where the number of states reaches 22(m+u+k+s)-C in the worst case. [ABSTRACT FROM AUTHOR]

There is an increasing demand for network devices to perform deep packet inspection (DPI) in order to enhance network security. In DPI, the packet payload is compared against a set of predefined patterns that can be specified using regular expressions (regexes). It is well-known that mapping regexes to deterministic finite automaton (DFA) may suffer from the state explosion problem. Through observation, we attribute DFA explosion to the necessity of remembering matching history. In this paper, we investigate how to manage matching history efficiently and propose an extended DFA approach for regex matching called fcq-FA, which can make a memory size reduction of about 1,000 times with a fully automated approach. In fcq-FA, we use pipeline queues and counters to help record the matching history. Hence, state explosion caused by Kleene closure and length restriction can be completely avoided. Furthermore, it achieves a fully automated signature compilation with polynomial running time and space. The equivalence between fcq-FA and the traditional DFA is guaranteed by a strict theoretical proof, which means fcq-FA can process all the regexes supported by the traditional DFA. [ABSTRACT FROM AUTHOR]

In an earlier paper, the author used derivatives to construct a deterministic automaton recognizing the language defined by an ω-regular expression. The construction was related to a determinization method invented by Safra. This paper describes a new construction, inspired by Piterman's improvement to Safra's method. It produces an automaton with fewer states. In addition, the presentation and proofs are simplified by going via a nondeterministic automaton having derivatives as states. [ABSTRACT FROM AUTHOR]

This Paper presents an automated method of Epileptic Spike detection in Electroencephalogram (EEG) using Deterministic Finite Automata (DFA). It takes pre-recorded single channel EEG data file as input and finds the occurrences of Epileptic Spikes data in it. The EEG signal was recorded at 256 Hz in two minutes separate data files using the Visual Lab-M software (ADLink Technology Inc., Taiwan). It was preprocessed for removal of baseline shift and band pass filtered using an infinite impulse response (IIR) Butterworth filter. A system, whose functionality was modeled with DFA, was designed. The system was tested with 10 EEG signal data files. The recognition rate of Epileptic Spike as on average was 95.68%. This system does not require any human intrusion. Also it does not need any short of training. The result shows that the application of DFA can be useful in detection of different characteristics present in EEG signals. This approach could be extended to a continuous data processing system. [ABSTRACT FROM AUTHOR]

Partial words are sequences of characters from an alphabet in which some positions may be marked with a "hole" symbol, ⋄. We can create a ⋄-substitution mapping this symbol to a subset of the alphabet, so that applying such a substitution to a partial word results in a set of total words (ones without holes). This setup allows us to compress regular languages into smaller partial languages. Deterministic finite automata for such partial languages, referred to as ⋄-DFAs, employ a limited nondeterminism that can allow them to have lower state complexity than the minimal DFAs for the corresponding total languages. Our paper focuses on algorithms for the construction of minimal partial languages, associated with some ⋄-substitution, as well as approximation algorithms for the construction of minimal ⋄-DFAs. [ABSTRACT FROM AUTHOR]

Regular expression matching as a core component of deep packet inspection is widely used in various kinds of modern network intrusion detection system, traffic classification system, network monitoring system, and so on. In these systems, regular expressions are typically converted to a deterministic finite automaton (DFA), which takes O(1) to scan each input character. However, DFA generally consumes a large amount of memory. This paper proposes a novel, space-efficient and time-efficient DFA presentation, called reduced input character set DFA (RICS-DFA). A character escaping and replacing scheme is first introduced to decrease the size of DFA's character set and then to reduce DFA's space requirement with a series of optimization techniques. Based on transition rewriting, a RICS-DFA constructing algorithm with time complexity of O( n) is presented in this paper. For real rule-sets, RICS-DFA reduces the memory consumption by 68-92%, compared with the original DFA. Finally, this paper designs a scalable RICS-DFA matching engine on field-programmable gate array platform in which the reduced state transition matrix is mapped to on-chip memories. The throughput of executing deep packet inspection for real rule-sets can achieve 7-50.5 Gbps. Copyright © 2016 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Every deterministic finite automata can be converted into regular expression and vice versa.Various techniques like Transitive closure method, Brzozowski algebraic and State elimination exist for conversion of deteministic finite automata to regular expression. In state elimination method concept of bridge state, horizontal chopping and vertical chopping are used for obtaining smaller regular expressions from deterministic finite automata. In this research paper, new heuristic is discussed using which a smaller regular expression can be generated. Relationship between the size of deterministic finite automata and size of regular expression is estimated.. [ABSTRACT FROM AUTHOR]

The throughput of a string-matching engine can be multiplied up by inspecting multiple characters in parallel. However, the space that is required to implement a matching engine that can process multiple characters in every cycle grows dramatically with the number of characters to be processed in parallel. This paper presents a hybrid finite automaton (FA) that has deterministic and nondeterministic finite automaton (NFA and DFA) parts and is based on the Aho-Corasick algorithm, for inspecting multiple characters in parallel while maintaining favorable space utilization. In the presented approach, the number of multi-character transitions increases almost linearly with respect to the number of characters to be inspected in parallel. This paper also proposes a multi-stage architecture for implementing the hybrid FA. Since this multi-stage architecture has deterministic stages, configurable features can be introduced into it for processing various keyword sets by simply updating the configuration. The experimental results of the implementation of the multi-stage architecture on FPGAs for 8-character transitions reveal a 4.3 Gbps throughput with a 67 MHz clock, and the results obtained when the configurable architecture with two-stage pipelines was implemented in ASICs reveal a 7.9 Gbps throughput with a 123 MHz clock. [ABSTRACT FROM AUTHOR]

Semi-extended regular expressions are regular expressions with intersection, union, concatenation and Kleene closure operators. The aim of this paper is the metamorphosis of semi-extended regular expressions to deterministic finite automata. The proposed algorithm is based on the follow-positions of symbols present in the semi-extended regular expression. Comparison demonstrates that the deterministic finite automaton generated using the proposed algorithm is smaller than the earlier existing approaches in the literature. Finally, to expound upon this metamorphosis, we provide the reader with numerical examples. [ABSTRACT FROM PUBLISHER]

In this paper, on the basis of breadth-first and depth-first ways, we establish a fundamental framework of fuzzy grammars based on lattices, which provides a necessary tool for the analysis of fuzzy automata. The relationship among finite automata with membership values in lattices ( l-VFAs), lattice-valued regular grammars ( l-RGs) and lattice-valued deterministic regular grammars ( l-DRGs) is investigated. It is demonstrated that, based on each semantic way, l-VFAs and l-RGs are equivalent in the sense that they accept or generate the same classes of fuzzy languages. Furthermore, it is proved that l-VFAs, l-valued deterministic finite automata, l-RGs and l-DRGs are equivalent based on depth-first way. For any l-RG, the language based on breadth-first way coincides with the language based on depth-first way if and only if the truth-valued domain l is a distributive lattice. [ABSTRACT FROM AUTHOR]

Abstract: This paper presents a pattern language based on regular expressions that allows the introduction of variables that can be instantiated to portions of the path that matches the expression. The paper will define a simple syntax for the language and its formal semantics. It will also study a modification of finite state automata that, through the introduction of actions on transitions, allows the variables to be instantiated while matching the expression. Finally, the paper will show that the problem of answering queries with variables is inherently harder than simple matching, essentially because, even for fairly simple expressions, the size of the results can be exponential in the size of the graph. The class of expressions and a class of graphs for which query answering is polynomial will be identified, and a processing algorithm for these expressions based on the intersection graph will be provided and analyzed. [Copyright &y& Elsevier]

Abstract: One of the most usual strategies for tackling the 3D object recognition problem consists of representing the objects by their appearance. 3D recognition can therefore be converted into a 2D shape recognition matter. This paper is focused on carrying out an in depth qualitative and quantitative analysis with regard to the performance of 2D shape recognition methods when they are used to solve 3D object recognition problems. Well known shape descriptors (contour and regions) and 2D similarities measurements (deterministic and stochastic) are thus combined to evaluate a wide range of solutions. In order to quantify the efficiency of each approach we propose three parameters: Hard Recognition Rate (Hr), Weak Recognition Rate (Wr) and Ambiguous Recognition Rate (Ar). These parameters therefore open the evaluation to active recognition methods which deal with uncertainty. Up to 42 combined methods have been tested on two different experimental platforms using public database models. A detailed report of the results and a discussion, including detailed remarks and recommendations, are presented at the end of the paper. [Copyright &y& Elsevier]

Stressed bacteria have developed cooperative strategies to cope with unfavorable growth conditions and to replicate. In this paper, we describe experimentally the effects of stressing bacteria using antibiotic stress, nutritional stress and substrate stress. We find that the cooperative communications between bacteria in the colony are manifested as fascinating complex spatial patterns. We then describe a modeling of this experimentally observed cooperative behavior of the bacteria colony from the perspective of complexity. The inter-bacterial interactions that give rise to the spatial patterns are viewed as an emergent phenomenon, with the interactions being modeled as a Prisoner's dilemma game. We obtain deterministic finite automata that model the interactions, and derive both, a context-free as well as a context-sensitive grammar describing the bacterial interactions and consequent evolution over discrete time. [ABSTRACT FROM AUTHOR]

Regular expression is widely used in the field of computer science. For conversion of deterministic finite automata to regular expression, several techniques like Transitive closure method, Brzozowski Algebraic method and state elimination method are proposed. None of the proposed techniques is able to find the smallest regular expression. This paper investigates and compares different techniques for converting deterministic finite automata to regular expression. Inclusion of bridge state method in state elimination method leads to smaller regular expression as compared to other techniques. [ABSTRACT FROM AUTHOR]

A deterministic finite automaton (DFA) [formula] is called a cover automaton (DFCA) for a finite language L over some alphabet Σ if [formula], with l being the length of some longest word in L. Thus a word w ∈ Σ* is in L if and only if |w| ≤ l and [formula]. The DFCA [formula] is minimal if no DFCA for L has fewer states. In this paper, we present an algorithm which converts an n–state DFA for some finite language L into a corresponding minimal DFCA, using only O(n log n) time and O(n) space. The best previously known algorithm requires O(n[sup 2]) time and space. Furthermore, the new algorithm can also be used to minimize any DFCA, where the best previous method takes O(n[sup 4]) time and space. Since the required data structure is rather complex, an implementation in the common programming language C/C++ is also provided. [ABSTRACT FROM AUTHOR]

Partial word finite automata are deterministic finite automata that may have state transitions on a special symbol ⋄ which represents an unknown symbol or a hole in the word. Together with a subset of the input alphabet that gives the symbols which may be substituted for the ⋄, a partial word finite automaton (⋄-DFA) represents a regular language. However, this substitution implies a certain form of limited nondeterminism in the computations when the ⋄-transitions are replaced by ordinary transitions. In this paper we consider the state complexity of partial word finite automata accepting finite languages. We study the state complexity of the NFA to ⋄-DFA conversion for finite languages as well as the state complexity of the ⋄-DFA to DFA conversion for finite languages. Then we consider the operational state complexity with respect to complementation, union, reversal, and concatenation of finite languages. It turns out that the upper and lower bounds for all these operations are exponential. Moreover, we establish a state complexity hierarchy on the number of productive ⋄-transitions that may appear in ⋄-DFAs accepting finite languages. The levels of the hierarchy are separated by quadratic state costs. [ABSTRACT FROM AUTHOR]

We show in this paper (which appeared in a preliminary form as an extended abstract in [Proceedings of the 9th International ACM­SIAM Symposium on Discrete Algorithms, ACM, 1998]) that deterministic finite automata (DFAs) with n states and input alphabet ∑ can efficiently be learned from less than ¦∑¦n² smallest counterexamples. This improves on an earlier result of Ibarra and Jiang who required ¦∑¦n³ smallest counterexamples. We present a general strategy which learns a finite concept class F from [log F] smallest counterexamples (but not necessarily efficiently). An application to DFAs with at most n states shows that (1 + o(1)) ¦∑¦n log n smallest counterexamples are sufficient (if efficiency is not an issue). We show next that the special DFAs operating on input words of an arbitrary but fixed length (the so-called leveled DFAs) are efficiently learnable from (1 + o(1)) ¦∑¦n log n smallest counterexamples. This improves on an earlier result of Ibarra and Jiang who required ¦∑¦n² smallest counterexamples. Furthermore, we present a general lower bound on the number of smallest counterexamples (required by any learning algorithm). This bound can be stated in terms of a (new) combinatorial dimension associated with the target class. A computation of this dimension for leveled or arbitrary DFAs leads to a lower bound of the form (¼ + o(1)) ¦∑¦ n log n. This bound matches the aforementioned upper bounds modulo a constant of approximately 4. Finally, we present a general conversion of algorithms learning from smallest counterexamples into algorithms performing self-directed learning. For the particular classes of leveled or arbitrary DFAs, this conversion leads to self-directed learners making the smallest possible number of mistakes (modulo a constant of approximately 4). A similar remark is valid for the class of multiplicity automata (MAs). Key words. learning from smallest counterexamples; self-directed learning; deterministic finite automata; multiplicity automata [ABSTRACT FROM AUTHOR]

Model abstraction for finite state automata is beneficial to reduce the complexity of discrete-event systems (DES), enhance the readability and facilitate the control synthesis and verification of DES. Supremal quasi-congruence computation is an effective way for reducing the state space of DES. Effective algorithms on the supremal quasi-congruence relation have been developed based on the graph theory. This paper proposes a new approach to translate the supremal quasi-congruence computation into a satisfiability (SAT) problem that determines whether there exists an assignment for Boolean variables in the state-to-coset allocation matrix. If the result is satisfied, then the supremal quasi-congruence relation exists and the minimum equivalence classes is obtained. Otherwise, it indicates that there is no such supremal quasi-congruence relation, and a new set of observable events needs to be modified or reselected for the original system model. The satisfiability problem on the computation of supremal quasi-congruence relation is solved by different methods, which are respectively implemented by mixed integer linear programming (MILP) in MATLAB, binary linear programming (BLP) in CPLEX, and a SAT-based solver (Z3Py). Compared with the MILP and BLP methods, the SAT method is more efficient and stable. The computation time of model abstraction for large-scale systems by Z3Py solver is significantly reduced.

Regular expressions are widely used in various applications. Due to its low time complexity and stable performance, Deterministic Finite Automaton (DFA) has become the first choice to perform fast regular expression matching. Unfortunately, compiling a large set of regular expressions into one DFA often leads to the well-known state explosion problem, and consequently requires huge memory consumption. Regular expression grouping is a practical approach to mitigate this problem. However, existing grouping algorithms are either brute-force or locally optimal and thus not efficient for large-scale regular expressions. In this paper, we propose two grouping algorithms, namely Reevo and Reant, to solve this problem intelligently and efficiently. In addition, two optimization methods are presented to accelerate the convergence speed and reduce the running time of proposed algorithms. Experimental results on large-scale rulesets from real world show that our algorithms achieve around 25% to 45% improvement compared to previous regular expression grouping algorithms. [ABSTRACT FROM AUTHOR]

A deterministic finite automaton (DFA) separates two strings w and x if it accepts w and rejects x . The minimum number of states required for a DFA to separate w and x is denoted by sep ( w , x ) . The present paper shows that the difference | sep ( w , x ) − sep ( w R , x R ) | is unbounded for a binary alphabet; here w R stands for the mirror image of w . This solves an open problem stated in Demaine et al. (2011) [2] . [ABSTRACT FROM AUTHOR]

A novel approach is proposed for medical analysis and clinical decision support of the Electrocardiogram (ECG) signals based on the deterministic finite automata (DFA) with the addition of some requirements. This paper proves regular grammar is effective in the extraction of QRS complex and interpretation of ECG signals. The DFA will be used to represent a normalized QRS complex as a sequence of negative and positive peaks. A QRS is considered as a set of adjacent peaks that satisfy certain criteria of standard deviation and duration. The proposed method is applied on several kinds of ECG signals collected from the standard MIT-BIH arrhythmia database. Several metrics are calculated including QRS durations, RR distances and peak amplitudes. Furthermore, σRR and σQRS metrics were added to quantify RR distances regularity and QRS durations, respectively. Regular grammar with the addition of some requirements and deterministic automata proved functional for both biomedical signals and ECG signal diagnosis. The suggested method provided a sensitivity rate of 99.74% and the positive predictivity rate of 99.86%. The algorithm was compared to other works in the literature and the quality performance detection was compared with several algorithms tested and validated on the MIT-BIH database. A head-to-head comparison in terms of sensitivity and CPU runtime was provided with the wavelet method. [ABSTRACT FROM AUTHOR]

Europay-MasterCard-Visa (EMV) standard aims to improve the security and reliability of smartcards. The main concern of this contribution is to detect vulnerabilities in an EMV transaction between terminal and EMV card. In this paper, we propose a new methodology for vulnerabilities detection based on Deterministic finite automaton (DFA). In fact, we use, as a starting point, the machine state diagram which models the specifications of a secure transaction between a terminal and a payment card. Then, we provide the DFA based on this transition state graph. We also provide the implementation of our DFA in order to recognize valid and invalid patterns automatically. Our tests proved the efficiency of our algorithm and its ability to recognize the vulnerabilities in terms of sequence of orders sent by the terminal to the EMV card. [ABSTRACT FROM AUTHOR]

Let Σ be an alphabet. A subset X of the free monoid Σ* is a code over Σ if for all m, n ≥ 1 and x1, ..., xn, y1, ... ym ∈ X, the condition : xn, y1, ... ym implies n = m and xi = yi for i = 1, ..., n. In other words, a set X is a code if any word in X can be written uniquely as a product of words in X ([BP84]). It is not always easy to verify a given set of words is a code. In this paper, we give the construction and representation by deterministic finite automata of some variable length codes. [ABSTRACT FROM AUTHOR]

The aliasing probability (AP) of a Built-In Self-Test (BIST)architecture is the probability that an error response gets classified as agood response. A general technique to determine the AP for many common andalternative BIST response analysis (RA) architectures is presented here.This technique models the RA circuit as a Deterministic Finite Automaton(DFA), and determines the AP by counting the ratio of strings accepted bythe DFA to the total number of possible error strings. The strings acceptedby a DFA can be calculated by counting the paths in the DFA‘s statetransition graph (STG). Moreover, if the STG is complete, then theAP(k) = ((1/N)Nk-1)/(Nk-1), where k is the testlength and N is the number of states and input symbols. Thistechnique is demonstrated by determining the APs for the following RAarchitectures: Multiple-Input Shift Registers (MISRs), Cellular Automata(CA), Linear Feedback Shift Registers (LFSRs), accumulators, and a set ofalternative architectures directly based on DFAs. This paper also shows howthe adjacency matrix of the STG can be used to directly determine the AP ofany RA architecture modeled as a DFA. Finally, the eigenvalues andeigenvectors of the DFA‘s STG adjacency matrix are used to derive generalexpressions for the DFA‘s AP. [ABSTRACT FROM AUTHOR]

DFA(deterministic finite automata) is very important to achieve deep packet inspection (deep packet inspection，DPI) technology. With the growing number of deep packet inspection rules, the storage space of DFA expands rapidly. Therefore, this paper presented an effective compression algorithm based character replacement. Using the characteristics that the state transition table in each state is often only a few different jumps, it decomposed the state transition table into the remaining table and the character replacement table to make storage space reduce. In addition，many similar states could share the same character replacement table to further compress the storage space. Finally，it presented an O(n2) compression algorithm which n denoted the number of DFA states. The test results show that the proposed algorithm is more stable compression ratio on the L7-filter and Snort rule set，and the compression ratio is below 5% . [ABSTRACT FROM AUTHOR]

The concept of promise problems was introduced and started to be systematically explored by Even, Selman, Yacobi, Goldreich, and other scholars. It has been argued that promise problems should be seen as partial decision problems and as such that they are more fundamental than decision problems and formal languages that used to be considered as the basic ones for complexity theory. The main purpose of this paper is to explore the promise problems accepted by classical, quantum and also semi-quantum finite automata. More specifically, we first introduce two acceptance modes of promise problems, recognizability and solvability , and explore their basic properties. Afterwards, we show several results concerning descriptional complexity on promise problems. In particular, we prove: (1) there is a promise problem that can be recognized exactly by measure-once one-way quantum finite automata (MO-1QFA), but no deterministic finite automata (DFA) can recognize it; (2) there is a promise problem that can be solved with error probability ϵ ≤ 1 / 3 by one-way finite automaton with quantum and classical states (1QCFA), but no one-way probability finite automaton (PFA) can solve it with error probability ϵ ≤ 1 / 3 ; and especially, (3) there are promise problems A ( p ) with size p that can be solved with any error probability by MO-1QFA with only two quantum basis states, but they can not be solved exactly by any MO-1QFA with two quantum basis states; in contrast, the minimal PFA solving A ( p ) with any error probability (usually smaller than 1/2) has p states. Finally, we mention a number of problems related to promise for further study. [ABSTRACT FROM AUTHOR]

Copyright of Transactions of Beijing Institute of Technology is the property of Beijing University of Technology and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Approximate pattern matching (APM) targets to find the occurrences of a pattern inside a subject text allowing a limited number of errors. It has been widely used in many application areas such as bioinformatics and information retrieval. Bit-parallel APM takes advantage of the intrinsic parallelism of bitwise operations inside a machine word. This approach typically encodes non-deterministic finite automaton (NFA) states or value differences between adjacent cells of a dynamic programming matrix in the form of bit arrays. Wu–Manber (WM) is a well-known bit-parallel APM algorithm, which simulates an NFA and gains parallel efficiency by performing multiple state updates within a machine word. An important parameter is the machine word size (e.g. 32 or 64 bits for CPUs). Due to increasing vector capabilities, efficient mapping of bit-parallel APM algorithms onto modern high performance computing architectures is an interesting research topic. Prominent examples are Xeon Phi coprocessors and CUDA-enabled GPUs, which provide words of size 512 bits (by means of vector registers) and 1024 bits (by means of warps), respectively. In this paper, we investigate mappings of the WM algorithm onto these two accelerator types. Both architectures are able to achieve around two orders-of-magnitude speedups compared to a single-threaded CPU implementation. Moreover, our tile-based implementation on a GeForce Titan graphics card runs up to 2.9 × faster than our implementation on an Intel Xeon Phi 5110P. Source code is available at http://xbitpar.sourceforge.net . [ABSTRACT FROM AUTHOR]

In the literature, there exist several interesting hybrid models of finite automata which have both quantum and classical states. We call them semi-quantum finite automata. In this paper, we compare the descriptional power of these models and DFA. Specifically, we present a uniform method that gives a lower bound on the size of the three existing main models of semi-quantum finite automata, and this bound shows that semi-quantum finite automata can be at most exponentially more concise than DFA. Compared with a recent work [4] , our method has the following two advantages: (i) it is much more concise; and (ii) it is universal, since it is applicable to the three existing main models of semi-quantum finite automata, instead of only one specific model. [ABSTRACT FROM AUTHOR]

The role of network security systems such as network intrusion detection system (NIDS) has become more important. The regular expression (a.k.a. regex) matching algorithm used for inspecting the payloads of packets is one of the most intensive tasks in NIDS. When multiple regular expressions are processed together, the corresponding Deterministic Finite Automata (DFA) becomes so complicated and needs a large amount of memory. In this paper, we propose a memory efficient parallel compatible DFA algorithm that uses the techniques of compression and pattern segmentation to reduce the memory usage. Extended from PFAC (Parallel Failureless-AC) algorithm4, the proposed compressed and segmented DFA (CSDFA) needs less numbers of states and transitions than δFA. Without considering the leading symbols “.*” in the regular expressions, the transition table can be compressed very efficiently by the run-length encoding. The number of transitions in CSDFA is about a half of the transitions needed in δFA, and uses only 74% of the memory consumed by δFA. Based on our experiments, the throughput of the proposed CSDFA is also much better than δFA. [ABSTRACT FROM AUTHOR]