Abstract
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 log nn 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.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Ranjan D, Chang R, Hartmanis J. Space bounded computations: Review and new separation results. Theoretical Computer Science, 1991, 80: 289–302.
Geffert V. Nondeterministic computations in sublogarithmic space and space constructability. SIAM J. Comput., 1991, 20(3): 484–498.
Chandra A K, Kozen D C, Stockmeyer L J. Alternation. J. ACM, 1981, 28(1): 114–133.
Chang 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.)
Ito A, Inoue K, Takanami I. A note on alternating Turing machines using small space. IEICE Trans. Inf. & Syst., 1987, E70(10): 990–996.
Liśkiewicz M, Reischuk R. The sublogarithmic alternating space world. SIAM J. Comput., 1996, 25(4): 828–861.
Szepietowski A. Turing machines with sublogarithmic space. Lecture Notes in Computer Science 843. Berlin: Springer-Verlag, 1994, pp.89–94.
Inoue K, Ito A, Takanami I. On 1-inkdot alternating Turing machines with small space. Theoretical Computer Science, 1994, 127: 171–179.
Xu J. Alternating pushdown automata with sublogarithmic space [Dissertation]. Yamaguchi University, 1998.
Xu 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.
Xu J, Yoshinaga T, Inoue K et al. Alternation for sublogarithmic space-bounded alternating pushdown automata. Theoretical Computer Science, 2001, 259: 475–492.
Xu J, Chen Y, Yoshinaga T et al. On 1-inkdot alternating pushdown automata sublogarithmic space. IEICE Trans. Inf. & Syst., 2003, E86-D(9): 1814–1824.
Yoshinaga T, Xu J, Inoue K. A note on closure property of sublogarithmic space-bounded 1-inkdot alternating Turing machines with only existential (universal) states. Research Reports of the Tokuyama College of Technology, 2003, 27: 7–11.
Inoue K, Ito A, Takanami I, Yoshinaga T. A note on multi-inkdot nondeterministic Turing machines with small space. Information Processing Letters, 1993, 48: 285–288.
Author information
Authors and Affiliations
Corresponding author
Additional information
This work is supported by the National Natural Science Foundation of China under Grant No. 60403012.
Rights and permissions
About this article
Cite this article
Xu, JL., Liu, YX. & Yoshinaga, T. A Note on Non-Closure Property of Sublogarithmic Space-Bounded 1-Inkdot Alternating Pushdown Automata with Only Existential (Universal) States. J Comput Sci Technol 21, 979–983 (2006). https://doi.org/10.1007/s11390-006-0979-7
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/s11390-006-0979-7