Search

We look at nondeterministic finite automata augmented with multiple reversal-bounded counters where, during an accepting computation, the behavior of the counters is specified by some fixed pattern. These patterns can serve as a useful "bridge" to other important automata and grammar models in the theoretical computer science literature, thereby helping in their study. Various pattern behaviors are considered, together with characterizations and comparisons. For example, one such pattern defines exactly the smallest full trio containing all the bounded semilinear languages. Another pattern defines the smallest full trio containing all the bounded context-free languages. The "bridging" to other families is then applied, e.g. to certain Turing machine restrictions, as well as other families. Certain general decidability properties are also studied using this framework., 28 pages, 1 figure

We present an active learning algorithm named NRTALearning for nondeterministic real-time automata (NRTAs). Real-time automata (RTAs) are a subclass of timed automata with only one clock which resets at each transition. First, we prove the corresponding Myhill-Nerode theorem for real-time languages. Then we show that there exists a unique minimal deterministic real-time automaton (DRTA) recognizing a given real-time language, but the same does not hold for NRTAs. We thus define a special kind of NRTAs, named residual real-time automata (RRTAs), and prove that there exists a minimal RRTA to recognize any given real-time language. This transforms the learning problem of NRTAs to the learning problem of RRTAs. After describing the learning algorithm in detail, we prove its correctness and polynomial complexity. In addition, based on the corresponding Myhill-Nerode theorem, we extend the existing active learning algorithm NL* for nondeterministic finite automata to learn RRTAs. We evaluate and compare the two algorithms on two benchmarks consisting of randomly generated NRTAs and rational regular expressions. The results show that NRTALearning generally performs fewer membership queries and more equivalence queries than the extended NL* algorithm, and the learnt NRTAs have much fewer locations than the corresponding minimal DRTAs. We also conduct a case study using a model of scheduling of final testing of integrated circuits.

Let $NFA_b(q)$ denote the set of languages accepted by nondeterministic finite automata with $q$ states over an alphabet with $b$ letters. Let $B_n$ denote the set of words of length $n$. We give a quadratic lower bound on the VC dimension of \[ NFA_2(q)\cap B_n = \{L\cap B_n \mid L \in NFA_2(q)\} \] as a function of $q$. Next, the work of Gruber and Holzer (2007) gives an upper bound for the nondeterministic state complexity of finite languages contained in $B_n$, which we strengthen using our methods. Finally, we give some theoretical and experimental results on the dependence on $n$ of the VC dimension and testing dimension of $NFA_2(q)\cap B_n$., Comment: ISAIM 2020 (International Symposium on Artificial Intelligence and Mathematics), Fort Lauderdale, FL. January 6--8, 2020. Accepted for publication in Annals of Mathematics and Artificial Intelligence

We introduce a new measure of descriptional complexity on finite automata, called the number of active states. Roughly speaking, the number of active states of an automaton A on input w counts the number of different states visited during the most economic computation of the automaton A for the word w. This concept generalizes to finite automata and regular languages in a straightforward way. We show that the number of active states of both finite automata and regular languages is computable, even with respect to nondeterministic finite automata. We further compare the number of active states to related measures for regular languages. In particular, we show incomparability to the radius of regular languages and that the difference between the number of active states and the total number of states needed in finite automata for a regular language can be of exponential order.

We study the NFA reductions by invariant equivalences and preorders. It is well-known that the NFA minimization problem is PSPACE-complete. Therefore, there have been many approaches to reduce the size of NFAs in low polynomial time by computing invariant equivalence or preorder relation and merging the states within same equivalence class. Here we consider the nondeterminism reduction of NFAs by invariant equivalences and preorders. We, in particular, show that computing equivalence and preorder relation from the left is more useful than the right for reducing the degree of nondeterminism in NFAs. We also present experimental evidence for showing that NFA reduction from the left achieves the better reduction of nondeterminism than reduction from the right.

This paper presents a new method to translate a regular expression into a nondeterministic finite automaton (an NFA for short). Letrbe a regular expression and letMbe a Thompson automaton forr. We first introduce a labeled Thompson automaton defined by assigning two types of expressions which denote prefixes and suffixes of words inL(r) to each state ofM. Then we give new ϵ-free NFAs constructed from a labeled Thompson automaton. These NFAs are calleda prefix equation automatonanda suffix equation automaton. We show that a suffix equation automaton is isomorphic to an equation automaton defined by Antimirov. Furthermore we give an NFA calleda unified equation automatonby joining two NFAs. Thus the number of states of a unified equation automaton can be smaller than that of an equation automaton., Article, IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS E104D(3) : 381-388(2021)

The Closest Substring problem asks whether there exists a consensus string w of given length l such that each string in a set of strings L has a substring whose edit distance is at most r (called the radius) from w. The Closest Substring problem has been studied for finite sets of strings and is known to be NP -hard. We show that the Closest Substring problem for regular languages represented by nondeterministic finite automata (NFA) is PSPACE -complete. The problem remains PSPACE -hard even when the input is a deterministic finite automaton and the length l and radius r are given in unary. Also we show that the Closest Substring problem for acyclic NFAs lies in the second level of the polynomial-time hierarchy and is both NP -hard and coNP -hard.

The goal of this paper is to develop the parallel algorithms that, on input of a learning sample, identify a regular language by means of a nondeterministic finite automaton (NFA). A sample is a pair of finite sets containing positive and negative examples. Given a sample, a minimal NFA that represents the target regular language is sought. We define the task of finding an NFA, which accepts all positive examples and rejects all negative ones, as a constraint satisfaction problem, and then propose the parallel algorithms to solve the problem. The results of comprehensive computational experiments on the variety of inference tasks are reported. The question of minimizing an NFA consistent with a learning sample is computationally hard.

Deep neural networks (DNNs) are known to be inherently vulnerable to malicious attacks such as the adversarial attack and the backdoor attack. The former is crafted by adding small perturbations to benign inputs so as to fool a DNN. The latter generally embeds a hidden pattern in a DNN by poisoning the dataset during the training process, which causes the infected model to misbehave on predefined inputs with a specific trigger and normally perform for others. Much work has been conducted on defending against the adversarial samples, while the backdoor attack received much less attention, especially in recurrent neural networks (RNNs), which play an important role in the text processing field. Two main limitations make it hard to directly apply existing image backdoor detection approaches to RNN-based text classification systems. First, a layer in an RNN does not preserve the same feature latent space function for different inputs, making it impossible to map the inserted specific pattern with the neural activations. Second, the text data is inherently discrete, making it hard to optimize the text like image pixels. In this work, we propose a novel backdoor detection approach named InterRNN for RNN-based text classification systems from the interpretation perspective. Specifically, we first propose a novel RNN interpretation technique by constructing a nondeterministic finite automaton (NFA) based abstract model, which can effectively reduce the analysis complexity of an RNN while preserving its original logic rules. Then, based on the abstract model, we can obtain interpretation results that explain the fundamental reason behind the decision for each input. We then detect trigger words by leveraging the differences between the behaviors in the backdoor sentences and those in the normal sentences. The extensive experiment results on four benchmark datasets demonstrate that our approach can generate better interpretation results compared to state-of-the-art approaches and effectively detect backdoors in RNNs.

We study two simple yet general complexity classes, which provide a unifying framework for efficient query evaluation in areas like graph databases and information extraction, among others. We investigate the complexity of three fundamental algorithmic problems for these classes: enumeration, counting and uniform generation of solutions, and show that they have several desirable properties in this respect. Both complexity classes are defined in terms of non deterministic logarithmic-space transducers (NL transducers). For the first class, we consider the case of unambiguous NL transducers, and we prove constant delay enumeration, and both counting and uniform generation of solutions in polynomial time. For the second class, we consider unrestricted NL transducers, and we obtain polynomial delay enumeration, approximate counting in polynomial time, and polynomialtime randomized algorithms for uniform generation. More specifically, we show that each problem in this second class admits a fully polynomial-time randomized approximation scheme (FPRAS) and a polynomial-time Las Vegas algorithm (with preprocessing) for uniform generation. Remarkably, the key idea to prove these results is to show that the fundamental problem #NFA admits an FPRAS, where #NFA is the problem of counting the number of strings of length n (given in unary) accepted by a non-deterministic finite automaton (NFA). While this problem is known to be #P-complete and, more precisely, SpanL-complete, it was open whether this problem admits an FPRAS. In this work, we solve this open problem, and obtain as a welcome corollary that every function in SpanL admits an FPRAS.

PurposeWith the rapid growth of wireless sensor networks (WSNs), they have become an integral and substantial part of people's life. As such WSN stands as an assuring outlook, but because of sensor's resource limitations and other prerequisites, optimal dual route discovery becomes an issue of concern. WSN along with central sink node is capable of handling wireless transmission, thus optimizing the network's lifetime by selecting the dual path. The major problem confronted in the application of security mechanisms in WSNs is resolving the issues amid reducing consumption of resources and increases security.Design/methodology/approachAccording to the proposed system, two metrics, namely, path length and packets delivery ratio are incorporated for identifying dual routes amid the source and destination. Thereafter by making use of the distance metric, the optimal dual route is chosen and data transmission is carried out amid the nodes. With the usage of the recommended routing protocol high packet delivery ratio is achieved with reduced routing overhead and low average end to end delay. It is clearly portrayed in the simulation output that the proposed on demand dual path routing protocol surpasses the prevailing routing protocol. Moreover, security is achieved make use of in accord the data compression reduces the size of the data. With the help of dual path, mathematical model of Finite Automata Theory is derived to transmit data from source to destination. Finite Automata Theory comprises Deterministic Finite Automata (DFA) that is being utilized for Dual Path Selection. In addition, data transition functions are defined for each input stage. In this proposed work, another mathematical model is 10; introduced to efficiently choose an alternate path between a receiver and transmitter for data transfer with qualified node as relay node using RR Algorithm. It also includes Dynamic Mathematical Model for Node Localization to improve the precision in location estimation using Node Localization Algorithm. As a result a simulator is built and various scenarios are elaborated for comparing the performance of the recommended dual path routing protocol with respect to the prevailing ones.FindingsReliability and fault-tolerance: The actual motive in utilizing the approach of multipath routing in sensor network was to offer path resilience in case of a node or link failures thus ascertaining reliable transmission of data. Usually in a fault tolerant domain, when the sensor node is unable to forward the data packets to the sink, alternative paths can be utilized for recovering its data packets during the failure of any link/node. Load balancing: Load balancing involves equalizing energy consumption of all the existing nodes, thereby degrading them together. Load balancing via clustering improves network scalability. The network's lifetime as well as reliability can be extended if varied energy level's nodes exist in sensor node. Quality of service (QoS): Improvement backing of quality of service with respect to the data delivery ratio, network throughput and end-to-end latency stands very significant in building multipath routing protocols for various network types. Reduced delay: There is a reduced delay in multipath routing since the backup routes are determined at the time of route discovery. Bandwidth aggregation: By dividing the data toward the same destination into multiple streams (by routing all to a separate path) can aggregate the effective bandwidth. The benefit being that, in case a node possesses many links with low bandwidth, it can acquire a bandwidth which is more compared to the individual link.Research limitations/implicationsFew more new algorithms can be used to compare the QoS parameters.Practical implicationsProposed mechanism with feedback ascertains improvised delivery ratio compared to the single path protocol since in case of link failure, the protocol has alternative route. In case there are 50 nodes in the network, the detection mechanism yields packet delivery of 95% and in case there are 100 nodes, the packet delivery is lowered to 89%. It is observed that the packet rate in the network is more for small node range. When the node count is 200, the packet ratio is low, which is lowered to 85%. With a node count of 400, the curve depicts the value of 87%. Hence, even with a decrease in value, it is superior than the existing protocols. The average end-to-end delay represents the transmission delay of the data packets that have been successfully delivered as depicted in Figure 6 and Table 3. The recommended system presents the queue as well as the propagation delay from the source to destination. The figure depicts that when compared to the single path protocol, the end-to-end delay can be reduced via route switching. End-to-end delay signifies the time acquired for the delay in the receival of the the retransmitted packet by each node. The comparison reveals that the delay was lower compared to the existing ones in the WSN. Proposed protocol aids in reducing consumption of energy in transmitter, receiver and various sensors. Comparative analysis of energy consumptions of the sensor in regard to the recommended system must exhibit reduced energy than the prevailing systems.Originality/valueOn demand dual path routing protocol. Hence it is verified that the on demand routing protocol comprises DFA algorithms determines dual path. Here mathematical model for routing between two nodes with relay node is derived using RR algorithm to determine alternate path and thus reduce energy consumption. Another dynamic mathematical model for node localization is derived using localization algorithm. For transmitting data with a secure and promising QoS in the WSNs, the routing optimization technique has been introduced. The simulation software environment follows the DFA. The simulation yields in improvised performance with respect to packet delivery ratio, throughput, average end-to-end delay and routing overhead. So, it is proved that the DFA possesses the capability of optimizing the routing algorithms which facilitates the multimedia applications over WSNs.

Deterministic finite automata are one of the simplest and most practical models of computation studied in automata theory. Their conceptual extension is the non-deterministic finite automata which also have plenty of applications. In this article, we study these models through the lens of succinct data structures where our ultimate goal is to encode these mathematical objects using information-theoretically optimal number of bits along with supporting queries on them efficiently. Towards this goal, we first design a succinct data structure for representing any deterministic finite automaton $\mathcal{D}$ having $n$ states over a $\sigma$-letter alphabet $\Sigma$ using $(\sigma-1) n\log n + O(n \log \sigma)$ bits of space, which can determine, given an input string $x$ over $\Sigma$, whether $\mathcal{D}$ accepts $x$ in $O(|x| \log \sigma)$ time, using constant words of working space. When the input deterministic finite automaton is acyclic, not only we can improve the above space-bound significantly to $(\sigma -1) (n-1)\log n+ 3n + O(\log^2 \sigma) + o(n)$ bits, we also obtain optimal query time for string acceptance checking. More specifically, using our succinct representation, we can check if a given input string $x$ can be accepted by the acyclic deterministic finite automaton using time proportional to the length of $x$, hence, the optimal query time. We also exhibit a succinct data structure for representing a non-deterministic finite automaton $\mathcal{N}$ having $n$ states over a $\sigma$-letter alphabet $\Sigma$ using $\sigma n^2+n$ bits of space, such that given an input string $x$, we can decide whether $\mathcal{N}$ accepts $x$ efficiently in $O(n^2|x|)$ time. Finally, we also provide time and space-efficient algorithms for performing several standard operations such as union, intersection, and complement on the languages accepted by deterministic finite automata.

Network intrusion detection systems (NIDS) can be evaded by carefully crafted packets that exploit implementation-level discrepancies between how they are processed on the NIDS and at the endhosts. These discrepancies arise due to the plethora of endhost implementations and evolutions thereof. It is prohibitive to proactively employ a large set of implementations at the NIDS and check incoming packets against all of those. Hence, NIDS typically choose simplified implementations that attempt to approximate and generalize across the different endhost implementations. Unfortunately, this solution is fundamentally flawed since such approximations are bound to have discrepancies with some endhost implementations. In this paper, we develop a lightweight system Themis, which empowers the NIDS in identifying these discrepancies and reactively forking its connection states when any packets with "ambiguities" are encountered. Specifically, Themis incorporates an offline phase in which it extracts models from various popular implementations using symbolic execution. During runtime, it maintains a nondeterministic finite automaton to keep track of the states for each possible implementation. Our extensive evaluations show that Themis is extremely effective and can detect all evasion attacks known to date, while consuming extremely low overhead. En route, we also discovered multiple previously unknown discrepancies that can be exploited to bypass current NIDS.

The paper determines the number of states in finite automata necessary to represent “unambiguous” variants of the union, concatenation, and Kleene star operations on formal languages. For the disjoint union of languages represented by an m-state and an n-state deterministic finite automata (DFA), the state complexity is m n − 1 ; for the unambiguous concatenation, it is known to be m 2 n − 1 − 2 n − 2 (Daley et al., “Orthogonal concatenation: language equations and state complexity” , J. UCS, 2010), and this paper shows that this number of states is necessary already over a binary alphabet; for the unambiguous star, the state complexity function is determined to be 3 8 2 n + 1 . In the case of a unary alphabet, disjoint union requires up to 1 2 m n states in a DFA, unambiguous concatenation has state complexity m + n − 2 , and unambiguous star requires n − 2 states in the worst case. For nondeterministic finite automata, as well as for unambiguous finite automata, the complexity for disjoint union is m + n , for unambiguous concatenation, square, and star, the resulting complexities are m + n , 2n, and n + 1 , respectively, and all of them are witnessed by binary languages. In the unary nondeterministic or unambiguous case, the corresponding complexities are m + n for disjoint union, m + n − 1 and 2 n − 1 for unambiguous concatenation and square, respectively, and n − 1 for unambiguous star.

Problems from a wide variety of application domains can be modeled as “nondeterministic finite automaton” (NFA) and hence, efficient execution of NFAs can improve the performance of several key applications. However, traditional architectures, such as CPU and GPU are not inherently suited for executing NFAs, and hence, special-purpose architectures are required for accelerating them. Micron’s automata processor (AP) exploits massively parallel in-memory processing capability of DRAM for executing NFAs and hence, it can provide orders of magnitude performance improvement compared to traditional architectures. In this paper, we present a survey of techniques that propose architectural optimizations to AP and use it for accelerating problems from various application domains. This paper will be useful not only for computer architects and processor-designers, but also for researchers in the field of bioinformatics, data-mining, machine learning and others.

We introduce the concept of one-time nondeterminism as a new kind of limited nondeterminism for finite state machines and pushdown automata. Roughly speaking, one-time nondeterminism means that at the outset the computation is nondeterministic, but whenever it performs a guess, this guess is fixed for the rest of the computation. We characterize the computational power of one-time nondeterministic finite automata (OTNFAs) and one-time nondeterministic pushdown devices. Moreover, we study the descriptional complexity of these machines. For instance, we show that for an [Formula: see text]-state OTNFA with a sole nondeterministic state, that is nondeterministic for only one input symbol, [Formula: see text] states are sufficient and necessary in the worst case for an equivalent deterministic finite automaton. In case of pushdown automata, the conversion of a nondeterministic to a one-time nondeterministic as well as the conversion of a one-time nondeterministic to a deterministic one turn out to be non-recursive, that is, the trade-offs in size cannot be bounded by any recursive function.

Consider a regular expression r of length m and a text string T of length n over an alphabet Σ. Then, the RE shortest substring search problem is to find all shortest substrings of T matching r. The previous algorithm proposed by Clarke and Cormack uses an e-free nondeterministic finite automaton (NFA) and runs in O ( k s n ) time and O ( s ) space, where k is the maximum number of outgoing transitions for any state and symbol, and s is the number of states. Generally, an e-free NFA obtained from a regular expression has s = O ( m ) and k = O ( m ) ; thus the algorithm takes O ( m 2 n ) time and O ( m ) space. We propose a faster algorithm that runs in O ( m n ) time and O ( m ) space. The proposed algorithm is based on a Thompson automaton which is an NFA with e-transitions.

In this paper, a semi-tensor product (STP) approach is proposed to discuss the stability problem of a constrained switching system (CSS). The switching sequence is subject to the constraint of a nondeterministic finite automaton (NFA). By the mathematical tool, the constrained joint spectral radius (CJSR) of the CSS can be approximated. We propose the equivalence of a matrix-based expression of the CSS and its lifted l-dimensional switching system by using the STP approach. After that, the approximate relation between the constrained joint spectral radius (CJSR) /the constrained generalized spectral radius (CGSR) and the joint spectral radius (JSR)/ generalized spectral radius (GSR) is developed for the switching system. At the same time, there is a special case of NFA, where the equivalence relation between them also is proved.

International audience; Grammatical inference is concerned with the study of algorithms for learning automata and grammars from words. We focus on learning Nondeterministic Finite Automaton of size k from samples of words. To this end, we formulate the problem as a SAT model. The generated SAT instances being enormous, we propose some model improvements, both in terms of the number of variables, the number of clauses, and clauses size. These improvements significantly reduce the instances, but at the cost of longer generation time. We thus try to balance instance size vs. generation and solving time. We also achieved some experimental comparisons and we analyzed our various model improvements.

Counting the number of words of a certain length accepted by a non-deterministic finite automaton (NFA) is a fundamental problem, which has many applications in different areas such as graph databases, knowledge compilation, and information extraction. Along with this, generating such words uniformly at random is also a relevant problem, particularly in scenarios where returning varied outputs is a desirable feature. The previous problems are formalized as follows. The input of #NFA is an NFA N and a length k given in unary (that is, given as a string 0^k), and then the task is to compute the number of strings of length k accepted by N. The input of GEN-NFA is the same as #NFA, but now the task is to generate uniformly, at random, a string accepted by N of length k. It is known that #NFA is #P-complete, so an efficient algorithm to compute this function exactly is not expected to exist. However, this does not preclude the existence of an efficient approximation algorithm for it. In this talk, we will show that #NFA admits a fully polynomial-time randomized approximation scheme (FPRAS). Prior to our work, it was open whether #NFA admits an FPRAS; in fact, the best randomized approximation scheme known for #NFA ran in time n^O(log(n)). Besides, we will mention some consequences and applications of our results. In particular, from well-known results on counting and uniform generation, we obtain that GEN-NFA admits a fully polynomial-time almost uniform generator. Moreover, as #NFA is SpanL-complete under polynomial-time parsimonious reductions, we obtain that every function in the complexity class SpanL admits an FPRAS.

Computing theory analyzes abstract computational models to rigorously study the computational difficulty of various problems. Introductory computing theory can be challenging for undergraduate students, and the overarching goal of our research is to help students learn these computational models. The most common pedagogical tool for interacting with these models is the Java Formal Languages and Automata Package (JFLAP). We developed a JFLAP server extension, which accepts homework submissions from students, evaluates the submission as correct or incorrect, and provides a witness string when the submission is incorrect. Our extension currently provides witness feedback for deterministic finite automata, nondeterministic finite automata, regular expressions, context-free grammars, and pushdown automata. In Fall 2019, we ran a preliminary investigation on two synchronized sections (Control and Study) of the required undergraduate course Introduction to Computer Science Theory. The Study section (n=29) used our extension for five targeted homework questions, and the Control section (n=35) submitted these problems using traditional means. The Study section strongly outperformed the Control section with respect to the percent of perfect homework grades for the targeted homework questions. Our most interesting result was student persistence: with only the short witness string as feedback, students voluntarily persisted in submitting attempts until correct.

We introduce a new measure on regular languages: their nondeterministic syntactic complexity. It is the least degree of any extension of the ‘canonical boolean representation’ of the syntactic monoid. Equivalently, it is the least number of states of any subatomic nondeterministic acceptor. It turns out that essentially all previous structural work on nondeterministic state-minimality computes this measure. Our approach rests on an algebraic interpretation of nondeterministic finite automata as deterministic finite automata endowed with semilattice structure. Crucially, the latter form a self-dual category.