The relationships among several types of fuzzy automata

We discuss the relationships among several types of fuzzy automata in which all fuzzy sets are defined by membership functions whose codomains are a lattice-ordered monoid L. These automata include nondeterministic L-valued finite automata with Λ-move, nondeterministic L-valued finite automata, deterministic L-valued finite automata, and L-valued finite-state automata. We consider all that come with fuzzy initial states and fuzzy final states or with crisp initial states or crisp final states. Some comparative results concerning the power of fuzzy automata used in the existing literature to recognize fuzzy languages are given systematically.     

Regular grammars with truth values in lattice-ordered monoid and their languages

In this study, we introduce the concept of lattice-valued regular grammars. Such grammars have become a necessary tool for the analysis of fuzzy finite automata. The relationship between lattice-valued finite automata (LA) and lattice-valued regular grammars (LRG) are discussed and we get the following results, for a given LRG, there exists an LA such that they accept the same languages, and vice versa. We also show the equivalence between deterministic lattice-valued regular grammars and deterministic lattice-valued finite automata.     

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).     

Fuzzy multiset finite automata and their languages

Inspired by the generalizations from grammars and finite automata to fuzzy grammars and fuzzy finite automata, respectively, we introduce the concepts of fuzzy multiset grammars and fuzzy multiset finite automata (FMFAs), as the generalizations of multiset grammars and multiset finite automata, respectively. The relationship between fuzzy multiset regular grammars and FMFAs is discussed. Furthermore, we define some operations on fuzzy multiset languages, and prove that the family of FMFA languages is closed under the operations.     

扰动值模糊有限自动机及其语言*

引入扰动值模糊有限自动机及其语言的概念,讨论扰动值模糊有限自动机的状态转移函数的扩张问题,证明3类确定型扰动值模糊有限自动机、非确定型扰动值模糊有限自动机相互等价性,研究扰动值模糊有限自动机的语言关于正则运算的封闭性.     

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.     

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.     

On transformations of formal power series

Formal power series are an extension of formal languages. Recognizable formal power series can be captured by the so-called weighted finite automata, generalizing finite state machines. In this paper, motivated by codings of formal languages, we introduce and investigate two types of transformations for formal power series. We characterize when these transformations preserve recognizability, generalizing the recent results of Zhang [16] to the formal power series setting. We show, for example, that the “square-root” operation, while preserving regularity for formal languages, preserves recognizability for formal power series when the underlying semiring is commutative or locally finite, but not in general.     

State complexity of some operations on binary regular languages

We investigate the state complexity of some operations on binary regular languages. In particular, we consider the concatenation of languages represented by deterministic finite automata, and the reversal and complementation of languages represented by nondeterministic finite automata. We prove that the upper bounds on the state complexity of these operations, which were known to be tight for larger alphabets, are tight also for binary alphabets.     

基于量子逻辑的下推自动机的代数刻画

首先,本文提出量子下推自动机（简记为L-VPDA）的概念,从代数角度出发详细研究了此类自动机的性质,同时建立此类自动机的代数刻画,即利用量子状态构造证明了任意L-VPDA与状态转移为经典函数且具有量子终状态的L-VPDA间的相互等价性;其次详细研究了量子上下文无关语言的代数刻画以及对于正则运算的封闭性。     

Language equations for timed alternating finite automata

Traditionally, finite state automata are untimed or asynchronous models of computation in which only the ordering of events, not the time at which events occur, would affect the result of a computation. For real-time systems, it is important to augment these models of computation with a notion of time. For this purpose timed automata have become a powerful canonical model for describing timed behaviors and an effective tool for modeling real-time computations. In this paper, we extend the notion of timed alternating finite automata (TAFA), a class of alternating finite automata (AFA) extended with a finite set of real-valued clocks, and we present an algebraic interpretation of TAFA which parallels that of timed regular expressions and language equations. We further extend the equational representation of AFA to describe timed alternating finite automata, and explore solutions for such equations over time languages.     

Finite fuzzy automata, regular fuzzy languages, and pattern recognition

Fuzzy set theory is summarized, and finite fuzzy automata and languages are described. Some results in fuzzy languages based on the “max(min)” rule are discussed. An application of fuzzy languages in syntactic pattern analysis is described and is illustrated by a simple example.     

More on quantum,stochastic, and pseudo stochastic languages with few states

Stochastic languages are the languages recognized by probabilistic finite automata (PFAs) with cutpoint over the field of real numbers. More general computational models over the same field such as generalized finite automata (GFAs) and quantum finite automata (QFAs) define the same class. In 1963, Rabin proved the set of stochastic languages to be uncountable presenting a single 2-state PFA over the binary alphabet recognizing uncountably many languages depending on the cutpoint. In this paper, we show the same result for unary stochastic languages. Namely, we exhibit a 2-state unary GFA, a 2-state unary QFA, and a family of 3-state unary PFAs recognizing uncountably many languages; all these numbers of states are optimal. After this, we completely characterize the class of languages recognized by 1-state GFAs, which is the only nontrivial class of languages recognized by 1-state automata. Finally, we consider the variations of PFAs, QFAs, and GFAs based on the notion of inclusive/exclusive cutpoint, and present some results on their expressive power.     

Composition and orbits of language operations: finiteness and upper bounds

We consider a set of eight natural operations on formal languages (Kleene closure, positive closure, complement, prefix, suffix, factor, subword, and reversal), and compositions of them. If x and y are compositions, we say x is equivalent to y if they have the same effect on all languages L. We prove that the number of equivalence classes of these eight operations is finite. This implies that the orbit of any language L under the elements of the monoid is finite and bounded, independent of L. This generalizes previous results about complement, Kleene closure, and positive closure. We also estimate the number of distinct languages generated by various subsets of these operations.     

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.     

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.     

Formal systems in Artificial Intelligence: an illustration using semigroup,automata and language theory

As the field of Artificial Intelligence (AI) matures, methods relying less on ad hoc procedures and more on well defined operations in the context of formal structures are emerging. Evidence for this can be found, for example, in the increasingly sophisticated approaches to inexact reasoning in knowledge-based systems and in the mathematical framework developed for semantic net representation. This tutorial and brief survey presents a facet of formal language theory which provides a formalism for naturally representing and operating on strings of symbols and which also admits obvious means of handling issues such as specialization and generalization, pervasive in AI. The broad subject area covered is part of semigroup theory which has a natural relationship to both finite state automata theory and regular languages. This paper aims to introduce some of the underlying theory relevant to representation issues in AI in this context.     

La representation ergodique d'un automate fini

We study a special class of finite automata called reversible and defined by the following property: there exists a state such that, starting from it, both the automation and its (deterministic) reversal are strongly connected.The main tool to handle these automata is the ergodic representation which is mainly the Schützenberger matrix representation of the semigroup of the automaton over its minimal ideal. This representation allows the construction of a class of reversible automata: the so called homogeneous ones. This class is precisely the one obtained by considering a class of finite languages that are both prefix and suffix. We obtain here, by means of their automaton, a construction of these languages.     

Abstract Regular Tree Model Checking

Regular (tree) model checking (RMC) is a promising generic method for formal verification of infinite-state systems. It encodes configurations of systems as words or trees over a suitable alphabet, possibly infinite sets of configurations as finite word or tree automata, and operations of the systems being examined as finite word or tree transducers. The reachability set is then computed by a repeated application of the transducers on the automata representing the currently known set of reachable configurations. In order to facilitate termination of RMC, various acceleration schemas have been proposed. One of them is a combination of RMC with the abstract-check-refine paradigm yielding the so-called abstract regular model checking (ARMC). ARMC has originally been proposed for word automata and transducers only and thus for dealing with systems with linear (or easily linearisable) structure. In this paper, we propose a generalisation of ARMC to the case of dealing with trees which arise naturally in a lot of modelling and verification contexts. In particular, we first propose abstractions of tree automata based on collapsing their states having an equal language of trees up to some bounded height. Then, we propose an abstraction based on collapsing states having a non-empty intersection (and thus “satisfying”) the same bottom-up tree “predicate” languages. Finally, we show on several examples that the methods we propose give us very encouraging verification results.     

On regular tree languages and deterministic pushdown automata

The theory of formal string languages and of formal tree languages are both important parts of the theory of formal languages. Regular tree languages are recognized by finite tree automata. Trees in their postfix notation can be seen as strings. This paper presents a simple transformation from any given (bottom-up) finite tree automaton recognizing a regular tree language to a deterministic pushdown automaton accepting the same tree language in postfix notation. The resulting deterministic pushdown automaton can be implemented easily by an existing parser generator because it is constructed for an LR(0) grammar, and its size directly corresponds to the size of the deterministic finite tree automaton. The class of regular tree languages in postfix notation is a proper subclass of deterministic context-free string languages. Moreover, the class of tree languages which are in their postfix notation deterministic context-free string languages is a proper superclass of the class of regular tree languages.