Narrow Results

Finite Deterministic Cover Automata (DFCA) can be obtained from Deterministic Finite Automata (DFA) using the similarity relation and a method of merging similar states. The DFCA minimization procedure can yield different results depending on the order of merging the similar states, because the minimal DFCA for a finite language is in general not unique.

We count the number of minimal DFCA that can be obtained from a given minimal DFA with n states by merging the similar states in the given DFA. We compute an upper-bound for this number and prove that in the worst case, it is n-1 for an unary alphabet, and for a non-unary alphabet. We prove that this upper-bound is reached, i.e., for any given positive integer n one can construct a minimal DFA with n states, which has the number of minimal DFCA obtained by merging similar states equal to this maximum expression.

We extend an algorithm by Paige and Tarjan that solves the coarsest stable refinement problem to the domain of trees. The algorithm is used to minimize nondeterministic tree automata (NTA) with respect to bisimulation. We show that our algorithm has an overall complexity of , where is the maximum rank of any symbol in the input alphabet, m is the total size of the transition table, and n is the number of states.

Two formal languages are f-equivalent if their symmetric difference L₁ Δ L₂ is a finite set — that is, if they differ on only finitely many words. The study of f-equivalent languages, and particularly the DFAs that accept them, was recently introduced [3]. First, we restate the fundamental results in this new area of research. Second, we introduce our main result, which is a faster algorithm for the natural minimization problem: given a starting DFA D, find the smallest (by number of states) DFA D′ such that L(D) and L(D′) are f-equivalent. Finally, we suggest a technique that combines this hyper-minimization with the well-studied notion of a deterministic finite cover automaton [2, 4, 5], or DFCA, thereby extending the applicability of DFCAs from finite to infinite regular languages.

The consequences of regular expression hashing as a means of finite state automaton reduction is explored, based on variations of Brzozowski's algorithm. In this approach, each hash collision results in the merging of the automaton's states, and it is subsequently shown that a super-automaton will always be constructed, regardless of the hash function used. Since direct adaptation of the classical Brzozowski algorithm leads to a non-deterministic super-automaton, a new algorithm is put forward for constructing a deterministic FA. Approaches are proposed for measuring the quality of a hash function.

These ideas are empirically tested on a large sample of relatively small regular expressions and their associated automata, as well as on a small sample of relatively large regular expressions. Differences in the quality of tested hash functions are observed. Possible reasons for this are mentioned, but future empirical work is required to investigate the matter.

We show that for every deterministic bottom-up tree transducer, a unique equivalent transducer can be constructed which is minimal. The construction is based on a sequence of normalizing transformations which, among others, guarantee that non-trivial output is produced as early as possible. For a deterministic bottom-up transducer where every state produces either none or infinitely many outputs, the minimal transducer can be constructed in polynomial time.

Minimal deterministic finite automata (DFAs) can be reduced further at the expense of a finite number of errors. Recently, such minimization algorithms have been improved to run in time O(n log n), where n is the number of states of the input DFA, by [GAWRYCHOWSKI and JEŻ: Hyper-minimisation made efficient. Proc. MFCS, LNCS 5734, 2009] and [HOLZER and MALETTI: An n log n algorithm for hyper-minimizing a (minimized) deterministic automaton. Theor. Comput. Sci. 411, 2010]. Both algorithms return a DFA that is as small as possible, while only committing a finite number of errors. These algorithms are further improved to return a DFA that commits the least number of errors at the expense of an increased (quadratic) run-time. This solves an open problem of [BADR, GEFFERT, and SHIPMAN: Hyper-minimizing minimized deterministic finite state automata. RAIRO Theor. Inf. Appl. 43, 2009]. In addition, an experimental study on random automata is performed and the effects of the existing algorithms and the new algorithm are reported.

Hyper-minimization of deterministic finite automata (DFA) is a recently introduced state reduction technique that allows a finite change in the recognized language. A generalization of this lossy compression method to the weighted setting over semifields is presented, which allows the recognized weighted language to differ for finitely many input strings. First, the structure of hyper-minimal deterministic weighted finite automata is characterized in a similar way as in classical weighted minimization and unweighted hyper-minimization. Second, an efficient hyper-minimization algorithm, which runs in time , is derived from this characterization. Third, the closure properties of canonical regular languages, which are languages recognized by hyper-minimal DFA, are investigated. Finally, some recent results in the area of hyper-minimization are recalled.

Hyper-minimization is a recent automaton compression technique that can reduce the size of an automaton beyond the limits imposed by classical minimization. The additional compression power is enabled by allowing a finite difference in the represented language. The necessary theory for hyper-minimization is developed for (bottom-up) deterministic tree automata. The hyper-minimization problem for deterministic tree automata is reduced to the hyper-minimization problem for deterministic finite-state string automata, for which fast algorithms exist. The fastest algorithm obtained in this way runs in time , where m is the size of the transition table and n is the number of states of the input tree automaton.

We introduce planar directed acyclic graph algebras and present an explicit minimization method. The minimal simulation of a nondeterministic automaton on planar directed acyclic graphs is constructed.

The size of deterministic automata required for recognizing regular and $\omega$-regular languages is a well-studied measure for the complexity of languages. We introduce and study a new complexity measure, based on the sensing required for recognizing the language. Intuitively, the sensing cost quantifies the detail in which a random input word has to be read in order to decide its membership in the language. We study the sensing cost of regular and $\omega$-regular languages, as well as applications of the study in practice, especially in the monitoring and synthesis of reactive systems.

Order-preserving DAG grammars (OPDGs) is a formalism for representing languages of structurally restricted graphs. As demonstrated in [17], they are sufficiently expressive to model abstract meaning representations in natural language processing, a graph-based form of semantic representation in which nodes encode objects and edges relations. At the same time, they can be parsed in ${𝒪}(n^2+nm)$, where $m$ and $n$ are the sizes of the grammar and the input graph, respectively. In this work, we provide an initial algebra semantic for OPDGs, which allows us to view them as regular tree grammars under an equivalence theory. This makes it possible to transfer results from the field of formal tree languages to the domain of OPDGs, both in the unweighted and the weighted case. In particular, we show that deterministic OPDGs can be minimised efficiently, and that they are learnable under the “minimal adequeate teacher” paradigm, that is, by querying an oracle for equivalence between languages, and membership of individual graphs. To conclude, we demonstrate that the languages generated by OPDGs are definable in monadic second-order logic.

Many difficult open problems in theoretical computer science center around non-determinism. We study the fundamental problem of converting a given deterministic finite automaton (DFA) to a minimal nondeterministic finite automaton (NFA). Despite extensive work on finite automata, this fundamental problem has remained open. Recently, we studied this problem and showed that this (and related) problems are computationally hard.¹¹ Herewe study the restriction of this problem to the case when the input DFA is over a one-letter alphabet. Even in this restricted case the problem is computationally hard even though our evidence of hardness is different from (and is weaker than) the standard ones such as NP-hardness. Let A→B denote the problem of converting a finite automaton of type A to a minimal finite automaton of type B. Our main result is that DFA→NFA, when the input is a unary cyclic DFA (a DFA whose graph is a simple cycle), is in NP but not in P unless NP⊆DTIME (n^{O(log n)}). Our work was also motivated by the problem of finding structurally simple “normal forms” of NFA’s over a unary alphabet. We present some normal forms for minimal NFA’s over a unary alphabet and present an application to lower bounds on the size complexity of an NFA. In fact, the normal form result is used in a nontrivial manner to show the NP membership result stated above.

Starting from the derivation of an analytical method to expand measured static displacement data to full degrees of freedom, this study proposes a damage detection method to detect the damage of damaged beam by introducing displacement curvature and damage factor (DF). The validity of the proposed method is evaluated in damaged beam system that two simple beams are perpendicularly interconnected at a point.

An algorithm is proposed in this paper that finds exact exclusive-or sum-of-products of an arbitrary function, provided the number of product terms is less than eight. If the number of product terms in the minimal expression is more than seven, then the algorithm detects it and heuristically returns near-optimal expressions. The algorithm is time and space efficient even for functions with many input variables.

This paper deals with the use of a minimal model for performing secure computations. The communication is based on a protocol which makes use of disjoint function decomposition and more precisely of minimal ESCT (Exclusive-or Sum of Complex Terms) expressions in order to perform a secure computation. The complexity of this protocol is directly proportional to the size of the ESCT expression in use, which is much smaller in comparison to other proposed minimal models (e.g., ESOP). Moreover, quantum algorithms are discussed that provide significant speedup to the process of producing the ESCT expressions, when compared to conventional ones. Hence, this paper provides a very useful application of the ESCT expressions in the field of cryptographic protocols.

Using logic gates is the traditional way of designing logic circuits. However, in many cases, the use of modules is advantageous as the module is considered a uniform structure composed of multiple gates. In this paper, a nonlinear approach is proposed for designing logic circuits for use as modules multiplexers (MUXs) or Reed–Muller universal blocks (RMs). The experimental results show that the method gives better results compared to other methods available in the literature. The main advantages of the method are that it guarantees minimality and it can also handle Boolean functions for incompletely specified functions. The method is general enough and can be used for any kind of modules.

Software regression testing techniques verify previous functionalities each time software modifications occur or new characteristics are added. With the aim of gaining a better understanding of this subject, in this work we present a survey of software regression testing techniques applied in the last 15 years; taking into account its application domain, kind of metrics they use, its application strategies and the phase of the software development process where they are applied. From an outcome of 460 papers, a set of 25 papers describing the use of 31 software testing regression techniques were identified. Results of this survey suggest that at the time of applying a regression testing techniques, metrics like cost and fault detection efficiency are the most relevant. Most of the techniques were assessed with instrumented programs (experimental cases) under academic settings. Conversely, we observe a minimum set of software regression techniques applied in industrial settings, mainly, under corrective and maintenance approaches. Finally, we observe a trend using some regression techniques under agile approaches.

A key basis for seeking solutions of the Camassa–Holm equation is to understand the associated spectral problem

Software-Defined Networking disassociates the control plane from data plane. The problem of deciding upon the number and locations of controllers and assigning switches to them has attracted the attention of researchers. Foreseeing the possibility of failure of a controller, a backup controller has to be maintained for each switch so that the switches assigned to the failed controller can immediately be connected to their backup controllers. Hence, the switches cannot experience disconnections in case of failure of their controller. In this paper, two mathematical models are proposed. The first model focuses on minimizing the average of latencies from all switches to their backup controllers while considering the failure of the controllers. The second model aims at minimizing both the average and worst-case of latencies from all switches to the corresponding backup controllers. Both of our models are evaluated on three networks and are compared (in terms of two metrics, viz., average and worst-case latencies) with an existing model that focuses on minimizing only worst-case latency. The first model gives better average latency compared to the reference model. The second model also gives better average latency and almost equal worst-case latency compared to the reference model.

In this paper, a new modified harmonic balance method is presented for the nonlinear aeroelastic analysis of two degree-of-freedom airfoils. Using this method, the nonlinear problem is first translated into a minimization problem, and the Particle Swarm Optimization which has high calculation efficiency is adopted to solve the problem. The proposed method is used to solve the nonlinear aeroelastic behavior of supersonic airfoil, with the unsteady aerodynamic load evaluated by the piston theory. Three examples of nonlinear aeroelasticity with significantly different coefficients are prepared, in which the frequencies and amplitudes of the limit cycles are obtained. The results show that the present current method is computationally more efficient.