Art

J-GLOBAL ID：200902015663605274   Reference number：92A0821503

On the Upper Bound of the Shortest Length of Input Strings to Decide the Equivalence of Simple Deterministic Pushdown Automata.

単純決定性プッシュダウンオートマトンの等価性を決定する最短入力記号列長の上界

Author (2)： WAKAKITSU MITSUO (電通大 電気通信) ,  TOMITA ETSUJI (電通大 電気通信)
Material： 電子情報通信学会論文誌 D-1  (IEICE Transactions on Information and Systems, Pt.1 (Japanese Edition))
Volume： 75  Issue： 10  Page： 950-953  Publication year： Oct. 1992 
JST Material Number： S0757B  ISSN： 0915-1915  Document type： Article
Article type： 短報  Country of issue： Japan (JPN)  Language： JAPANESE (JA)

Thesaurus term： pushdown automaton ,...

   To see more with JDream III (charged).   {{ this.onShowAbsJLink("http://jdream3.com/lp/jglobal/index.html?docNo=92A0821503&from=J-GLOBAL&jstjournalNo=S0757B") }}

JST classification (1)： Automaton theory  (JB04000O)

Reference (7)：

• KORENJAK, A. J. Simple deterministic linguages. Proc. IEEE 7th Annual Symposium on Switching and Automata Theory. 1966, 36-46
• WOOD, D. Some remarks on the KH algorithm for s-grammars. BIT. 1973, 13, 476-489
• BUTZBACH, P. Sur l'equivalence des grammaires simples. Actes des premieres journees d'informatique theorique, Langages algebriques. 1973, 223-245
• CAUCAL, D. Algorithme optimal de decision pour l'equivalence des grammaires simples. 1984
• 若月光夫. 単純決定性プッシュダウンオートマトンの等価性判定の改良分岐アルゴリズムとその最大時間計算量. 信学論(D-I). 1991, J74-D-I, 9, 595-603

Terms in the title (4)： プッシュダウンオートマトン ,  等価性 ,  記号列 ,  上界