The Equivalence Problem for Real-Time Strict Deterministic Languages
The Equivalence Problem for Real-Time Strict Deterministic Languages
复制标题
实时严格确定性语言的等价问题
DOI：
10.1016/s0019-9958(80)90887-6
复制
发表时间：
1980
期刊：
影响因子：
--
通讯作者：
N. Honda
中科院分区：
文献类型：
--
作者：
M. Oyamaguchi;N. Honda
确定性下推存储自动机（dpda）的等价性问题近年来受到广泛关注。然而，它还没有解决一般dpda的。对于dpda的某些子类或确定性上下文无关语言，等价问题被证明是可判定的：简单dpda，科伦亚克和Hopcroft（t966）; LL语言，Rosenkrantz和Stearns（1970）;非奇异dpda，Valiant（1973）;两个dpda，其中一个是非奇异的，Taniguchi和Kasami（1976）;有限转dpda，Valiant（1974）;单计数器自动机，Valiant和Paterson（1975）;无状态dpda，Oyamaguchi和本田（1978）;堆栈统一dpda，Linna（1979）。关于等价问题的其他结果可以在Beeri（1976），Courcelle（1974，1977），Friedman（1977），Harrison，Hovel，and Yehudai（1978），Katayama，Tsuchiya，and Enomoto（1975），Wood（1973），科伦亚克和Hopcroft（1966）是第一篇证明简单确定语言（So语言）等价问题是可判定的论文。SO语言是一种被简单dpda接受的语言，即被单态dpda接受的语言。Rosenkrantz和Stearns（1970）证明了LL语言的等价问题是可判定的。的LL
The equivalence problem for deterministic pushdown store automata (dpda) has received much attention in recent years. However, it has not been solved for general dpda's. For some subfamilies of dpda's or deterministic context-free languages the equivalence problems were shown to be decidable: simple dpda's, Korenjak and Hopcroft (t966); LL languages, Rosenkrantz and Stearns (1970); nonsingular dpda's, Valiant (1973); two dpda's, one of which is nonsingular, Taniguchi and Kasami (1976); finite-turn dpda's, Valiant (1974); one-counter automata, Valiant and Paterson (1975); stateless dpda's, Oyamaguchi and Honda (1978); stack uniform dpda's, Linna (1979). The other results concerning the equivalence problems can be found in Beeri (1976), Courcelle (1974, 1977), Friedman (1977), Harrison, Hovel, and Yehudai (1978), Katayama, Tsuchiya, and Enomoto (1975), Wood (1973).Korenjak and Hopcroft (1966) is the first paper that proved the equivalence problem for simple deterministic languages (So languages) to be decidable. An SO language is a language accepted by a simple dpda, ie, a language accepted by single-state dpda accepting by empty stack. Rosenkrantz and Stearns (1970) showed that the equivalence problem for LL languages is decidable. An LL