共查询到20条相似文献,搜索用时 15 毫秒
1.
Jelena Ignjatovi? 《Information Sciences》2010,180(7):1104-139
In this paper we study formal power series over a quantale with coefficients in the algebra of all languages over a given alphabet, and representation of fuzzy languages by these formal power series. This representation generalizes the well-known representation of fuzzy languages by their cut and kernel languages. We show that regular operations on fuzzy languages can be represented by regular operations on power series which are defined by means of operations on ordinary languages. We use power series in study of fuzzy languages which are recognized by fuzzy finite automata and deterministic finite automata, and we study closure properties of the set of polynomials and the set of polynomials with regular coefficients under regular operations on power series. 相似文献
2.
针对模糊识别器与有穷自动机的关系,证明了当输入字母表相同时,任给一个模糊识别器,必然存在一个有穷自动机,使得模糊识别器的行为与有穷自动机所接受的语言相同;反之,任给一个有穷自动机,必然存在一个模糊识别器,使得有穷自动机所接受的语言与模糊识别器的行为相同,从而得出它们之间的等价性。 相似文献
3.
I. I. Macarie 《Theory of Computing Systems》1997,30(1):91-109
We present properties of multihead two-way probabilistic finite automata that parallel those of their deterministic and nondeterministic
counterparts. We define multihead probabilistic finite automata withlogspace constructible transition probabilities, and we describe a technique to simulate these automata by standard logspace probabilistic Turing
machines. Next, we represent logspace probabilistic complexity classes as proper hierarchies based on corresponding multihead
two-way probabilistic finite automata, and we show their (deterministic logspace) reducibility to the second levels of these
hierarchies.
We obtain a simple formula for the maximum inherent bandwidth of the configuration transition matrices associated with thek-head probabilistic finite automata processing a length-n input string. (The inherent bandwidth of the configuration transition matrices associated with an automaton processing a
length-n input string is the smallest bandwidth we can get by changing the enumeration order of the automaton’s configurations.) Partially
based on this relation, we find an apparently easier logspace complete problem forPL (the class of languages recognized by logspace unbounded-error probabilistic Turing machines), and we discuss possibilities
for a space-efficient deterministic simulation of probabilistic automata.
This research was supported by the National Science Foundation under Grant No. CDA 8822724 while the author was at the University
of Rochester. An extended abstract of this paper appeared in Proceedings, Second Latin American Symposium, LATIN ’95: Theoretical
Informatics, Valparaiso, Chile, April 1995. 相似文献
4.
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. 相似文献
5.
Summary We discuss the technique for testing the equivalence of two deterministic automata by constructing a language that matches the computations of two equivalent automata on the same input word. Specifically, we propose to use HDTOL languages that are powerful enough to match computations of many equivalent deterministic multitape automata, and at the same time, have nice decidable properties. Using this new technique of HDTOL matching, we show that the inclusion problem between an arbitrary deterministic multitape automaton and a simple one is decidable in both directions. Further, we show that the equivalence for a restricted class of transducers based on deterministic multitape automata is decidable.Reported research was supported by the National Sciences Foundation under Grant No. CCR-8702752 and by the Natural Sciences and Engineering Research Council of Canada under Grant No. A-7403 相似文献
6.
Young Bae Jun 《Information Sciences》2007,177(22):4977-4986
Quotient structures of intuitionistic fuzzy finite state machines are discussed. We give congruence relations which can be naturally introduced in such a way that each associates a semigroup with an intuitionistic fuzzy finite state machine. We also introduce the notion of intuitionistic admissible relation, and give its characterization. An isomorphism between an intuitionistic fuzzy finite state machine and the quotient structure of another intuitionistic fuzzy finite state machine is established. 相似文献
7.
The relationships among several types of fuzzy automata 总被引:3,自引:0,他引:3
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. 相似文献
8.
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. 相似文献
9.
给出了[Σ-]代数、[Σ-]树、模糊[Σ-]树自动机、模糊[Σ-]树自动机行为的定义。引入了模糊树自动机语言的并、交、连接和Kleene闭包运算,证明了在这些运算下模糊树自动机语言的封闭性。 相似文献
10.
11.
主要研究确定型模糊多重集有限自动机的状态极小化问题。给出了模糊多重集有限自动机的同余和同态概念,并利用同余和同态关系研究了确定型模糊多重集有限自动机的极小化问题。进一步从确定型模糊多重集有限自动机自身出发,构造出极小模糊多重集有限自动机,并给出了极小化的算法。 相似文献
12.
Structure of Weakly Invertible Semi-Input-Memory Finite Automata with Delay 1 总被引:4,自引:2,他引:4 下载免费PDF全文
Semi-input-memory finite automata,a kind of finite automata introduced by the first author of this paper for studying error propagation ,are a generalization of inputmemory finite automata ,by appending an autonomous finite automation component .In this paper,we give a characterization of the structure of weakly invertible semi-input-memory finite automata with delay 1,in which the state graph of each autonomous finite automation is cycle,From a result on mutual invertibility of finite automata obtained by th authors recently,it leads to a characerization of the structure of feedfoward inverse finite automata with delay 1. 相似文献
13.
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. 相似文献
14.
This paper presents a general framework for the study of relation-based (I,T)-intuitionistic fuzzy rough sets by using constructive and axiomatic approaches. In the constructive approach, by employing an intuitionistic fuzzy implicator I and an intuitionistic fuzzy triangle norm T, lower and upper approximations of intuitionistic fuzzy sets with respect to an intuitionistic fuzzy approximation space are first defined. Properties of (I,T)-intuitionistic fuzzy rough approximation operators are examined. The connections between special types of intuitionistic fuzzy relations and properties of intuitionistic fuzzy approximation operators are established. In the axiomatic approach, an operator-oriented characterization of (I,T)-intuitionistic fuzzy rough sets is proposed. Different axiom sets characterizing the essential properties of intuitionistic fuzzy approximation operators associated with various intuitionistic fuzzy relations are explored. 相似文献
15.
This paper designs and analyzes switching fuzzy reduced-order observer and proves that the corresponding separation principle
does hold. A numerical simulation and comparison with smooth fuzzy full-order observer are given to assess switching fuzzy
reduced-order observer and the validity of the separation principles.
Supported by the National Laboratory of Space Intelligent Control and Open Foundation (Grant No. SIC07010202), and the National
Natural Science Foundation of China (Grant Nos. 60604010, 90716021, 60736023) 相似文献
16.
Bae Jun Young 《Information Sciences》2009,179(24):4284-1770
The idea of (faithful) intuitionistic fuzzy transformation semigroup, intuitionistic admissible relation, and intuitionistic (strong) homomorphism are introduced and their basic properties are examined. 相似文献
17.
In rough set theory, the lower and upper approximation operators defined by binary relations satisfy many interesting properties. Various generalizations of Pawlak’s rough approximations have been made in the literature over the years. This paper proposes a general framework for the study of relation-based intuitionistic fuzzy rough approximation operators within which both constructive and axiomatic approaches are used. In the constructive approach, a pair of lower and upper intuitionistic fuzzy rough approximation operators induced from an arbitrary intuitionistic fuzzy relation are defined. Basic properties of the intuitionistic fuzzy rough approximation operators are then examined. By introducing cut sets of intuitionistic fuzzy sets, classical representations of intuitionistic fuzzy rough approximation operators are presented. The connections between special intuitionistic fuzzy relations and intuitionistic fuzzy rough approximation operators are further established. Finally, an operator-oriented characterization of intuitionistic fuzzy rough sets is proposed, that is, intuitionistic fuzzy rough approximation operators are defined by axioms. Different axiom sets of lower and upper intuitionistic fuzzy set-theoretic operators guarantee the existence of different types of intuitionistic fuzzy relations which produce the same operators. 相似文献
18.
Summary A direct proof is given that shows that (one-way) 3-head deterministic finite automata are computationally more powerful than 2-head finite automata.This research was supported by the National Science Foundation Grant GJ-35614. 相似文献
19.
S.E. Abbas 《Information Sciences》2006,176(6):745-757
We introduce the intuitionistic fuzzy semiregularization space induced by an intuitionistic fuzzy topological space. We also investigate some properties of intuitionistic fuzzy semiregularization spaces. 相似文献
20.
Changjian Liang Yongming Li 《Soft Computing - A Fusion of Foundations, Methodologies and Applications》2008,12(11):1049-1057
In this paper, the algebraic operations on the cuts of lattice-valued regular languages are studied. Some sufficient conditions
are given to guarantee the family of the cuts of lattice-valued regular languages to be closed under such algebraic operations
as union, intersection, complement, quotient, homomorphism, inverse homomorphism, concatennation, reversal, etc.
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). 相似文献