强可识语言族

Σ为一有限集,Σ~*表示Σ生成的自由么半群,Σ~*的元素与子集分别称为Σ上的字与语言,2~(Σ*)表示Σ~*的幂集,L(Σ)=2~(Σ*)—{φ}的子集称为Σ上的语言族。在人工智能中的一些问题的推动下,1974年Havet等人开创了语言的分支代数结构的研究,定义了有限分支自动机,从而导致了作为有限分支自动机识别的所谓可识语言族的研究;Havel在文献[2]中又引进了语言的相似度的概念,进而定义了语言之间的一种距离d,使(L(Σ),d)成一距离空间;文献[2]中还定义了语言族的一种替换性,并证明了,语言族是自相容的,当且仅当它具替换性且为L(Σ)的闭集。     

交换封闭的理想语言及其准素分解

设X为一个有限集,X~*表示由X生成的自由么半群。X中的元素叫字母,X~*的元素与子集分别称为X上的字与语言。X~*的恒等元称为空字,记为λ。且记X~+=x~*-{λ}。 关于X上任一语言A,如下定义的X~*上的关系P_A是X~*上的同余:     

镶成右凸语言并、交、连结的超码与右凸语言幺半群的自由性

设X为有限字母表,X~*为X生成的自由幺半群。X~*的子集称为X上的语言,X~*的元素称为X上的字,X~*的恒等元1称为X上的空字,X~+=X~*-{1}。很多作者认为X~*上的嵌入序≤是一个十分重要的偏序: x≤y当且仅当x=x_1x_2…x_n,y=y_1x_1y_2x_2…y_nx_ny_(n+1)。围绕嵌入序定义了若干类语言:     

一个求强连通自动机的自同构群的多项式算法

在本文中,所谓自动机是指一个体系(?)=(S,∑),其中S为一个集合,其元素称为状态,∑为一个集合,其元素称为字母,并且对任何s∈S和σ∈∑,都有一个状态与之对应,并记作s~σ。∑的字母的有限序列称为字。称(?)是强连通的,如果对任何两个状态s,s′∈S都有∑上的字ω=σ_1σ_2…σ_i,使s~ω=s′,其中s~ω=(((s~(σ_1)~σ_2)…)~σ_t。称S到自身的一个1-1映     

关于循环自动机若干问题的多项式时间算法

自动机A=(Q,Σ,δ)称为循环的。如果存在状态q_0∈Q,使得对于任何状态P∈Q,有x∈Σ~*,成立ε(q_0,x)=P;q_0称为A的一个生成元。本文中所指的自动机均为有限自动机。自动机A=(Q,Σ,δ)的一个自同态是一个映射ξ:Q→Q,满足(?)_a∈Σ,P∈Q(ξ(δ(P,a))=     

一个万能的ω上下文无关文法

∑~∞是字母表∑上的一切ω字的集合。令c、(?)、d、(?)是不在∑中的符号。令∑_1={c,(?),d,(?)},记△=Σ∪Σ_1。令∽是△~*上如下定义的二元关系:     

L-fuzzy拓扑空间逆系统间的映射

本文中的有关术语和记号请参看文[1,2]。定义设S={L~(x_σ),G_ρ~σ,Σ)和S′={L~(x′)σ′,T_ρ′~σ′,Σ′}分别是空间族{(L~Xσ,δ_σ)}σ∈Σ和{(L~X′σ′,~′δ_σ′)}σ′∈Σ′的逆系统。若i)φ:Σ′→     

富里埃级数的负阶蔡查罗绝对求和因子

设级数Σa_(?)的α阶蔡查罗平均是σ_(?)~a,σ_(-1)~a=0.当级数Σ|σ~(?)~a-σ~(?)~a|收敛时,称级数Σa_(?)是|C,a|可和.设f(x)∈L(0,2π),φ(t)=1/2[f(x+t)+     

形如<(?)·(?)>的-正则半群簇

称半群S为~*-正则半群,如果有一个映射*:S→S,x|→x~*,使得下面等式成立:x=xx~*x,(x~*)~*=x,(xy)~*=y~*x~*,(?)_x,y∈S.记R~*为全体~*-正则半群构成的类,则作为(2,1)型泛代数,R~*被以下等式所确定:     

积分语言族的强可识性、半可识性与语言族的强替换性

令∑为有限字母表,∑~*为三生成的自由么半群。u∈∑~*为∑上的字,L ∑~*为∑上的语言,x L(∑)为∑上的语言族。∫XdV为关于字V的X的积分。c′(X)为X的强相容闭包。 郭聿琦等建立并讨论了语言族的强可识性,半可识性与强替换性。本文讨论积分语言族的强可识性与半可识性,建立了积分语言族强可识与半可识     

形如<(?)·(?)>的-正则半群簇

<正>称半群S为~*-正则半群,如果有一个映射*:S→S,x|→x~*,使得下面等式成立:x=xx~*x,(x~*)~*=x,(xy)~*=y~*x~*,(?)_x,y∈S.记R~*为全体~*-正则半群构成的类,则作为(2,1)型泛代数,R~*被以下等式所确定:     

Levin猜想之证明

一、若干记号 设B={0,1},N={0,1,2,…}.B~n(n∈(N)和B~∞分别表示字母表B上的长为n的字全体和右端无穷的字全体。记B~*=(?)B~n。用x表示有限或无限0-1串,即x∈B~*∪ B~∞,l(x)表示x的长度,带有下标的x_i(i=1,2,…)表示B中的字母,x表示取值于B的随机     

可结合的BCI代数

1966年由Imai及井关清志一起引进了BCK代数,即有下列:定义1 设X是具有一个二元运算*和一个常元0的一个集。那末X被称为一个BCK代数,是指它满足下列条件:(Ⅰ)(x*y)*(x*z)≤z*y;(Ⅱ)x*(x*y)≤y;(Ⅲ)x≤x;(Ⅳ)0≤x;(Ⅴ)x≤y,y≤xx=y;(Ⅵ)x≤yx*y=0。日本、斯里兰卡等国许多数学家,从事对这种代数系的研究,写出了大量的论文,得到了很多结果(文献[1])。本文要用到BCK代数的下列两个性质:     

常平均曲率曲面的等距变形

本文要证明一个有趣的结果。 定理 3维常曲率空间M~3(c)内具常平均曲率C_1(C_1>0)的无脐点曲面片Σ能够等距变形为另一具常平均曲率C_2(C_2>0和C_1≠C_2)的无脐点曲面片Σ~*的充要条件是Σ是常主曲率的可展无脐点曲面片。即在R~3内,Σ是圆柱面片;在单位球面S~3内,Σ是平环面     

一个f-析取的上下文无关前缀码

郭聿琦,Shyr和Thierrin讨论了f-析取语言,本文作为f-析取语言的一点注记,给出一非析取的f-析取的上下文无关前缀码。 设X是有限字母表X生成的自由么半群.X的元素称为X上的字。X的恒等元称为x上的空字,记为ε.X的子集称为X上的语言。关于任一L(?)X,在X上定义等价关系P_L如下:     

Poisson积分作为算子半群

考虑与半空间R_ ~(n 1)={(x,t);x∈R~n,t>0)关联的Puisson积分:P_1*f=∫_(R~n)P_t(x-ξ)f(ξ)dξ(t>0),这里Poisson核(?),c_n=1/ω_n,ω_n是R~(n 1)中单位球面面积,|x|~2=X_1~2     

超核的奇异相似谱

近年来,通过在核上的奇异交换反应(κ~-,π~-),已经发现了一些超核谱如_△~9Be,_Σ~9Be和_△~(12)C,_Σ~(12)C等.分析无反冲奇异交换反应(κ~-,π~-)的实验激发谱,人们可以发现     

典型相关与广义相关系数

设x和y分别为p×1、q×1随机向量,协方差矩阵为记ρ_i(x,y)为x与y的第i个典型相关系数,即且ρ_1(x,y)≥…≥ρ_t(x,y)>0,t=R(Σ_(xy))。这里A~-和R(A)分别表示A的广义逆和秩。本文证明了如下三个定理。定理1 设q≤r=R(Σ_(xx)),则q×1随机向量y满足cov(y)=l_q,且使达到最     

抛物型方程柯西问题近似解法

资料[1]研究了线性抛物型方程柯西问假定连续导数。u(x,:)~ d才 十艺。dxr,…Ox共,口ta。 ,~价(已,,”、., :》△u(x,t)(二,,)~鲍叹些 头, (o镇a,簇户,l《矛《, z)都存在,且对每一变数都有周期1,命 亡=1 a(x,t)u(x,t) f(x,t),”护”一戳;厄△一兰 口对十‘二 O2-t-— dx蕊(x,t)〔少,x「(人万r占务*)价]‘p·”’·“,!,(3)。(x,,)}:,~o,(l)(2)其中少为:{(x,假定a‘(笼,t),t):x〔石,,t〔(o,T]}.a(x,t),f(x,t)对向量x此处 占久*价(x,,)~ 一小(丸,·lr、/云‘甲、二,,“”二走十入,’‘”‘,二,x*一h*,…,t)],的每一分量周期为l,在少:{(x,t):…     

拓扑Markov链

给定K(>1)个符号{0,1,…,k—1}。记Σ_k为k单边符号空间,其元素为这里记σ为Σ_k上转移自映射。