多项式理想准素分解的算法

讨论了多项式理想准素分解的算法,对于理想坐标变换中关键的“一般位置”的计算,给出了一个确定算法,并建立了特别规范Groebner基的概念,利用这一概念及文中提供的相应算法,可以方便地计算理想的维数,进而使用降维的方法来得到高维理想的准素分解。     

The Improvement in Chomsky-Schtzenberger Theorem and Its Form in “Deterministic” Case

In several papers such as[1], [2], [4], [8], the representation problems of formal languages were discussed. It is well-known, Chomsky-Schtzenberger theozem plays an important role in the representation of context-free languages which is one of the most interesting classes of languages. The Chomsky-Schtzenberger theorem asserts that given a Σ_1, there exist Σ_2, a Dyck set and a homomorphism h from onto ∑_1~* which satisfy the property that for each contextfree language a regular set can be found such that h(D_(Σ_2),∩R)=L. In present paper, we establish a normal-form of pushdown automata, abbreviated     

线性方程组对于量词的可满足性

本文讨论有关主理想环上线性方程组对于量词组合的可满足性问题,特别是当全称量词和存在量词混合出现的情形.它的背景之一是模上的线性定理的机械化证明.我们对此问题得到了一个算法型的充要条件,该方法对量词未做任何限制.进而讨论了在有限生成Abel群、初等数论、向量空间、多元多项式环等领域中的应用.     

关于稠密语言的析取结构

本文利用析取语言来刻画稠密语言,得到如下结论:1.关于字母表∑={α},其上任一稠密语言可表为∑上无限多个析取语言的无交并。2.关于任意字母表∑,其上任一稠密语言可表为∑上一离散析取语言与一析取语言的无交并。     

离线非确定图灵机的一个巡迴——空间对偶定理

本文证明了,当f(n),g(n)≥n时,一个f~*(n)巡迥,g~*(n)空间的离线非确定图灵机可被一g~*(n)巡迴,f~*(n)空间的离线非确定图灵机模拟.此外,对于单带和多带非确定图灵机的巡迥——空间对偶问题,本文也做了讨论.     

自由星号语言及其关于左(右)酉星号语言的自由积分解

本文涉及两类星号语言,它们是星号语言类的一个子类,所谓自由星号语言类,以及后者的一个子类,所谓左(右)酉星号语言类.给出了非单位星号语言成自由星号语言和非单位星号语言成左(右)酉星号语言的一些充要条件;并且建立了自由星号语言关于左(右)酉星号语言的自由积分解.     

稠密语言关于析取语言的并分解

本文讨论了稠密语言与析取语言的关系.得到了稠密语言的两个充分必要条件:一个语言是稠密的充分必要条件是它为无限多个析取语言的无交并;一个语言是稠密的充分必要条件是它为两个析取语言的无交并.     

论可识语言族类关于弱连接的封闭性

1974年,Havel从人工智能中的一个实际问题出发,抽象出如下一个关于语言代数学的公开问题:可识语言族类在弱连接运算下是否封闭,本文彻底解决了这一问题,证明了 1.可识语言族类在弱连接运算下不封闭, 2.可识语言族类关于弱连接相客闭包是封闭的.     

语言的Schreier系统

为了开展语言代数结构的研究,本文移植自由群子群的 Schreier 方法到语言理论中来,建立了一般语言描述上的所谓 Schreier 系统,并讨论了这种系统的基本构造.