师海忠,师越.(V,R)-语言[J].计算机科学,2014,41(Z6):33-36
(V,R)-语言
(V,R)-Languages
  
DOI:
中文关键词:  (V,R)-半群,(V,R)-语言,超图半群,超图语言,无向图语言,有向图语言,正则语言,Rees同余 中图法分类号TP301.2文献标识码A
英文关键词:(V,R)-semigroup,(V,R)-language,Hypergraph semigroup,Hypergraph language,Undirected graph language,Digraph language,Regular language,Rees congruence
基金项目:
作者单位E-mail
师海忠 西北师范大学数学与统计学院 兰州730070 haizhong.shi@163.com 
师越 北京工业大学经济与管理学院 北京100022  
摘要点击次数: 6868
全文下载次数: 789
中文摘要:
      V是一个字母表。FV是V上的一个自由半群,R是FV的一个子集。首先,提出了(V,R)-半群的概念,证明了图半群和有向图半群都是(V,R)-半群。其次,提出了超图半群的概念,证明了超图半群是(V,R)-半群,超图半群把超图理论和自由半群理论联系起来。以此为基础,提出了(V,R)-语言和超图语言两个概念。超图语言把超图理论和形式语言理论联系起来。进而,证明了超图语言、无向图语言和有向图语言都是特殊的(V,R)-语言。第三,证明了无向图语言和有向图语言都是正则语言。这就回答了文献“无向图语言”和“有向图语言”中提出的开问题。(V,R)-半群和(V,R)-语言是研究自由半群和形式语言的新理论和新方法。
英文摘要:
      V is an alphabet.FV is a free semigroup on V.R is a subset of FV.At first,we proposed a concept—(V,R)-semigroup and proved that graph-semigroup and digraph-semigroup are both(V,R)-smigroups.Second,we proposed a concept—hypergraph semigroup.The theories of hypergraphs and free semigroups are connected by the hypergraph semigroups.On this base,we proposed two concepts--(V,R)-languages and hypergraph language.The theories of hypergraphs and formal languages are connected by the hypergraph languages.Furthermore,we proved that the hypergraph language,undirected graph and digraph language are all(V,R)-languages.Third,we proved that the undirected graph language and the digrapg language are both regular languages,which answers the open problems in references of “undirected graph languages” and “digraph languages “.(V,R-)semigroups and(V,R)-languages are new theories and methods of studying free semigroups and formal languages.
查看全文  查看/发表评论  下载PDF阅读器