资源描述：
《Random graph languages》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、RandomGraphLanguagesHaizhongShia,,YueShibaCollegeofMathematicsandStatistics,NorthwestNormalUniversity,Lanzhou,Gansu,730070,P.R.ChinabResearchCenterofGraph&BigData,Lanzhou,Gansu,730070,P.R.ChinaAbstractTheretendtobenorelatedresearchesregardingtherelation
2、shipsbetweengraphtheoryandlanguageseversincetheconceptofgraph-semigroupwasfirstproposedin1991.In2011,afterfindingouttheinnerco-relationsamongdigraphs,undirectedgraphsandlanguages,weproposedcertainconceptsincludingundirectedgraphlanguageanddigraphlanguage;m
3、oreover,in2014,weproposedabroadenconcept—(V,R)-languageandproved:(1).bothundirectedgraphlanguageanddigraphlanguageare(V,R)-languages;(2).bothundirectedgraphlanguageanddigraphlanguageareregularlanguages;(3).naturallanguagesareregularlanguages.Inthispaper,
4、weproposeanewconcept—RandomGraphLanguageandbuildtherelationshipsbetweenrandomgraphandlanguage,whichprovidesresearcherswiththepossibilitytodoresearchaboutlanguagesbyusingrandomgraphtheory.Keywords:Randomgraph,randomgraphsemigroup,undirectedgraphlanguage,d
5、igraphlanguage,Reescongruence1.IntroductionLet(S;·)beasemigroup,IisanidealofsemigroupS,thenI=(I×I)∪1snisacongruenceonS.Toseethis,noticethat(x;y)∈Iifandonlyifeitherx=yorbothxandybelongtoI.ItistheneasytoverifythatIisreflexive,symmetric,transitiveandcompa
6、tible.ThequotientsemigroupCorrespondingauthorEmailaddresses:haizhong.shi@163.com(HaizhongShi),GraphTech.Yue@outlook.com(YueShi)PreprintsubmittedtoTheoreticalComputerScienceJune28,2015isS=I={I}∪{{x}:x∈SI};whichitisconvenienttoregardasconsistingofItoget
7、herwiththemembersofSI.InS=ItheproduceoftwoelementsofSIisthesameasthereproductinSifthisliesinSI;otherwisetheproductisI.SincetheelementIofS=Iinthezeroelementofthesemigroup,anotherusefulwayofthinkingofS=Iisas(SI)∪{0}),whereallproductnotfallinginSIar
8、ezero.WeshallcallacongruenceofthistypeaReescongruence.LetVisanon-emptyset.LetusdenotebyFVthesetofallnon-emptyfinitewordsa1a2···aninthe”alphabet”V.AbinaryoperationisdefinedonFVbyjuxtaposition:(a1a2···am)(b1b2···bn)=a1a2···amb
