收藏本站
《南开大学》 2014年
收藏 | 手机打开

上下文无关文法,多元稳定多项式及递增树

郝小健  
【摘要】:与上下文无关文法相关的微分算子的概念是由陈永川最先引入的。进一步陈永川提出了运用上下文无关文法生成组合多项式的框架。此后上下文无关文法被广泛用于生成和处理组合多项式。Borcea和Branden发展了多元多项式的稳定性理论。在他们工作的基础上Haglund和Visontai提出了一个证明Stirling排列和r-Stirling排列生成函数的稳定性的方法。本文的主要目的是运用上下文无关文法来生成多元组合多项式,并证明多元组合多项式的稳定性。同时,我们将通过恰当的文法标号生成一些组合结构并利用上下文无关文法得到相关的组合恒等式。 论文结构如下。第一章我们主要介绍相关的背景知识,基本概念及常用符号。我们将着重对Haglund和Visontai所做的关于Stirling排列和r-Stirling排列生成函数的稳定性的工作进行介绍。 在第二章中,我们回顾了上下文无关文法的相关背景。在本章节中我们将集中介绍如何使用上下文无关文法刻画组合结构并生成相关的组合多项式,例如:Stirling多项式,Eulerian多项式及二阶Eulerian多项式。其中,我们主要研究了包含多个参数的组合多项式。 第三章,我们主要介绍如何运用上下文无关文法生成多元组合多项式,并证明其稳定性。基于Borcea和Branden给出的关于保持多重仿射多项式稳定性的算子的刻画,我们给出运用上下文无关文法证明多元多项式的稳定性的方法。进一步,我们将给出一些通过上下文无关文法生成的多元多项式的稳定性证明。其中我们解决了Haglund和Visontai提出的关于给出Legendre-Stirling排列下降位的生成函数的稳定细化的问题。三项递推关系是组合数学中一类重要的递推关系,在本章结尾我们给出了一个生成特殊三项递推关系的文法。运用这个文法我们得到了一些新的组合恒等式,并且给出一组算子生成满足该三项递推关系序列的生成函数。在此基础上我们得到了此算子保持稳定性的充分必要条件。 在第四章中,我们主要说明了一些可以递归生成的组合结构都是可以由上下文无关文法生成的,例如:递增树,递增二叉树,自反排列,递增圈树及强受限森林。通过上下文无关文法,这些组合结构的性质往往可以被容易的证明。在本章中,我们引入了一种被称之为禁止替换的特殊替换规则,我们将利用含有禁止替换规则的上下文无关文法来生成一些组合结构并证明一些组合恒等式。 在第五章中,我们将上下文无关文法与缸模型相关联。我们利用缸模型对刻画排列中连续的132型及强受限森林中的绝对孤立点的上下文无关文法进行分析,并给出上述统计量的一些分析结果。
【学位授予单位】:南开大学
【学位级别】:博士
【学位授予年份】:2014
【分类号】:O175.3;O174.14

手机知网App
【共引文献】
中国期刊全文数据库 前3条
1 Pei-Chu Hu;;Global Meromorphic Solutions of Partial Differential Equations[J];Analysis in Theory and Applications;2014年01期
2 WANG Yi;ZHU BaoXuan;;Proofs of some conjectures on monotonicity of number-theoretic and combinatorial sequences[J];Science China(Mathematics);2014年11期
3 段萍;杜金元;;RIEMANN-HILBERT CHARACTERIZATION FOR MAIN BESSEL POLYNOMIALS WITH VARYING LARGE NEGATIVE PARAMETERS[J];Acta Mathematica Scientia;2014年02期
中国博士188bet全文数据库 前8条
1 王星炜;组合多项式的对数凹性质[D];南开大学;2010年
2 苏循团;组合三角中的单峰型问题[D];大连理工大学;2011年
3 杨丽敏;赋权树上的组合及渐近结果[D];南开大学;2006年
4 马世美;组合学中实零点多项式的若干问题[D];大连理工大学;2009年
5 刘丽;组合学中的单峰型问题[D];大连理工大学;2008年
6 郭剑峰;组合序列对数性质的分析方法证明[D];南开大学;2013年
7 龚泽;有限Coxeter群上统计量的研究[D];南开大学;2013年
8 彭芳芳;拉马努金与查波顿多项式上的组合学[D];南开大学;2014年
中国硕士188bet全文数据库 前5条
1 叶明玉;一些组合数的对数凸性和对数凹性的组合证明[D];大连理工大学;2006年
2 张翠;一些多项式的实零点问题[D];大连理工大学;2006年
3 孟辉;细分格式、插值及小波的若干问题研究[D];浙江大学;2006年
4 张滨;组合学中的极值问题研究[D];大连理工大学;2013年
5 林志聪;树的图同态与排列的统计量[D];兰州大学;2013年
【相似文献】
中国期刊全文数据库 前10条
1 马世骅;一个万能的ω上下文无关文法[J];科学通报;1986年21期
2 毛红梅;夏利民;肖云;;应用模块法杂凑语言的上下文无关文法[J];江西科学;2007年01期
3 马世骅;万能的ω-上下文无关文法及它的一个应用[J];数学学报;1989年01期
4 宋小震;韩召伟;李永明;;量子上下文无关文法的代数性质[J];计算机工程与应用;2011年04期
5 盛莉;;格值上下文无关文法的范式[J];纯粹数学与应用数学;2010年02期
6 潘培琛;一般上下文无关文法的一个分析算法[J];北京大学学报(自然科学版);1989年05期
7 杨敏,王志远,杨红雨,游志胜;基于上下文无关文法电报译码的算法实现[J];四川大学学报(自然科学版);2001年02期
8 左劼;段磊;唐良;巩杰;唐常杰;;求解复杂约束问题的基因表达式编程文法模型[J];四川大学学报(自然科学版);2009年03期
9 杨春志;张超;;格值上下文无关文法对基于词的计算[J];重庆交通大学学报(自然科学版);2009年04期
10 张志春,雷相波;YACC中的冲突消解方法[J];哈尔滨师范大学自然科学学报;2002年04期
中国重要会议论文全文数据库 前2条
1 吴端仪;陈雷;陈海明;;上下文无关文法的句子生成方法综述[A];2006年全国理论计算机科学学术年会论文集[C];2006年
2 柏明强;莫智文;;Fuzzy上下文无关文法的简化[A];中国系统工程学会模糊数学与模糊系统委员会第十一届年会论文选集[C];2002年
中国博士188bet全文数据库 前1条
1 郝小健;上下文无关文法,多元稳定多项式及递增树[D];南开大学;2014年
中国硕士188bet全文数据库 前1条
1 金龙飞;通用可扩展编译器前端生成器的设计与实现[D];吉林大学;2005年
中国知网广告投放
相关机构
>吉林大学
>南开大学
相关作者
>郝小健 >金龙飞
 快捷付款方式  订购知网充值卡  订购热线  帮助中心
  • 400-819-9993
  • 010-62791813
  • 010-62985026