Search

A finite automaton can be either deterministic (DFA) or nondeterministic (NFA). An automaton‐based task is in general more efficient when performed with a DFA rather than an NFA. For any NFA there is an equivalent DFA that can be generated by the classical Subset Construction algorithm. When, however, a large NFA may be transformed into an equivalent DFA by a series of actions operating directly on the NFA, Subset Construction may be unnecessarily expensive in computation, as a (possibly large) deterministic portion of the NFA is regenerated as is, a waste of processing. This is why a conservative algorithm for NFA determinization is proposed, called Quick Subset Construction, which progressively transforms an NFA into an equivalent DFA instead of generating the DFA from scratch, thereby avoiding unnecessary processing. Quick Subset Construction is proven, both formally and empirically, to be equivalent to Subset Construction, inasmuch it generates exactly the same DFA. Experimental results indicate that, the smaller the number of repair actions performed on the NFA, as compared to the size of the equivalent DFA, the faster Quick Subset Construction over Subset Construction. [ABSTRACT FROM AUTHOR]

Discrete-event knowledge (DEK) consists in a variety of automaton-based data structures which are generated by knowledge-based and engineering systems, including intelligent diagnosis systems. Model-based diagnosis methods for discrete-event systems (DESs) are typically supported by large automata that allow for the efficient generation of the candidate diagnoses when the DES is being operated. However, the generation of the DEK may involve a determinization step, where a nondeterministic finite automaton (NFA) is transformed into an equivalent deterministic finite automaton (DFA) by means of the classical Subset Construction algorithm. When this determinization is performed online and the NFA is large, the diagnosis engine may slow down to such an extent that the entire diagnosis task is jeopardized. This is why a novel determinization algorithm is proposed, called Quick Subset Construction, which, instead of generating from scratch the equivalent DFA, removes the nondeterminism by operating directly on the NFA. This way, the larger the NFA and the smaller the portion of nondeterminism involved, the faster Quick Subset Construction will be over Subset Construction. Massive experimentation on large automata has confirmed this result empirically. [ABSTRACT FROM AUTHOR]

Input-driven pushdown automata (IDPDA) are pushdown automata where the next action on the pushdown store (push, pop, nothing) is solely governed by the input symbol. Nowadays such devices are usually defined such that popping from the empty pushdown does not block the computation but continues it with empty pushdown. Here, we consider IDPDAs that have a more balanced behavior concerning pushing and popping. Digging input-driven pushdown automata (DIDPDA) are basically IDPDAs that, when forced to pop from the empty pushdown, dig a hole of the shape of the popped symbol in the bottom of the pushdown. Popping further symbols from a pushdown having a hole at the bottom deepens the current hole furthermore. The hole can only be filled up by pushing symbols previously popped. We study the impact of the new behavior of DIDPDAs on their power and compare their capacities with the capacities of ordinary IDPDAs and tinput-driven pushdown automata which are basically IDPDAs whose input may be preprocessed by length-preserving finite state transducers. It turns out that the capabilities are incomparable. We address the determinization of DIDPDAs and their descriptional complexity, closure properties, and decidability questions. [ABSTRACT FROM AUTHOR]

Summary: A mutating finite automaton (MFA) is a nondeterministic finite automaton (NFA) that changes its morphology over discrete time by a sequence of mutations. This results in a sequence of NFAs, the initial NFA, and one mutated NFA for each mutation. Some application domains, including model‐based diagnosis of discrete‐event systems in artificial intelligence and model‐based testing in software engineering, require temporal determinization of MFAs. Determinizing an MFA temporally means generating a deterministic finite automaton (DFA) that is equivalent to the mutated NFA as soon as a mutation occurs. Since, in computation time, the classical Subset Construction determinization algorithm may be less than optimal when applied to MFAs, a conservative algorithm is proposed, called Subset Restructuring, which, instead of constructing the new DFA from scratch based on the mutated NFA, generates the new DFA by updating the previous DFA based on the mutation occurred. Subset Restructuring is sound and complete, thereby yielding the same DFA generated by Subset Construction. Results from massive experimentation indicate the viability of Subset Restructuring, especially so when large MFAs change by small mutations. [ABSTRACT FROM AUTHOR]

It is a well known fact that not all max-plus automata can be determinized, i.e. transformed into deterministic max-plus automata with the same behavior. A classical sequentialization procedure, extended in the literature to max-plus automata, succeeds in computing an equivalent deterministic max-plus automaton for important subclasses of max-plus automata. This procedure is based on the normalization of state vectors in order to detect and merge states which have similar future behavior. In this paper, a novel and weaker condition is proposed that still guarantees this property. This allows for a considerable improvement of the existing determinization procedure, because it terminates for a larger class of max-plus automata. [ABSTRACT FROM AUTHOR]

In this paper, we propose a canonization method for fuzzy automata, i.e., a determinization method that is able to return a minimal fuzzy deterministic automaton equivalent to the original fuzzy automaton. The canonization method is derived from the well-known Brzozowski's algorithm for ordinary nondeterministic automata. For a given fuzzy automaton A , we prove that the construction M ˆ (r (N (r (A)))) returns a minimal fuzzy deterministic automaton equivalent to A. In that construction, r (.) represents the reversal of a fuzzy automaton, N (.) is the determinization of a fuzzy automaton based on fuzzy accessible subset construction, and M ˆ (.) is the determinization of a fuzzy automaton via factorization of fuzzy states which also includes a simple reduction of a particular case of proportional fuzzy states. The method is accomplished for fuzzy automata with membership values over the Gödel structure (also called max-min fuzzy automata). These fuzzy automata are always determinizable and have been proved useful in practical applications. [ABSTRACT FROM AUTHOR]

The theory of formal languages widely uses finite state automata both in implementation of automata-based approach to programming, and in synthesis of logical control algorithms.To ensure unambiguous operation of the algorithms, the synthesized finite state automata must be deterministic. Within the approach to the synthesis of the mobile robot controls, for example, based on the theory of formal languages, there are problems concerning the construction of various finite automata, but such finite automata, as a rule, will not be deterministic. The algorithm of determinization can be applied to the finite automata, as specified, in various ways. The basic ideas of the algorithm of determinization can be most simply explained using the representations of a finite automaton in the form of a weighted directed graph.The paper deals with finite automata represented as weighted directed graphs, and discusses in detail the procedure for determining the finite automata represented in this way. Gives a detailed description of the algorithm for determining finite automata. A large number of examples illustrate a capability of the determinization algorithm.

This paper introduces the notion of multidimensional fuzzy finite tree automata (MFFTA) and investigates its closure properties from the area of automata and language theory. MFFTA are a superclass of fuzzy tree automata whose behavior is generalized to adapt to multidimensional fuzzy sets. An MFFTA recognizes a multidimensional fuzzy tree language which is a regular tree language so that for each dimension, a fuzzy membership grade is assigned to each tree. We study MFFTA by extending some classical problems and properties of automata and regular languages such as determinization, reduction, duality and operations on languages. Furthermore, we provided the method of converting every complete fuzzy tree automata to an MFFTA as well as an example to show the efficiency of MFFTA in comparison to FFTA. [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]

A mutating finite automaton (MFA) is a nondeterministic finite automaton (NFA) which changes its morphology over discrete time by a sequence of mutations, one mutation at each time instant. A mutation involves the insertion and/or removal of a set of states and/or transitions. This results in a sequence of NFAs, one mutated NFA for each mutation. Some application domains, including model-based diagnosis and monitoring of active systems in artificial intelligence and model-based testing in software engineering, require online determinization of MFAs. Determinizing an MFA online means generating a deterministic finite automaton (DFA) as soon as a mutation occurs, which is equivalent to the mutated NFA. Since the classical Subset Construction determinization algorithm may be inadequate for MFAs, a conservative algorithm is proposed, called Subset Restructuring, that generates the new DFA by restructuring the previous DFA based on the mutation occurred, instead of building it from scratch. Experimental results indicate the effectiveness of the approach, especially so when large MFAs change in time by small mutations. [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]

Deterministic timed automata are strictly less expressive than their non-deterministic counterparts, which are again less expressive than those with silent transitions. As a consequence, timed automata are in general non-determinizable. This is unfortunate since deterministic automata play a major role in model-based testing, observability and implementability. However, by bounding the length of the traces in the automaton, effective determinization becomes possible. We propose a novel procedure for bounded determinization of timed automata. The procedure unfolds the automata to bounded trees, removes all silent transitions and determinizes via disjunction of guards. The proposed algorithms are optimized to the bounded setting and thus are more efficient and can handle a larger class of timed automata than the general algorithms. We show how to apply the approach in a fault-based test-case generation method, called model-based mutation testing, that was previously restricted to deterministic timed automata. The approach is implemented in a prototype tool and evaluated on several scientific examples and one industrial case study. To our best knowledge, this is the first implementation of this type of procedure for timed automata. [ABSTRACT FROM AUTHOR]

Subset Construction (SC) is the classical algorithm for the determinization of a nondeterministic finite automaton (NFA) into an equivalent deterministic one (DFA). Although SC works fine in most application domains, it may be inappropriate when the NFA expands over time and determinization is required after each expansion, such as in diagnosis of active systems in artificial intelligence, or in model-based testing in software engineering. For such an expanding automaton, the IDEA algorithm (Incremental Determinization of Expanding Automata) may be more suitable. Given an NFA N, an equivalent DFA D, and an expansion ΔN of N, the determinization of N' = N ∪ ΔN into D' is performed based not only on N' but also on ΔN and D. Rather than starting from scratch the generation of the DFA D' equivalent to N', IDEA applies the set of actions which are sufficient for transforming D into D'. This way, a possibly large part of the determinization process is avoided. Experiments show that the degree of convenience in determinizing expanding automata using IDEA rather than SC largely depends on the nature of the expanding automaton in the actual application domain. [ABSTRACT FROM AUTHOR]

New algorithms for the determinization of nondeterministic visibly and nondeterministic real-time height-deterministic pushdown automata are presented. The algorithms improve the results of existing algorithms. They construct only accessible states and necessary pushdown symbols of the resulting deterministic pushdown automata. [ABSTRACT FROM AUTHOR]

In this paper we provide further improvements of determinization methods for fuzzy finite automata. These methods perform better than all previous determinization methods for fuzzy finite automata, developed by Bělohlávek [3] , Li and Pedrycz [38] , Ignjatović et al. [25] , and Jančić et al. [33] , in the sense that they produce smaller automata, while require the same computation time. The only exception is the Brzozowski type determinization algorithm developed recently by Jančić and Ćirić [34] , which produces a minimal crisp-deterministic fuzzy automaton, but the algorithms created here can also be used within the Brzozowski type algorithm and improve its performance. [ABSTRACT FROM AUTHOR]

In this paper we are interested in sequentialization of formal power series with coefficients in the semiring $(\mathbb {R}\cup \{- \infty \},\max ,+)$ which represent the behavior of timed Petri nets. Several approaches make it possible to derive nondeterministic (max, + ) automata modeling safe timed Petri nets. Their nondeterminism is a serious drawback since determinism is a crucial property for numerous results on (max, + ) automata (in particular, for applications to performance evaluation and control) and existing procedures for determinization succeed only for restrictive classes of (max, + ) automata. We present a natural semi-algorithm for determinization of behaviors based on the semantics of bounded timed Petri nets. The resulting deterministic (max, + ) automata can be infinite, but a sufficient condition called strong liveness is proposed to ensure the termination of the semi-algorithm. It is shown that strong liveness is closely related to bounded fairness, which has been widely studied for Petri nets and other models for concurrency. Moreover, if the net cannot be sequentialized we propose a restriction of its logical behavior so that the sufficient condition becomes satisfied for the restricted net. The restriction is based on the synchronous product with non injectively labeled scheduler nets that are built in an incremental hierarchical way from simple scheduler nets. [ABSTRACT FROM AUTHOR]

SUMMARY The determinization of a nondeterministic finite automaton (FA) [ABSTRACT FROM AUTHOR]

This paper deals with one-way and two-way weighted automata. When the semiring of weights is commutative, we prove that unambiguous one-way automata, unambiguous two-way automata and deterministic two-way automata realize the same (rational) power series. If the semiring of weights is not commutative, unambiguous one-way automata and deterministic two-way automata realize the same rational power series, but unambiguous two-way automata may realize non rational power series. [ABSTRACT FROM AUTHOR]

Determinization of fuzzy finite automata is understood here as a procedure of their conversion into equivalent crisp-deterministic fuzzy automata, which can be viewed as being deterministic with possible infinitely many states, but with fuzzy sets of terminal states. Particularly, significant determinization methods are those that provide a minimal crisp-deterministic fuzzy automaton equivalent to the original fuzzy finite automaton called canonization methods. One canonization method for fuzzy finite automata, the Brzozowski type determinization, has been developed recently by Jančić and Ćirić in [10]. Here we provide another canonization method for a fuzzy finite automaton $\cal A=(A,\sigma, \delta, \tau)$ over a complete residuated lattice $\cal L$ , based on the degrees of inclusion of the right fuzzy languages associated with states of $\cal A$ into the left derivatives of the fuzzy language recognized by $\cal A$. The proposed procedure terminates in a finite number of steps, whenever the membership values taken by $\delta$ , $\sigma$, and $\tau$ generate a finite subsemiring of the semiring reduct of $\cal L$ . This procedure is generally faster than the Brzozowski type determinization, and if the basic operations in the residuated lattice $\cal L$ can be performed in constant time, it has the same computational time as all other determinization procedures provided in [8], [11], and [12]. [ABSTRACT FROM PUBLISHER]

A weighted automaton is functional if any two accepting runs on the same finite word have the same value. In this paper, we investigate functional weighted automata for four different measures: the sum, the mean, the discounted sum of weights along edges and the ratio between rewards and costs. On the positive side, we show that functionality is decidable for the four measures. Further more, the existential and universal threshold problems, the language inclusion problem and the equivalence problem are all decidable when the weighted automata are functional. On the negative side, we also study the quantitative extension of there alizability problem and show that it is undecidable for sum, mean and ratio. We finally show how to decide whether the language associated with a given functional automaton can be defined with a deterministic one, for sum, mean and discounted sum. The results on functionality and determinizability are expressed for the more general class of functional group automata. This allows one to formulate within the same framework new results related to discounted sum automata and known results on sum and mean automata. Ratio automata do not fit within this general scheme and different techniques are required to decide functionality. [ABSTRACT FROM AUTHOR]

Timed automata are frequently used to model real-time systems. Their determinization is a key issue for several validation problems. However, not all timed automata can be determinized, and determinizability itself is undecidable. In this paper, we propose a game-based algorithm which, given a timed automaton, tries to produce a language-equivalent deterministic timed automaton, otherwise a deterministic over-approximation. Our method generalizes two recent contributions: the determinization procedure of Baier et al. (Proceedings of the 36th international colloquium on automata, languages and programming (ICALP'09), ) and the approximation algorithm of Krichen and Tripakis (Form Methods Syst Des 34(3):238-304, ). Moreover, we extend it to apply to timed automata with invariants and $$\varepsilon $$ -transitions, and also consider other useful approximations: under-approximation, and combination of under- and over-approximations. [ABSTRACT FROM AUTHOR]

This paper considers the problem of determinizing probabilistic data to enable such data to be stored in legacy systems that accept only deterministic input. Probabilistic data may be generated by automated data analysis/enrichment techniques such as entity resolution, information extraction, and speech processing. The legacy system may correspond to pre-existing web applications such as Flickr, Picasa, etc. The goal is to generate a deterministic representation of probabilistic data that optimizes the quality of the end-application built on deterministic data. We explore such a determinization problem in the context of two different data processing tasks—triggers and selection queries. We show that approaches such as thresholding or top-1 selection traditionally used for determinization lead to suboptimal performance for such applications. Instead, we develop a query-aware strategy and show its advantages over existing solutions through a comprehensive empirical evaluation over real and synthetic datasets. [ABSTRACT FROM PUBLISHER]

Abstract: The formulation of fuzzy automata allows us to select a great variety of triangular norms. Depending on the selected triangular norm, a fuzzy automaton can accept a fuzzy language (FA-language) with infinite range. These fuzzy automata are not equivalent to the so-called deterministic fuzzy automata (deterministic automata with a fuzzy subset of final states) which only accept fuzzy languages with finite range. In this paper, we study FA-languages with infinite range and a determinization procedure in order to obtain an equivalent fuzzy deterministic automaton for a given fuzzy automaton. A fuzzy deterministic automaton is a fuzzy automaton which satisfies the deterministic condition in its state transition function. The main contributions of our paper are: (1) a Pumping Lemma of FA-languages with infinite range; (2) the formulation of fuzzy deterministic automata and a Pumping Lemma of FDA-languages; (3) the necessary conditions for the determinization of fuzzy automata under continuous triangular norms which accept fuzzy languages of infinite range; and (4) a determinization algorithm for fuzzy automata, its correctness proof and performance. [Copyright &y& Elsevier]

Abstract: In this paper we adapt the well-known Brzozowski determinization method to fuzzy automata. This method gives better results than all previously known methods for determinization of fuzzy automata developed by Bělohlávek [4], Li and Pedrycz [20], Ignjatović et al. [15], and Jančić et al. [18]. Namely, as in the case of ordinary nondeterministic automata, Brzozowski type determinization of a fuzzy automaton results in a minimal crisp-deterministic fuzzy automaton equivalent to the starting fuzzy automaton, and we show that there are cases when all previous methods result in infinite automata, while Brzozowski type determinization results in a finite one. The paper deals with fuzzy automata over complete residuated lattices, but identical results can also be obtained in a more general context, for fuzzy automata over lattice-ordered monoids, and even for weighted automata over commutative semirings. [Copyright &y& Elsevier]

A discounted-sum automaton (NDA) is a nondeterministic finite automaton with edge weights, valuing a run by the discounted sum of visited edge weights. More precisely, the weight in the i-th position of the run is divided by γi, where the discount factor γ is a fixed rational number greater than 1. The value of a word is the minimal value of the automaton runs on it. Discounted summation is a common and useful measuring scheme, especially for infinite sequences, reflecting the assumption that earlier weights are more important than later weights. Unfortunately, determinization of NDAs, which is often essential in formal verification, is, in general, not possible. We provide positive news, showing that every NDA with an integral discount factor is determinizable. We complete the picture by proving that the integers characterize exactly the discount factors that guarantee determinizability: for every nonintegral rational discount factor ?, there is a nondeterminizable ?-NDA. We also prove that the class of NDAs with integral discount factors enjoys closure under the algebraic operations min, max, addition, and subtraction, which is not the case for general NDAs nor for deterministic NDAs For general NDAs, we look into approximate determinization, which is always possible as the influence of a word's suffix decays. We show that the naive approach, of unfolding the automaton computations up to a sufficient level, is doubly exponential in the discount factor. We provide an alternative construction for approximate determinization, which is singly exponential in the discount factor, in the precision, and in the number of states. We also prove matching lower bounds, showing that the exponential dependency on each of these three parameters cannot be avoided All our results hold equally for automata over finite words and for automata over infinite words. [ABSTRACT FROM AUTHOR]