期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

A Note on Non-Closure Property of Sublogarithmic Space-Bounded 1-Inkdot Alternating Pushdown Automata with Only Existential （Universal） States 被引量：1

A Note on Non-Closure Property of Sublogarithmic Space-Bounded 1-Inkdot Alternating Pushdown Automata with Only Existential （Universal） States
原文传递
导出
摘要 1-inkdot alternating pushdown automaton is a slightly modified alternating pushdown automaton with the additional power of marking at most 1 tape-cell on the input （with an inkdot） once. This paper investigates the closure property of sublogarithmic space-bounded 1-inkdot alternating pushdown automata with only existential （universal） states, and shows, for example, that for any function L（n） such that L（n） ≥ log logn and L（n） = o（log n）, the class of sets accepted by weakly （strongly） L（n） space-bounded 1-inkdot two-way alternating pushdown automata with only existential （universal） states is not closed under concatenation with regular sets, length-preserving homomorphism, and Kleene closure. 1-inkdot alternating pushdown automaton is a slightly modified alternating pushdown automaton with the additional power of marking at most 1 tape-cell on the input （with an inkdot） once. This paper investigates the closure property of sublogarithmic space-bounded 1-inkdot alternating pushdown automata with only existential （universal） states, and shows, for example, that for any function L（n） such that L（n） ≥ log logn and L（n） = o（log n）, the class of sets accepted by weakly （strongly） L（n） space-bounded 1-inkdot two-way alternating pushdown automata with only existential （universal） states is not closed under concatenation with regular sets, length-preserving homomorphism, and Kleene closure.
作者 徐建良 刘运霞 Tsunehiro Yoshinaga
机构地区 Department of Computer Science Department of Computer Science and Electronics Engineering
出处 《Journal of Computer Science & Technology》 SCIE EI CSCD 2006年第6期979-983,共5页 计算机科学技术学报（英文版）
基金 This work is supported by the National Natural Science Foundation of China under Grant No. 60403012,
关键词 alternating pushdown automata 1-inkdot sublogarithmic space closure property alternating pushdown automata, 1-inkdot, sublogarithmic space, closure property
分类号 TP3 [自动化与计算机技术—计算机科学与技术]
  • 相关文献

参考文献14

  • 1Ranjan D, Chang R, Hartmanis J. Space bounded computations: Review and new separation results. Theoretical Computer Science, 1991, 80: 289-302.
  • 2Geffert V. Nondeterministic computations in sublogarithmic space and space constructability. SIAM J. Comput, 1991, 20(3): 484-498.
  • 3Chandra A K, Kozen D C, Stockmeyer L J. Alternation. J. ACM, 1981, 28(1): 114-133.
  • 4Chang J H, Ibarra O H, Ravikumar B. Some observations concerning alternating Turing machines using small space. Information Processing Letters, 1987, 25: 1-9, 1987 (Erratum: Information Processing Letters, 1988, 27: 53.)
  • 5Ito A, Inoue K, Takanami I. A note on alternating Turing machines using small space. IEICE Trans. Inf. & Syst, 1987, E70(10): 990-996.
  • 6Li'skiewicz M, Reischuk R. The sublogarithmic alternating space world. SIAM J. Comput, 1996, 25(4): 828-861.
  • 7Szepietowski A. Turing machines with sublogarithmic space. Lecture Notes in Computer Science 843. Berlin: Springer-Verlag, 1994, pp.89-94.
  • 8Inoue K, Ito A, Takanami I. On 1-inkdot alternating Turing machines with small space. Theoretical Computer Science, 1994, 127: 171-179.
  • 9Xu J. Alternating pushdown automata with sublogarithmic space [Dissertation]. Yamaguchi University, 1998.
  • 10Xu J, Inoue K, Wang Y, Ito A. A note on alternating pushdown automata with sublogarithmic space. IEICE Trans. Inf. & Syst, 1996, E79-D(4): 259-270.

同被引文献14

  • 1Ranjan D,Chang R,Hartmanis J.Space bounded computations:review and new separation[J].Theoretical Computer Science,1991,80:289-302.
  • 2Geffert V.Nondeterministic computations in sublogarithmic space and space constructability[J].SIAM J Computations,1991,20(3):484-498.
  • 3Inoue K,Ito A,Takanami I.A relationship between non-deterministic Turing machines and 1-inkdot Turing machines with small space[J].Information Processing Letters,1992,43:225-227.
  • 4Inoue K,Ito A,Takanami I,et al.A note on multi-inkdot nondeterministic Turing machines with small space[J].Information Processing Letters,1993,48:285-288.
  • 5Chandra A,Kozen D,Stockmeyer L.Alternation[J].J ACM,1981,28(1):114-133.
  • 6Braunmühl B,Gengler R,Rettinger R.The alternation hierarchy for sub-logarithmic space is infinite[J].Computational Complexity,1993,3:207-230.
  • 7Chang J,Ibarra O,Ravikumar 13.Some observations concerning alternating Turing machines using small space[J].Information Processing Letters,1987,25:1-9.(Erratum:Information Processing Letters,1988,27:53).
  • 8Ito A,Inoue K,Takanami I.A note on alternating Turing machines using small space[J].IEICE Trans Inf & Syst,1987,ET0(10):990-996.
  • 9Liskiewicz M,Reischuk R.The complexity world below logarithmic space[C].Amsterndam:Proceedings of the Ninth Annual Structure in Complexity Theory,1994:64-78.
  • 10Inoue K,Ito A,Takanami I.On 1-inkdot alternating Turing machines with small space[J].Theoretical Computer Science,1994,127:171-179.

引证文献1

Journal of Computer Science & Technology
2006年 第6期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部