没有合适的资源?快使用搜索试试~ 我知道了~
理论计算机科学电子笔记162(2006)163-166www.elsevier.com/locate/entcs有限树上Zolt'anE'sik1,2数学语言学研究小组西班牙塔拉戈纳摘要我们利用树自动机的级联积给出了表达能力的代数刻画在有限树上的类CTL时态逻辑。关键词:时态逻辑,树自动机,级联积,伪簇1介绍有限自动机的级联积及其半群理论变体在描述几种逻辑对有限词的表达能力方面非常有用,参见。例如,在一个实施例中,[1、3、12、13]。在本文中,我们使用树自动机的级联积[9],对有限树(项)上的一类广泛的时态逻辑的表达能力提供了代数表征2时态逻辑假设R是包含0的自然数的有限子集。我们考虑(有限)秩字母表,使得秩为n的字母的集合n非空in∈R。我们假设每个排序的字母表都有一个固定的字典顺序。有限(基)树,或术语,像往常一样定义。我们用T表示树的集合。1部分由匈牙利国家科学研究基金会资助,拨款T46686。离开部门匈牙利塞格德大学计算机科学系2 电子邮件地址:ze@urv.net1571-0661 © 2006 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi:10.1016/j.entcs.2005.12.081164Z. Ésik/Electronic Notes in Theoretical Computer Science 162(2006)163语法. 对于一个排序字母表n,在n上的公式集是最小的集合,设符号pσ,对所有σ∈φ,关于布尔运算是(析取)和<$(否定),以及下面的结构。 假设L<$TΔ,且对于每个δ∈Δ,<$δ是关于<$的公式。然后L(δ<$→ δ)δ∈Δ(1)是一个除以π的公式。语义 设T是T上的一个公式,t ∈ T。我们说t满足,符号t| = 0,如果• n=pσ,对于某些σ∈n,且t的根标为σ,或• =|=J或t| = JJ,或• t =<$<$J,但t |=J,或• δ∈Δ,且该特征向量是由t∈TΔdetrminedd和amily(δ)δ∈Δbelongt到L. 因此,由于在不同的地理位置上存在着相同的空间,因此在不同的地理位置上,树t,而且,δ是Δn上字典序中的第一个字母,使得t的以v为根的子树满足δ。如果不存在这样的字母,则δ是Δn上按字典顺序排列的最后一个字母。对于任何超过的公式,我们让L表示由定义的语言:L ={t ∈ T:t |{\fn黑体\fs19\bord1\shad1\1cHD8AFAF\4cHC08000\b0}.我们说,当L<$=L<$时,公式<$1和公式<$2(在<$1上)是完全等价的。例2.1设R ={0,2},又设Δ 0={↑0,↓0},Δ 2={↑2,↓2},按字典顺序,使得↑i<↓i,i= 0,2。设L由至少包含一个标记为↑ 0或↑ 2的顶点的Δ-树组成。给出了m上的公式n_i和n_J,证明了m_i=L(↑i→ n_i,↓i →n_J)i= 0,2. t∈T是t个满足的子树。因此,模态算子(1)与L对应于CTL的(非严格)EF模态[10]。类似地,当LJ是在第二层上至少包含一个↑ 0或↑ 2的Δ-树的集合时,则Lj=LJ(↑i→Lj,↓i→Lj)i= 0,2corespondso ntont o t o n t o n t o t ont o to 通过这种模式,我们可以推导出所有常见的CTL模式。我们将考虑与树语言类相关的公式子集。当L是一类树语言时,我们让FTL(L)表示公式的集合,其所有上述形式(1)的子公式使得L属于L。我们用FTL(L)表示所有可由FTL(L)中的公式定义的树语言的类。注2.2当R={ 0, 1}时,我们的逻辑与[15]中定义的逻辑密切相关。见[5]。Z.Ésik /电子笔记在理论计算机科学162(2006)163-1661653树自动机与级联积当L是一类正则树语言时,我们将使用树自动机来刻画逻辑FTL(L)的表达能力假设字母表是一个排序的字母表。由于我们只考虑基树,我们将树自动机定义为没有真子代数的有限代数,即,其由对应于100中的字母的元素生成。 每个树自动机都配备了 它的底层载体的特定子集定义了一个正则语言LT,参见。[6]。当A是带有载体A的树自动机,B是带有载体B的Δ树自动机,α是函数族αn:An×λn→ Δn,n∈R时,级联积A ×αB是带有载体A×B的λ-代数的极小子代数,运算σ((a1,b1),. ,(a n,b n))=(σ(a1,. ,an),δ(bl,. ,bn)),其中δ=α(α1,.,a n,σ),对于所有(a1,b1),.,(an,bn)∈A×B,σ ∈n,n∈ R.4结果下面我们将说,如果对于语言L <$T <$in L的任何商t−1L ={s ∈ T<$:t(s)∈ L},其中t是任何带“洞”的树, 并 且对 于 任何 公 式<$δ ∈ FTL (L ) ,δ∈ Δ , 存在FTL (L )-公 式e q u i v a le n t o (t − 1 L ) (δ <$→ <$δ)δ ∈Δ,则子元在FTL(L)中可表达。进一步地,我们认为,如果对每个树t∈T∈ R,对每个i,使得1 ≤i≤n,那么所有的树x都可在FTL(L)中表示,并且对FTL(L)中的每个公式x,存在一个FTL(L)-公式X i,使得对任意树t ∈ T∈R,t |= X i<$i <$t的根由秩≥ i的字母标记,并且t的第i个直接子树满足我们可以很容易地证明这个条件等价于FTL(L)包含所有有界树语言的条件[7,8]。这两个条件都适用于树上的大多数自然时态逻辑我们的主要贡献是以下一般结果:定理4.1设L是一类正则树语言,使得前件和下一模态都可表示在FTL(L)中。 则一个树语言属于FTL(L)i,它的最小树自动机属于包含L中语言的最小树自动机的最小树自动机类,该最小树自动机类关于级联合成和子项是封闭的。上述定理的一个直接推论是,如果L是一个类,的正则树语言,那么FTL(L)由正则语言。当然,这个事实也可以从明显的观察得出,当L由正则语言组成时,FTL(L)可以嵌入到有限树上的一元二阶逻辑[14]中作为主要结果的进一步推论,我们证明了格包含有界树自动机[7,8]并且关于级联积和同态像是闭的树自动机类V的格同构于形式V=FTL(L)的正则树语言的所有类的格,这些正则树语言关于子元素是闭的并且包含有界树语言。一个166Z. Ésik/Electronic Notes in Theoretical Computer Science 162(2006)163同构由Eilenberg对应给出(c.f. [4]):给定V,将V映射到树语言V的类,其最小自动机属于V,或者等价地,它可以被V中的树自动机接受。在证明定理4.1的过程中,我们建立了树语言类FTL(L)和算子FTL的几个有用的性质。 例如,FTL(L)在布尔运算(平凡)和“逆文字树同态”(几乎平凡)下总是封闭的L中的每一个树语言都属于FTL(L)i,所有的子都可以在FTL(L)中表达。因此,当后面这些条件成立并且L由正则语言组成时,则FTL(L)是我们还证明了FTL是(正规)树语言类上的闭包算子,并建立了字面簇的Eilenberg簇定理假设VParticipateFTL(L)在上述Eilenberg对应下。然后正则树语言L属于FTL(L)i,它的最小树自动机属于到V。因此,当V是可判定的时,逻辑FTL(L)的表达能力得到了有效的刻画。我们应用这种方法来获得有效的特性的CTL的某个片段,无论是在有限树考虑本文在一般的CTL无序树模型上推广了这一结果,补充了文[2]中的结果。引用[1] Baziramwabo,A.,麦肯齐·P和D.陈文辉,[2] 博扬奇克湾和I. Walukiewicz,[3] Cohen,J.,Pin,J. -E、和D.Perrin,On the expressive power of temporal logic,J.Computer andSystem Sciences,46(1993),271[4] Eilenberg,S.,“Automata, Languages, and Machines,” vol. A and B, Academic Press, 1974 and[5] E'sik,Z. 和G. Martin,AnoteonWolpers logic i c,in:P r o c. ICALPWorkshoponSe migroupsandAutomata,Lisboa,2005,61 pp.[6] G'ec s eg,F., 和M. Steninbyy,“Tre e A u to m a ta”,A k a d ′ e miai K i a d ′ o,1984.[7] Heuter,U.,定义树语言,EATCS公报,35(1988),137[8] Nivat,M.,和A.Podelski,《定义树语言(英语:[9] Ricci,G.,树自动机的级联和通用代数中的计算,数学。系统理论,7(1973),201[10] Schneider,K.,[11] Steinby,M.,树语言的一般变种理论。Comput. 科学,205(1998),1[12] Straubing,H.,[13] Straubing,H.,Therien,D.,和W.Thomas,Regular languages defined with generalized quantiers,信息与计算,118(1995),289[14] 撒切尔,J.W.,和J. B. Wright,广义有限自动机理论及其在二阶逻辑决策问题中的应用。 数学SystemsTheory,2(1968),57[15] Wolper,P.,时间逻辑可以更有表现力,信息和控制,56(1983),72
下载后可阅读完整内容,剩余1页未读,立即下载
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/default.jpg!1)
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
我的内容管理 收起
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
会员权益专享
最新资源
- VMP技术解析:Handle块优化与壳模板初始化
- C++ Primer 第四版更新:现代编程风格与标准库
- 计算机系统基础实验:缓冲区溢出攻击(Lab3)
- 中国结算网上业务平台:证券登记操作详解与常见问题
- FPGA驱动的五子棋博弈系统:加速与创新娱乐体验
- 多旋翼飞行器定点位置控制器设计实验
- 基于流量预测与潮汐效应的动态载频优化策略
- SQL练习:查询分析与高级操作
- 海底数据中心散热优化:从MATLAB到动态模拟
- 移动应用作业:MyDiaryBook - Google Material Design 日记APP
- Linux提权技术详解:从内核漏洞到Sudo配置错误
- 93分钟快速入门 LaTeX:从入门到实践
- 5G测试新挑战与罗德与施瓦茨解决方案
- EAS系统性能优化与故障诊断指南
- Java并发编程:JUC核心概念解析与应用
- 数据结构实验报告:基于不同存储结构的线性表和树实现
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)