Superdeterministic PDAs
Superdeterministic PDAs
复制标题
超确定性掌上电脑
DOI：
10.1145/322217.322224
复制
发表时间：
1980
期刊：
影响因子：
--
通讯作者：
E. P. Friedman
中科院分区：
文献类型：
--
作者：
S. Greibach;E. P. Friedman
一个确定性下推存储自动机~S超定，如果它是有限延迟，且只要同一个输入将处于相同状态和m个读取模式的两个可访问配置c~和c~+取为两个配置c，且c‘，m读取模式，则c和c’_i也处于相同的状态，并且c和c_1之间的堆栈高度的变化与c~~和c‘__之间的变化相同，则可以判定一个确定性下推存储自动机是否为超定的。设L(M)表示M最终状态所接受的语言，空存储A语言L是超定的如果存在，S有一个超定义下推存储自动机M，使得对于某个符号$，L=L(M)或L=L(M)，因此，超定语言的名是一个包含所有括号语言和所有Dyck集的AFDL，它是非奇异语言的名是不可比的。L(M0 C L(M))对于M是一个任意的非定义名下推自动机和Mz超定自动机。在时间上与2‘成正比，对于p(N)是机器大小的一个多项式，无论L(Mj=L(Mz)对于M~a一个任意确定的下推商店自动机和M，超级判定mst~c)，都是m时间2z’
A deterministic pushdown store automaton ~s superdetermm~suc if it is finite delay, and whenever two accessible configurations c~ and c~ in the same state and m reading mode are taken by the same input into two configurations c, and c', m reading mode, then c, and c'_, are also m the same state and the change m stack height between c, and c_, is the same as between c~ and c'_, it is decidable whether a deterministic pushdown store automaton is superdetermmistic Let L(M) denote the language accepted by M by final state and empty store A language L is superdetermmlstic if there ,s a superdetermmtstlc pushdown store automaton M such that either L = L(M) or L$ = L(M) for some symbol $, thus, endmarkers are allowed The famdy of superdetermmlstic languages is an AFDL containing all parenthesis languages and all Dyck sets, and it is incomparable with the famdy of nonsingular languages It is decidable whether L(M 0 C L(M.,) for M~ an arbarary nondetermmlstlc pushdown store automaton and Mz superdetermmlstlc, in time proportional to 2-''"' for p(n) a polynomial in the size of the machines It is hkewlse deodable m time2 z'''' whether L(MJ = L(Mz) for M~ an arbitrary deterministic pushdown store automaton and M, superdetermmlst~c