An improved algorithm for determinization of weighted and fuzzy automata

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

Weighted finite automata over strong bimonoids

We investigate weighted finite automata over strings and strong bimonoids. Such algebraic structures satisfy the same laws as semirings except that no distributivity laws need to hold. We define two different behaviors and prove precise characterizations for them if the underlying strong bimonoid satisfies local finiteness conditions. Moreover, we show that in this case the given weighted automata can be determinized.     

Weighted tree automata and weighted logics

We define a weighted monadic second order logic for trees where the weights are taken from a commutative semiring. We prove that a restricted version of this logic characterizes the class of formal tree series which are accepted by weighted bottom-up finite state tree automata. The restriction on the logic can be dropped if additionally the semiring is locally finite. This generalizes corresponding classical results of Thatcher, Wright, and Doner for tree languages and it extends recent results of Droste and Gastin [Weighted automata and weighted logics, in: Automata, Languages and Programming—32nd International Colloquium, ICALP 2005, Lisbon, Portugal, 2005, Proceedings, Lecture Notes in Computer Science, Vol. 3580, Springer, Berlin, 2005, pp. 513–525, full version in Theoretical Computer Science, to appear.] from formal power series on words to formal tree series.     

Weighted automata and weighted logics with discounting

We introduce a weighted logic with discounting and we establish the Büchi–Elgot theorem for weighted automata over finite words and arbitrary commutative semirings. Then we investigate Büchi and Muller automata with discounting over the max-plus and the min-plus semiring. We show their expressive equivalence with weighted MSO-sentences with discounting. In this case our logic has a purely syntactic definition. For the finite case, we obtain a purely syntactically defined weighted logic if the underlying semiring is additively locally finite.     

Weighted automata with discounting

We investigate weighted automata with discounting and their behaviors over semirings and finitely generated graded monoids. We characterize the discounted behaviors of weighted automata precisely as rational formal power series with a discounted form of the Cauchy product. This extends a classical result of Kleene-Schützenberger. Here we show that the very special case of Schützenberger's result for free monoids over singleton alphabets suffices to deduce our generalization.     

加权有穷自动机的代数性质

在加权有穷自动机理论基础上,利用强同态的概念,证明两个加权有穷自动机在计算能力上是等价的,并在加权有穷自动机的状态集上建立一种等价关系,得到加权有穷自动机的商自动机,证明加权有穷自动机与其商自动机在计算能力上也是等价的。并通过引入加权有穷自动机的可交换性、分离性、(强)连通性及层的概念,讨论在(强)同态的条件下,两个加权有限状态机之间的可交换性、分离性、(强)连通性及层的关系。关键词：     

On the optimal reachability problem of weighted timed automata

We study the cost-optimal reachability problem for weighted timed automata such that positive and negative costs are allowed on edges and locations. By optimality, we mean an infimum cost as well as a supremum cost. We show that this problem is PSpace-Complete. Our proof uses techniques of linear programming, and thus exploits an important property of optimal runs: their time-transitions use a time τ which is arbitrarily close to an integer. We then propose an extension of the region graph, the weighted discrete graph, whose structure gives light on the way to solve the cost-optimal reachability problem. We also give an application of the cost-optimal reachability problem in the context of timed games. Research supported by the FRFC project “Centre Fédéré en Vérification” funded by the Belgian National Science Foundation (FNRS) under grant nr 2.4530.02.     

Inequality of finite behaviors of rational weight finite automata is in R

Inequivalence of finite automata accepting finite languages over a non-unary alphabet is NP-complete. However, the inequality of their behaviors does not appear to have been carefully investigated. In the simplest case, the behavior of a finite automaton is the formal series f such that the coefficient f(w) of a word w is the number of distinct accepting computations on w. This notion will be generalized in the paper to finite automata with rational weights. The main result is that inequality of rational weight finite automata with finite behaviors is in R, random polynomial time.     

RaRb Transformation of Compound Finite Automata over Commutative Rings

Some results on RaRb transformation of compound finite automata over finite field are generalized to the case of commutative rings.Properties of RaRb transformation are discussed and applied to the inversion problem for compound finite automata.     

Determinization of fuzzy automata with membership values in complete residuated lattices

In this paper we introduce a new method for determinization of fuzzy finite automata with membership values in complete residuated lattices. In comparison with the previous methods, developed by Bělohlávek [R. Bělohlávek, Determinism and fuzzy automata, Information Sciences 143 (2002), 205-209] and Li and Pedrycz [Y.M. Li, W. Pedrycz, Fuzzy finite automata and fuzzy regular expressions with membership values in lattice ordered monoids, Fuzzy Sets and Systems 156 (2005), 68-92], our method always gives a smaller automaton, and in some cases, when the previous methods result in infinite automata, our method can result in a finite one. We also show that determinization of fuzzy automata is closely related to fuzzy right congruences on a free monoid and fuzzy automata associated with them, and in particular, to the concept of the Nerode’s fuzzy right congruence of a fuzzy automaton, which we introduce and study here.     

Recognizability of the support of recognizable series over the semiring of the integers is undecidable

A recognizable series over the semiring of the integers is a function that maps each word over an alphabet to an integer. The support of such a series consists of all those words which are not mapped to zero. It is long known that there are recognizable series whose support is not a recognizable, but a context-free language. However, the problem of deciding whether the support of a given recognizable series is recognizable was never considered. Here we show that this problem is undecidable. The proof relies on an encoding of an instance of Post?s correspondence problem.     

Folk theorems on the determinization and minimization of timed automata

Timed automata are known not to be complementable or determinizable. Natural questions are, then, could we check whether a given TA enjoys these properties? These problems are not algorithmically solvable. Minimizing the “resources” of a TA (number of clocks or size of constants) are also unsolvable problems. In this paper we provide simple undecidability proofs using a “constructive” version of the problems where we require not just a yes/no answer, but also a “witness”. Proofs are then simple reductions from the universality problem. Recent work of Finkel shows that the corresponding decision problems are also undecidable [O. Finkel, On decision problems for timed automata, Bulletin of the European Association for Theoretical Computer Science 87 (2005) 185-190].     

Determinization and minimization of finite acyclic automata by incremental techniques

The determinization of a nondeterministic finite automaton (FA) is the process of generating a deterministic FA (DFA) equivalent to (sharing the same regular language of) . The minimization of is the process of generating the minimal DFA equivalent to . Classical algorithms for determinization and minimization are available in the literature for several decades. However, they operate monolithically, assuming that the FA to be either determinized or minimized is given once and for all. By contrast, we consider determinization and minimization in a dynamic context, where augments over time: after each augmentation, determinization and minimization of into is required. Using classical monolithic algorithms to solve this problem is bound to poor performance. An algorithm for incremental determinization and minimization of acyclic finite automata, called IDMA, is proposed. Despite being conceived within the narrow domain of model‐based diagnosis and monitoring of active systems, the algorithm is general‐purpose in nature. Experimental evidence indicates that IDMA is far more efficient than classical algorithms in solving incremental determinization and minimization problems. Copyright © 2015 John Wiley & Sons, Ltd.     

On characteristic sets and degrees of finite automata

The characteristic sets and degrees of finite automata are notions used by Biermann for his finite automaton learner. Some fundamental properties and relations of these notions are considered. A necessary and sufficient condition under which his learner converges to an expected automaton is given.     

Intuitionistic fuzzy recognizers and intuitionistic fuzzy finite automata

Intuitionistic fuzzy recognizers and intuitionistic fuzzy finite automata are discussed. The notions of intuitionistic fuzzy recognizer, complete accessible intuitionistic fuzzy recognizer, intuitionistic fuzzy finite automata, deterministic intuitionistic fuzzy finite automata, and intuitionistic fuzzy language are introduced. It is shown that the languages recognized by intuitionistic fuzzy recognizer are regular, and the intuitionistic fuzzy languages recognized by the intuitionistic fuzzy finite automaton and the intuitionistic fuzzy languages recognized by deterministic intuitionistic fuzzy finite automaton are equivalent. This work is supported by National Science Foundation of China (Grant No.10571112), “TRAPOYT” of China and National 973 Foundation Research Program(Grant No.2002CB312200).     

The concept of duality for automata over a changing alphabet and generation of a free group by such automata

In the paper, we deal with the notion of an automaton over a changing alphabet, which generalizes the concept of a Mealy-type automaton. We modify the methods based on the idea of a dual automaton and its action used by B. Steinberg et al. (2011) and M. Vorobets and Ya. Vorobets (2007, 2010) [16], [17] and [18] and adapt them to automata over a changing alphabet. We show that this modification provides some naturally defined automaton representations of a free nonabelian group by a 2-state automaton over a changing alphabet.     

A quadratic-time DBM-based successor algorithm for checking timed automata

Most of the timed automaton model checking algorithms explore state spaces by enumeration of time zones. The data structure called Difference Bound Matrix (DBM) is widely adopted to represent time zones because of its efficiency and simplicity. In this paper, we first present a quadratic-time algorithm to compute the canonical form of the conjunction of a canonical DBM and a time guard or a location invariant. Based on this algorithm, we present a quadratic-time DBM-based successor algorithm for timed automaton model checking.     

Unary finite automata vs. arithmetic progressions

We point out a subtle error in the proof of Chrobak's theorem that every unary NFA can be represented as a union of arithmetic progressions that is at most quadratically large. We propose a correction for this and show how Martinez's polynomial time algorithm, which realizes Chrobak's theorem, can be made correct accordingly. We also show that Martinez's algorithm cannot be improved to have logarithmic space, unless L = NL.