有向图语言

计算机工程与应用 ›› 2011, Vol. 47 ›› Issue (22): 53-56.

有向图语言

师海忠

西北师范大学数学与信息科学学院，兰州 730070

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2011-08-01 发布日期:2011-08-01

Digraph languages

SHI Haizhong

College of Mathematics and Information Science，Northwest Normal University，Lanzhou 730070，China

Received:1900-01-01 Revised:1900-01-01 Online:2011-08-01 Published:2011-08-01

摘要/Abstract

摘要： 经典形式语言有两条主线，就是自动机线索与形式文法线索。利用有向图理论和有向图半群理论建立了另一条线索——有向图语言，讨论了两类特殊的有向图语言——de Bruijn有向图语言和Kautz有向图语言，引入了连通语言及语言的直径等概念，计算出了de Bruijn有向图语言和Kautz有向图语言的直径。

关键词: 形式语言, 有向图, 有向图语言, de Bruijn有向图语言, Kautz有向图语言

Abstract: Research for formal languages have two main lines，automatons and formal grammars.A new line for formal languages，digraph languages is built.Furthermore，two special digraph languages，de Bruijn digraph languages and Kautz digraph languages are discussed.Two concepts，connected languages and diameter of languages are also proposed.The diameters of de Bruijn digraph languages and Kautz digraph languages are computed.

Key words: formal language, digraph, digraph language, de Bruijn digraph language, Kautz digraph language

师海忠. 有向图语言[J]. 计算机工程与应用, 2011, 47(22): 53-56.

SHI Haizhong. Digraph languages[J]. Computer Engineering and Applications, 2011, 47(22): 53-56.

[1]	李振涛，冯元珍，王正新. 事件触发下多智能体系统固定时间二分一致性[J]. 计算机工程与应用, 2021, 57(21): 80-86.
[2]	陈恒1，2，李冠宇2，孙云浩2. 重排序RDF流三元组模式的蚁群优化方法[J]. 计算机工程与应用, 2017, 53(12): 172-177.
[3]	刘敏娜，解争龙，黄素萍. 基于任务图的并行调度MEWFM算法[J]. 计算机工程与应用, 2015, 51(10): 67-71.
[4]	耿显亚，许峰. 基于图论模型的一类集成电路布线算法[J]. 计算机工程与应用, 2015, 51(1): 21-25.
[5]	袁津生，毛新武. 基于组合特征的中文新闻网页关键词提取方法[J]. 计算机工程与应用, 2014, 50(19): 222-226.
[6]	高东，许欣，马昕，张贝克. 基于符号有向图与趋势分析的故障诊断框架[J]. 计算机工程与应用, 2014, 50(13): 6-9.
[7]	马昕，张贝克. 模糊SDG故障诊断方法及其应用[J]. 计算机工程与应用, 2011, 47(9): 221-224.
[8]	党正军，杜中军. 基于图裁减和图搜索的工作流图验证算法[J]. 计算机工程与应用, 2011, 47(4): 226-228.
[9]	高文宇. 有向图连通支配集求解算法[J]. 计算机工程与应用, 2010, 46(21): 9-13.
[10]	张培颖. 运用有向图进行中文分词研究[J]. 计算机工程与应用, 2009, 45(22): 123-125.
[11]	郑炜,张科,汪芳. 概率预测的网络数学模型及其应用[J]. 计算机工程与应用, 2009, 45(18): 59-61.
[12]	宋超,刘明,龚海刚. 解决无线传感器网络能量洞问题的贪婪算法[J]. 计算机工程与应用, 2009, 45(15): 24-27.
[13]	姚春龙,王昱. 基于权值设定策略的公交出行路径查询模型[J]. 计算机工程与应用, 2009, 45(11): 241-244.
[14]	马芳芳¹,宋弢¹,李涵². DNA编码文法的分析与设计[J]. 计算机工程与应用, 2008, 44(28): 83-85.
[15]	舒少龙林峰黄志强. 离散事件系统N步稳定性分析[J]. 计算机工程与应用, 2007, 43(7期): 17-19.