Finite automata theory with membership values in lattices

被引：49

作者：

Li, Yongming ^{[1
]}

机构：

[1] Shaanxi Normal Univ, Coll Comp Sci, Xian 710062, Peoples R China

来源：

INFORMATION SCIENCES | 2011年 / 181卷 / 05期

基金：

美国国家科学基金会;

关键词：

Finite automata; Language; Lattice; Subset construction; QUANTUM LOGIC; FUZZY;

D O I：

10.1016/j.ins.2010.11.006

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

In this paper, we study finite automata with membership values in a lattice, which are called lattice-valued finite automata. The extended subset construction of lattice-valued finite automata is introduced, then the equivalences between lattice-valued finite automata, lattice-valued deterministic finite automata and lattice-valued finite automata with E-moves are proved. A simple characterization of lattice-valued languages recognized by lattice-valued finite automata is given, then it is proved that the Kleene theorem holds in the frame of lattice-setting. A minimization algorithm of lattice-valued deterministic finite automata is presented. In particular, the role of the distributive law for the truth valued domain of finite automata is analyzed: the distributive law is not necessary to many constructions of lattice-valued finite automata, but it indeed provides some convenience in simply processing lattice-valued finite automata. (C) 2010 Elsevier Inc. All rights reserved.

引用

页码：1003 / 1017

页数：15

共 34 条

[1] Determinism and fuzzy automata [J].

Belohlávek, R .

INFORMATION SCIENCES, 2002, 143 (1-4) :205-209

[2]

Birkhoff G., 1973, Lattice Theory

[3]

Chechik M., 2004, ACM T SOFTW ENG METH, V12, P1

[4] Weighted automata and weighted logics [J].

Droste, Manfred ;

Gastin, Paul .

THEORETICAL COMPUTER SCIENCE, 2007, 380 (1-2) :69-86

[5]

EILENBERG S, 1974, AUTOMATA LANGUAGES M, VB

[6]

Eilenberg S., 1974, Pure and Applied Mathematics, V59

[7] Parameter identification of recurrent fuzzy systems with fuzzy finite-state automata representation [J].

Gama, Carlos A. ;

Evsukoff, Alexandre G. ;

Weber, Philippe ;

Ebecken, Nelson F. F. .

IEEE TRANSACTIONS ON FUZZY SYSTEMS, 2008, 16 (01) :213-224

[8]

Gupta M.M., 1977, Fuzzy automata and decision process

[9]

Hopcroft J., 1979, Introduction to automata theory, languages, and computation

[10] Determinization of fuzzy automata with membership values in complete residuated lattices [J].

Ignjatovic, Jelena ;

Ciric, Miroslav ;

Bogdanovic, Stojan .

INFORMATION SCIENCES, 2008, 178 (01) :164-180

← 1 2 3 4 →