2 DECIDABILITY RESULTS FOR DETERMINISTIC PUSHDOWN AUTOMATA

被引：20

作者：

LINNA, M

机构：

[1] Department of Mathematical Sciences, University of Turku

来源：

JOURNAL OF COMPUTER AND SYSTEM SCIENCES | 1979年 / 18卷 / 01期

关键词：

D O I：

10.1016/0022-0000(79)90055-2

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

A real-time deterministic pushdown automaton is said to be stack uniform if for each input letter a, every a-tule has the same effect on the length of the pushdown store, i.e., if (s1, A) →a (S2, w) and (s1′, A′) →a (s2′, w′) are two a-rules, then the lengths of w and w′ are equal. It is shown that the equivalence problem for stack uniform automata and the inclusion problem for stack uniform automata with empty store acceptance are decidable. © 1979.

引用

页码：92 / 107

页数：16

共 13 条

[1]

Friedman E. P., 1976, Theoretical Computer Science, V1, P297, DOI 10.1016/0304-3975(76)90074-8

[2]

Harrison M. A., 1973, Journal of Computer and System Sciences, V7, P237, DOI 10.1016/S0022-0000(73)80008-X

[3]

Hopcroft J.E., 1966, SWAT, P36, DOI DOI 10.1109/SWAT.1966.22

[4]

JAFFE VA, 1974, KIBERNETIKA KIEV, V2, P89

[5] FORMAL TRANSLATIONS AND SZILARD LANGUAGES [J].

KRIEGEL, HP ;

MAURER, HA .

INFORMATION AND CONTROL, 1976, 30 (02) :187-198

[6]

KRIEGEL HP, 1976, LEFT FITTING TRANSLA

[7] ASSOCIATE LANGUAGES AND DERIVATIONAL COMPLEXITY OF FORMAL GRAMMARS AND LANGUAGES [J].

MORIYA, E .

INFORMATION AND CONTROL, 1973, 22 (02) :139-162

[8]

Penttonen M., 1974, Acta Informatica, V3, P285, DOI 10.1007/BF00288639

[9] PROPERTIES OF DETERMINISTIC TOP-DOWN GRAMMARS [J].

ROSENKRANTZ, DJ ;

STEARNS, RE .

INFORMATION AND CONTROL, 1970, 17 (03) :226-+

[10] RESULT ON EQUIVALENCE PROBLEM FOR DETERMINISTIC PUSHDOWN AUTOMATA [J].

TANIGUCHI, K ;

KASAMI, T .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1976, 13 (01) :38-50

← 1 2 →