信息系统更新的自动机

曹发生

中山大学逻辑与认知研究所

caofasheng@163.com

信息系统更新的自动机

曹发生

中山大学逻辑与认知研究所

caofasheng@163.com

通过引入信息等价和信息范式这两个主要概念，给出了信息系统更新的自动机。用自动机理论给出信息系统更新的模型的刻画，证明了星动作算子在信息系统的动态更新的逻辑系统的引入的不必要性，并且得到了自动机的语言和信息更新的联系。最后利用自动机理论研究了信息系统及其更新逻辑系统的模型检测的时间复杂性。

信息系统；动态；自动机；模型检测

粗糙集理论中的知识表达方式（[12,13]）一般采用信息表或称为信息系统的形式，对于粗糙集理论的逻辑推理系统来说，粗糙集公理系统是至关重要的。自从Lin在文[9]首次用公理化方法研究粗糙集之后，出现了许多关于粗糙集理论公理化方法方面的研究。（[3,8,10,11,15,17]）Khan利用公理化方法在文[6,7]中给出完全和不完全信息系统的逻辑系统。他们用框架语义建立逻辑系统的模型，这种模型是建立在粗糙集理论基础之上的，并且给出逻辑系统的可靠性和完全性。

如何表达信息系统的更新过程，以至形成逻辑系统，有助于计算机对信息系统做形式推演。本文致力于表达清楚信息系统的更新过程，具体表现为：刻画出从初始信息系统到终结信息系统的更新过程中的形式语言。形式自动机（[16]）是能够识别形式语言的数学系统，它可以用来检验输入的符号串是不是语言中符合语法的句子。如果是符合语法的句子，自动机就接收它；如果不是，就不接收它。自动机的状态转换图就是进程演变的数学结构，因此我们用自动机来刻画信息系统的更新。我们将不同的信息系统作为自动机的不同状态，用原子信息作为自动机的字母表，建立信息系统更新的自动机，得到该自动机语言和信息更新的联系：该自动机的任何可接受的语言都是从初始信息系统到终结信息系统的更新过程。

1 预备知识

定义1([12])一个信息系统（IS）S是一个四元组S=(W,A,V,f)，其中

(1)W是对象的非空有限集合，称为论域；

(2)A是属性的非空有限集合；

(4)f:W×A-→V是一个映射，即对每一个对象的任意属性都赋予了一个属性值。

不含未知属性值符号的信息系统，称为完全信息系统。

注记1我们在本文中限定A是属性的非空有限集合。有这样的限制，我们就可以研究信息系统模型检测的复杂性；再者，计算机处理的信息系统知识库都是有限属性集合，所以这样的限制是可行的。

下面叙述本文要用到的粗糙集理论中的一些定义。

定义2([12,13])S=(W,A,V,f)是一个完全信息系统，对于任意的B⊆A，定义W上的二元关系IND(B)为：(x,y)∈IND(B)当且仅当，对任意的a∈B都有f(x,a)=f(y,a)；S=(W,A,V∪{ϵ},f)是一个信息系统，对于任意的B⊆A定义W上的二元关系SIM(B)为：(x,y)∈SIM(B)当且仅当，对任意的a∈B都有f(x,a)=f(y,a)或者f(x,a)=ϵ或者f(y,a)=ϵ。

注记2下文的二元关系R的元素(x,y)∈R，我们有时候也用xRy来表示。下文中用xR1yR2z来表示xR1y并且yR2z。定义3([12,13])任给二元关系R⊆W×W，对于任意的x∈W记xR={y| xRy}，对于任意的X⊆W定义W的两个子集合及X={x∈W|xR∩X∅}，分别称它们为X的R下近似集合和上近似集合。

“完全信息系统”与“信息系统”的本质区别在于是否存在未知属性值。在完全信息系统的粗糙集理论中的关系是等价关系，而在信息系统的粗糙集理论中的关系是相似关系。

接下来按Stanley Burris（[2]）给出关于信息系统S一类泛代数AS的定义。

定义4设S=(W,A,V∪{ϵ},f)，代数的语言（型）,其中⊓是二元函数符号，～，是一元函数符号，(a,v)是零元函数符号。

关于S的一类泛代数AS是一个结构AS=〈2W,F〉。

2 信息系统的逻辑系统（LIS）

LIS的语言L采用Pawlak在文[14]及Khan在文[7]中给出的方式定义。

2.1 LIS的语法

定义5LIS语言L的字母表包括以下部分：

(1)一个有穷非空集合A，其元素称为属性常元，用符号a或加数字下标表示；

(2)集合A的子集合符号，用B或加数字下标表示；

(3)特殊属性值（空值）符号ϵ，及对每一个a∈A有一个有穷非空集合Va，其元素是属性值常元，用符号v或va或加数字下标表示；

(4)逻辑联结符号¬，∧，[IND(B)]，[SIM(B)]；

(5)两个常元符号⊤，⊥；

(6)变元符号，用α，β，γ或加数字下标表示；

(7)命题变元符号集合PV，其元素用符号p或加数字下标表示；

(8)技术性符号：(，)，,，[，]。

定义6LIS的合式公式的形成规则：

(1)常元符号⊤，⊥，命题变元符号，变元符号是合式公式；

(2)(a,v)是合式公式，也简记为av，称为描述子；

(3)若α，β是合式公式，则¬α，α∧β，[IND(B)]α，[SIM(B)]α是合式公式；

(4)仅由以上三条形成合式公式。全体描述子的集合记为D，全体合式公式的集合记为P。

2.2 LIS的语义

LIS语言L的语义是基于模态逻辑（[1]）模型的框架语义。

定义7([7])一个模型是一个组M=(W,{IND(B)}B⊆A,{SIM(B)}B⊆A,m,P)，其中

(1)W是一个非空集合；

(2)IND(B)，SIM(B)是W上的二元关系；

(3)m:D-→2W；

(4)P:PV-→2W。

下面我们叙述合式公式在模型中的可满足性的定义：

定义8([7])任给语言L中的合式公式α如下归纳定义模型M在w∈W上

可满足，记为M,w|=α:

(1)M,w|=⊤；

(2)非M,w|=⊥；

(3)M,w|=(a,v)当且仅当，w∈m(av)；

(4)M,w|=p当且仅当，w∈P(p)；

(5)M,w|=¬α当且仅当，非M,w|=α；

(6)M,w|=α∧β当且仅当，M,w|=α并且M,w|=β；

(7)对于任意的R∈{IND(B)}B⊆A∪{SIM(B)}B⊆A，M,w|=[R]α当且仅当，对任意的wRw′的w′都有M,w′|=α。

定义9([7])给定S=(W,A,V∪{ϵ},f)，它的标准模型为

MS=(W,{IND(B)}B⊆A,{SIM(B)}B⊆A,mS,P)，其中

(1)mS(a,v):={x∈W|f(x,a)=v}；

(2)P:PV-→2W。

在不混淆时候用S表示它的标准模型MS。在S的标准模型MS中，[R]α在模型解释下集合和粗糙集有着紧密的联系，具体如下：

定理1m([R]α)=m(α)。

证明.设x∈m([R]α)，由定义8(7)得，对任意的xRy的y都有y∈m(α)。这也即是，对任意的y∈xR都有y∈m(α)。由定义3中下近似集合定义得，x∈)。这些都是当且仅当的，于是反过来也成立。故m([R□

Khan在文[6,7]给出了LIS的公理和推理规则，并且给出了可靠性和完全性定理。本文的主要目标是给出信息系统的更新的自动机表示，下面就要先给出信息系统更新的逻辑系统。

3 信息系统更新的逻辑系统(DLIS)

DLIS语言LD采用Khan在文[7]中给出的方式定义。

3.1 DLIS的语法

定义10DLIS语言LD的字母表包括以下部分：

(1)L的字母表；

(2)两个信息更新算子符号：∨（选择）和;（合成）。

信息上的运算已经有两个二元运算，在一般的动态逻辑中都有二元算符(合成和选择)及一元算符(星)。我们本来打算按照动态逻辑（[4]）的模式在这个信息系统更新的逻辑系统中加上一个新的更新算子符号星算子∗，因而就引入更新的自动机，但是利用自动机理论发现这个星算子的引入是平凡的。文章的第4部分将给出证明。

定义11信息的形成规则：

(1)原子信息(α,a,v)是信息，这里α∈P，a∈A，v∈Va；

(2)若σ，σ′是信息，则σ;σ′，σ∨σ′是信息；

(3)仅由以上两条形成信息。

全体原子信息的集合记为AInf，全体信息的集合记为Inf。

我们设定合成算子的结合的紧密性比选择算子的结合的紧密性高，即是说σ1;σ2∨σ3表示(σ1;σ2)∨σ3。

定义12DLIS的合式公式的形成规则：

(1)常元符号⊤，⊥，命题变元符号是合式公式；

(2)(a,v)是合式公式，也简记为av，称为描述子；

(3)若α，β是合式公式，则¬α，α∧β，[IND(B)]α，[SIM(B)]α是合式公式；

(4)若α是合式公式，σ是信息，则[σ]α是合式公式；

(5)仅由以上四条形成合式公式。

3.2 DLIS的语义

定义13([7])设M=(W,{IND(B)}B⊆A,{SIM(B)}B⊆A,m,P)是一个模型，定义由原子信息σ0=(α,a,v)更新模型M所得模型，或称为M的σ0更新模型，记为

其中Pσ0:=P；另外，mσ0如下给出：

R(B)σ0,R∈{IND,SIM},B⊆A如下给出：

这个定义可以推广到原子信息的合成上的更新信息系统M(σ1;σ2;...;σk):= ((((Mσ1)σ2)...)σk)，这对定理3的证明起着非常重要的作用。

下面定义关于信息σ的模型间的二元关系Rσ，我们用花体R来区别W上的二元关系R，但都是集合论中的二元关系。

定义14([7])MRσM′归纳于σ的结构如下：

(1)MR(α,a,v)M′当且仅当，M′=M(α,a,v)；

(2)MRσ;σ′M′当且仅当，存在模型M′使得MRσM′且M′Rσ′M′；

(3)MRσ∨σ′M′当且仅当，MRσM′或者MRσ′M′。

定义15若MRσM′则称模型M′是模型M由信息σ更新而得到的模型，也称σ是从M′到M的信息更新。

引理1对于原子信息的合成信息σ和M来说，仅存在一个模型M′使得MRσM′。

这个引理根据Rσ的定义容易得证，故略去证明过程，它将在下节的定理5的证明中被用到。接下来给出由更新算子所得合式公式的可满足性的定义：

定义16([7])M,w|=[σ]α当且仅当，对任意的MRσM′的M′都有M′,w|= α。

为了引入信息系统更新的自动机，我们需要两个重要的概念，即：信息的等价和信息的范式。下面我们就来给出它们的定义。

定义17(信息的等价)如果MRσM′当且仅当MRσ′M′，则称信息σ与σ′等价，记为σ≡σ′。

注记3信息的等价是个等价关系。

定义18(信息的范式)有穷多个原子信息的合成称为合成信息；有穷多个原子信息的选择称为选择信息。有穷多个合成信息的选择称为选择范式信息，这里的合成信息也称为析取支；有穷多个选择信息的合成称为合成范式信息，这里的选择信息也称为合取支。

注记4原子信息既是一个选择范式，也是合成范式。

有了这两个概念，我们得到下面的一个基础型的定理：

定理2(信息的范式表示)(1)每个信息σ都有一个选择范式与它等价。

(2)每个信息σ都有一个合成范式与它等价。

为了证明这个定理，先给出关于等价的分配性的引理：

引理2(1)σ1;(σ2∨σ3)≡σ1;σ2∨σ1;σ3。

(2)σ1;σ2∨σ3≡(σ1∨σ3);(σ2∨σ3)。

证明.(1)设MRσ1;(σ2∨σ3)M′，由R定义知存在M′使得MRσ1M′R(σ2∨σ3)M′即是MRσ1M′并且（M′Rσ2M′或者M′Rσ3M′），当且仅当，（MRσ1M′并且M′Rσ2M′）或者（MRσ1M′并且M′Rσ3M′），于是MRσ1;σ2∨σ1;σ3M′。

故σ1;(σ2∨σ3)≡σ1;σ2∨σ1;σ3。

逻辑对偶地可类似证明(2)成立。 □

注记5这个引理还能推广到更一般的有穷个的分配律上，如σ1;(σ2∨σ3∨···∨σk)≡σ1;σ2∨σ1;σ3∨···∨σ1;σk。;和∨在等价意义下都具有结合律。

定理2的证明.归纳于σ的结构，同时证明(1)和(2)。

基础部分：当σ是原子信息，则它本身已是一个选择范式，也是合成范式。归纳部分：当σ是σ1;σ2形式，(1)由归纳假设有（这里σ;表示σ的合成范式），已是合成范式。(2)由归纳假设有（这里σ∨表示σ的选择范式），由引理2(1)可知它能等价为一个选择范式。

当σ是σ1∨σ2形式，(1)由归纳假设有（这里 σ;表示σ的合成范式），由引理2(2)可知它能等价为一个合成范式。(2)由归纳假设有（这里σ∨表示σ的选择范式），已是一个选择范式。

综上所述，定理2得证。 □

有了这个定理，我们把信息等价的选择范式的析取支简称为信息的的析取支。

4 信息系统更新的自动机

由信息的范式定理，任给的信息可以转化成范式形式，于是我们将信息系统更新的自动机的输入字母表定义为全体原子信息。本节中我们讨论IS上的更新，即是讨论从一个IS通过怎么的信息更新过程得到新的IS。从模型的角度上说，我们只局限于讨论由IS对应的标准模型。我们研究的IS中的属性集合是有穷的，而Khan在文[7]命题5.6中指出仅包含有穷个属性的语言下的一般模型和这种由IS对应的标准模型是等价的，所以这样的限制是合理的。

给定S及信息集合Inf，利用这些信息对S进行信息更新可以得到新的信息系统。记与S具有相同的对象集合，相同的属性集合，相同的属性值集合的全体信息系统为QS。记信息集合的原子信息的全体为ΣS，简记为Σ。

下面我们来给出由原子信息σ0=(α,a,v)更新S得到Sσ0定义。

定义19由原子信息σ0=(α,a,v)更新S所得Sσ0，或称为S的σ0更新信息系统，记为Sσ0=(W,A,V,fσ0)：

(1)W、A、V=∪a∈AVa和ϵ是更新前的信息系统中的定义。

(2)fσ0如下给出：

(2.1)当x∈[[α]]MS时，fσ0(x,a):=v；

(2.2)当x∈[[α]]MS且a′a时，fσ0(x,a′):=f(x,a′)；

任给S，给定原子信息集合AInf，归纳定义一类信息系统的集合QS，简记为Q。

定义20Q中的元素归纳定义如下：

(1)S是Q的元素；

(2)若S′是Q的元素，则对于任意的σ∈AInf，(S′)σ是Q中的元素；

(3)仅由以上两条形成Q中的元素。

有了上面的准备工作，接下来我们给出信息系统更新的自动机表示。

定义21给定初始信息系统S0，在原子信息集合AInf上进行更新的自动机是一组结构T=(Q,Σ,δ,S0)，其中：

(1)Q是有限的非空的状态集合，也即是信息系统的集合；

(2)Σ是有限的字母表，也即是原子信息集合AInf；

(3)δ:Q×Σ-→Q是状态转换函数，δ(S,σ):=Sσ；

(4)S0是初始状态。

定义22在原子信息集合AInf上进行更新的带有终结状态的自动机是一组结构T=(Q,Σ,δ,S0,Sfin)，其中：

(1)Q是有限的非空的状态集合，也即是信息系统的集合；

(2)Σ是有限的字母表，也即是原子信息集合AInf；

(3)δ:Q×Σ-→Q是状态转换函数，δ(S,σ):=Sσ；

(4)S0是初始状态，Sfin是终结状态。

由自动机理论知δ能唯一扩充为Q×Σ∗到Q上的映射：δ(S,σ)= δ(S,σ0;σ′):=δ(Sσ0,σ′)。

注记6由引理1可得信息系统更新的自动机是确定性有限自动机。

定理3任意给定原子信息集合AInf，则对于任意的原子信息的合成信息σ都有σ;σ≡σ。

证明.由信息等价的定义知，要证σ;σ≡σ，只要证明出Rσ;σ=Rσ即可。先证Rσ;σ⊂Rσ。若MRσ;σM′，由R的定义得，存在M′使得MRσM′RσM′，即有M′=Mσ，M′=M′σ。由定义13知，(Mσ)σ=Mσ，故M′=M′σ= (Mσ)σ=Mσ。于是MRσM′，故Rσ;σ⊂Rσ。再证Rσ;σ⊃Rσ。若MRσM′，由R的定义有，M′=Mσ。由定义13知，(Mσ)σ=Mσ，故M′=(Mσ)σ=Mσ。□于是MRσ;σM′，故Rσ;σ⊃Rσ。

这即表明：在信息系统中，如果获得一个信息，反复按这个信息对系统进行更新，和仅用这个信息更新一次达到的效果是相同的。因此在信息系统更新的逻辑系统中没必要引入如动态逻辑系统（[4]）中的那个星算子。下面举个例子来加以说明。

例1 设S=(W,A,V,f)，其中W={A1,...,A7}，A={size,animality,colour}，f如表1所示。

表1 :S的信息表

经信息σ=((size,s)∧(animality,cat),colour,brown)更新S所得Sσ，则由定义13可计算出更新系统Sσ=(W,A,V,fσ)，fσ如表2所示，同理可得Sσ;σ=Sσ。

注记7Khan M A.和Banerjee M.在文[7]没有提出重复更新的描述，本文的定理3给出重复更新算子（星算子）的意义。这也符合经过同一信息更新若干次和更新一次的效果是相同的这一事实。因此没有必要引入星算子。

定理4MS,x|=[σ]α当且仅当对σ的每一个析取支τ，都有Mδ(S,τ),x|=α。

证明.先证“=⇒”，假设当且仅当的左边成立。任给σ的一个析取支τ，由Rτ的定义有MSRτMδ(S,τ)。再设σ∨是σ的选择范式，由Rσ∨定义，因τ是σ∨的一个析取支，故有MSRσ∨Mδ(S,τ)。由定理2有MSRσMδ(S,τ)。于是由假设当且仅当的左边成立和定义16有Mδ(S,τ),x|=α。

表2 :Sσ的信息表

在原子信息集合AInf上进行更新的自动机是T=(Q,Σ,δ,S0)，若信息系统S是自动机T的终结状态(终结信息系统)，记在原子信息集合AInf上进行更新的自动机中的所有从S0到S的道路的集合为InfS。

定理5给定初始信息系统S0，给定终结信息系统S，则等价于InfS任意子集合的全体元素所形成的选择范式的信息都是从S0到S的信息更新。

证明.任选道路τ∈InfS，由定义22的扩充可得δ(S0,τ)=S，因而MS0RτMδ(S0,τ)，即MS0RτMS。任取等价于InfS任意子集合的全体元素所形成的选择范式的信息σ，由定理2和R的定义有MS0RσMS。故由定义15有信息σ是从S0到S的信息更新。 □

由定理3和定理5马上得到：

定理6 给定初始信息系统S0，给定终结信息系统S，则T=(Q,Σ,δ,S0,S)可接受的语言LT都是从S0到S的信息更新。

5 信息系统及其更新的逻辑系统的模型检测的复杂性：多项式时间

文[1]中给出了结论：模态逻辑模型检测复杂性是多项式时间的。仿照这个结论的证明方法（论域个体标记算法（[1]））得到下面的定理。

下面介绍自原子公式逐层而上给论域个体标记算法。为了对合式公式φ进行模型检测，我们对论域个体x标记上由那些在论域个体x处为真的φ的子公式形成的集合。即对x标记上{ψ|M,x|=ψ且ψ是φ的子公式}，记为label(x)={ψ|M,x|=ψ且ψ是φ的子公式}。我们从命题公式p开始：p∈label(x)当且仅当x∈[[p]]，(a,v)∈label(x)当且仅当f(x,a)=v。对于更复杂的合式公式，布尔型的合式公式如下标记:如果ψlabel(x)，则¬ψ∈label(x)；如果ψ1,ψ2∈label(x)，则ψ1∧ψ2∈label(x)。模态型的合式公式[R(B)]α（对于任意的R(B)∈{IND(B)}B⊆A∪{SIM(B)}B⊆A），如果对任意的xR(B)x′的x′都有α∈label(x′)则[R(B)]α∈label(x)。下文逻辑连接词符号〈〉是[]的对偶符号，即是¬[]¬。

定理7信息系统的逻辑系统的模型检测的复杂性是多项式时间的。

证明.模型检测M,x|=φ（当φ:=〈R(B)〉α时）的算法如下：

算法运行时间是：O(con(φ)×nodes(M)×nodes(M))。其中con(φ)是φ中的联结词的个数，nodes(M)是模型的论域个体数。con(φ)×nodes(M)× nodes(M)也是其他类型的合式公式模型检测运行时间的上界。

最后一步以布尔方式联结而成的公式φ的模型检测的复杂性也是多项式时间的。因此，信息系统的逻辑系统的模型检测的复杂性是多项式时间的。 □

为了给出信息更新逻辑系统的模型检测的复杂性，我们给出由信息系统S0、论域个体xS0（加上标为了区分来自不同信息系统的个体，在不引起混淆时也简记为x）及合式公式φ而确定的有向图GS0,x,φ=(Vφ,Eφ)的定义。

定义23 给定初始信息系统S0及论域个体xS0，归纳于合式公式φ的结构定义一个由它们而确定的有向图GS0,x,φ=(Vφ,Eφ)，Vφ和Eφ分别是顶点集合和有向边集，不引起混淆时候简记为Gφ或G：

注记8定义23通过原子信息合成的更新给不同模型中论域个体建立有向边，通过R(B)后继给相同模型中论域个体建立有向边，从而给定初始信息系统S0及论域个体xS0，给定合式公式φ就形成一个有向图。

自原子公式逐层而上给论域个体标记，若MS,xS|=φ，则对xS标记一个φ。为了对公式φ进行模型检测，对xS标记上{ψ|MS,xS|=ψ且ψ是φ的子公式}，记为label(xS)={ψ|MS,xS|=ψ且ψ是φ的子公式}。对于更新型的合式公式〈σ〉α，如果存在某个的的xSτ有α∈label(xSτ)则〈σ〉α∈label(xS)。其他公式标记方法如定理7前面给出的标记方式。

定理8信息更新逻辑系统的模型检测的复杂性是多项式时间的。

证明.模型检测MS,x|=〈σ〉α的算法如下

算法运行时间是：O(disjun(σ)×con(φ)×nodes(M)×nodes(M))。其中disjun(σ)是σ的析取支数，con(φ)是φ中的联结词的个数，nodes(M)是模型的论域个体数。这个运行时间有上界O(con(φ)×con(φ)×nodes(M)× nodes(M))，它也是其他类型的合式公式模型检测运行时间的上界。因此，信息系统的更新的逻辑系统的模型检测的复杂性是多项式时间的。

6 结束语

M.A.Khan和M.Banerjee在文[7]给出信息系统更新的逻辑系统。我们对信息系统的更新过程进一步研究，通过引入信息等价和将信息范式化，从范式中拆分出的原子信息而得到自动机的文字，从而建立了信息更新的自动机。然后利用自动机给出信息系统更新的刻画，证明了带有终结状态的自动机T=(Q,Σ,δ,S0,Sf)的语言都是从S0到Sf的信息更新。我们本来还打算在这个信息系统更新的逻辑系统中加上信息更新的星算子，但是利用自动机理论发现这个星算子的引入是平凡的。接下来进一步的工作可以利用信息更新的自动机的语言对更新过程作形式推演，具体可以表现为建立类似于Hoare逻辑（[5]）的形式系统。在这个形式系统中，可以对{S0}σ{Sf}做形式推演。这正是我们提出信息系统更新的自动机的初衷和动力。最后利用自动机理论得到了信息系统及其更新逻辑系统的模型检测的复杂性都是多项式时间的。

[1] P.Blackburn,J.F.van Benthem and F.Wolter(eds),2006,Handbook of Modal Logic, Amsterdam:Elsevier.

[2] S.Burris and H.P.Sankappanavar,1981,A Course in Universal Algebra,New York: Springer-Verlag.

[3] I.Duntsch,1997,“A logic for rough sets”,Theoretical Computer Science,179:427-436.

[4] D.Harel,J.TiurynandD.Kozen,2000,Dynamiclogic,Massachusetts:TheMITpress.

[5] C.A.R.Hoare,1985,Communicating Sequential Processes,New York:Springer.

[6] M.A.Khan and M.Banerjee,2009,“A logic for complete information systems”,in C. Sossai and G.Chemello(eds.),Symbolic and Quantitative Approaches to Reasoning with Uncertainty,Vol.5590,pp.829-840,Berlin:Springer Berlin Heidelberg.

[7] M.A.KhanandM.Banerjee,2011,“Logicsforinformationsystemsandtheirdynamic extensions”,ACM Transactions on Computational Logic(TOCL),12(4):29:1-29:36.

[8] M.Kondo,2005,“Algebraic approach to generalized rough sets”,Lecture Notes in Artificial Intelligence,3641:132-140.

[9] T.Y.Lin and Q.Liu,1994,“Rough approximate operators:Axiomatic rough set theory”,in W.Ziarko(ed.),Rough Sets,Fuzzy sets and Knowledge Discovery,pp.256-260,Berlin:Springer.

[10] G.L.Liu,2013,“Using one axiom to characterize rough set and fuzzy rough set approximations”,Information Sciences,223:285-296.

[11] G.L.LiuandW.Zhu,2008,“Thealgebraicstructuresofgeneralizedroughsettheory”, Information Sciences,178(21):4105-4113.

[12] Z.Pawlak,1981,“Information systems theoretical foundations”,Information systems, 6(3):205-218.

[13] Z.Pawlak,1982,“Rough sets”,International Journal of Computer and Information Sciences,11:341-356.

[14] Z.Pawlak,1991,RoughSets:TheoreticalAspectsofReasoningaboutData,TheNetherlands:Kluwer Academic Publishers.

[15] Y.Y.Yao,1998,“Constructive and algebraic methods of the theory of rough sets”, Information Sciences,109:21-47.

[16] 陶仁骥，自动机引论，1986年，北京：科学出版社。

[17] 祝峰，何华灿，“粗集的公理化”，计算机学报，2000年第23卷第3期，第330-333页。

（责任编辑：何健坤）

Automata of Update for Information Systems

Fasheng Cao
Institute of Logic and Cognition,Sun Yat-sen University
caofasheng@163.com

By defining the concepts of information equivalence and normal form,automata of update for information systems is presented.The model of update for information systems is characterized by automata theory.It is proved that it is not necessary to add the iteration operator to the logic system of update for information systems.Then,we obtain the connection with update for information systems and its automata.Finally, the model checking complexities of update for information systems are studied by the automata theory of information system and update logic system.

B81

A

1674-3202(2015)-01-0079-16

2014-12-05