A Space Lower Bound for Acceptance by One-Way Π2-Alternating Machines

Viliam Geffert; Norbert Popély

RAIRO - Theoretical Informatics and Applications (2010)

  • Volume: 34, Issue: 5, page 357-372
  • ISSN: 0988-3754

Abstract

top
We show that one-way Π2-alternating Turing machines cannot accept unary nonregular languages in o(log n) space. This holds for an accept mode of space complexity measure, defined as the worst cost of any accepting computation. This lower bound should be compared with the corresponding bound for one-way Σ2-alternating machines, that are able to accept unary nonregular languages in space O(log log n). Thus, Σ2-alternation is more powerful than Π2-alternation for space bounded one-way machines with unary inputs.

How to cite

top

Geffert, Viliam, and Popély, Norbert. " A Space Lower Bound for Acceptance by One-Way Π2-Alternating Machines." RAIRO - Theoretical Informatics and Applications 34.5 (2010): 357-372. <http://eudml.org/doc/222025>.

@article{Geffert2010,
abstract = { We show that one-way Π2-alternating Turing machines cannot accept unary nonregular languages in o(log n) space. This holds for an accept mode of space complexity measure, defined as the worst cost of any accepting computation. This lower bound should be compared with the corresponding bound for one-way Σ2-alternating machines, that are able to accept unary nonregular languages in space O(log log n). Thus, Σ2-alternation is more powerful than Π2-alternation for space bounded one-way machines with unary inputs. },
author = {Geffert, Viliam, Popély, Norbert},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Alternation; lower bounds; nonregular languages; space complexity; Turing machine.; -alternating Turing machines},
language = {eng},
month = {3},
number = {5},
pages = {357-372},
publisher = {EDP Sciences},
title = { A Space Lower Bound for Acceptance by One-Way Π2-Alternating Machines},
url = {http://eudml.org/doc/222025},
volume = {34},
year = {2010},
}

TY - JOUR
AU - Geffert, Viliam
AU - Popély, Norbert
TI - A Space Lower Bound for Acceptance by One-Way Π2-Alternating Machines
JO - RAIRO - Theoretical Informatics and Applications
DA - 2010/3//
PB - EDP Sciences
VL - 34
IS - 5
SP - 357
EP - 372
AB - We show that one-way Π2-alternating Turing machines cannot accept unary nonregular languages in o(log n) space. This holds for an accept mode of space complexity measure, defined as the worst cost of any accepting computation. This lower bound should be compared with the corresponding bound for one-way Σ2-alternating machines, that are able to accept unary nonregular languages in space O(log log n). Thus, Σ2-alternation is more powerful than Π2-alternation for space bounded one-way machines with unary inputs.
LA - eng
KW - Alternation; lower bounds; nonregular languages; space complexity; Turing machine.; -alternating Turing machines
UR - http://eudml.org/doc/222025
ER -

References

top
  1. M. Alberts, Space complexity of alternating Turing machines, in Proc. Fund. Comput. Theory. Springer-Verlag, Lecture Notes in Comput. Sci. 199 (1985) 1-7.  
  2. H. Alt and K. Mehlhorn, A language over a one symbol alphabet requiring only O(log log n) space. SIGACT News7 (1975) 31-33.  
  3. A. Bertoni, C. Mereghetti and G. Pighizzini, Strong optimal lower bounds for Turing machines that accept nonregular languages, in Proc. Math. Found. Comput. Sci. Springer-Verlag, Lecture Notes in Comput. Sci. 969 (1995) 309-18.  
  4. A. Bertoni, C. Mereghetti and G. Pighizzini, Space and reversal complexity of nonregular languages. Technical Report, University of Milano (1998).  
  5. A.K. Chandra, D.C. Kozen and L.J. Stockmeyer, Alternation. J. Assoc. Comput. Math.28 (1981) 114-33.  
  6. P. van Emde Boas, Machine models and simulations, edited by J. van Leeuwen, Handbook of Theoretical Computer Science. Elsevier Science (1989).  
  7. R. Freivalds, On the work time of deterministic and nondeterministic Turing machines. Latv. Mat. Ezhegodnik 23 (1979) 158-65 (in Russian).  
  8. V. Geffert, Nondeterministic computations in sublogarithmic space and space constructibility. SIAM J. Comput.20 (1991) 484-98.  
  9. V. Geffert, A hierarchy that does not collapse: Alternations in low level space. RAIRO: Theoret. Informatics Appl.28 (1994) 465-512.  
  10. V. Geffert, C. Mereghetti and G. Pighizzini, Sublogarithmic bounds on space and reversals. SIAM J. Comput.28 (1999) 325-40.  
  11. J. Hartmanis, P.M. Lewis II and R.E. Stearns, Hierarchies of memory limited computations, in IEEE Conf. Record on Switching Circuit Theory and Logical Design (1965) 179-90.  
  12. J. Hartmanis, P.M. Lewis II and R.E. Stearns, Memory bounds for recognition of context-free and context-sensitive languages, in IEEE Conf. Record on Switching Circuit Theory and Logical Design (1965) 191-202.  
  13. J.E. Hopcroft and J.D. Ullman, Some results on tape-bounded Turing machines. J. Assoc. Comput. Mach.16 (1969) 168-77.  
  14. J. Hromkovic, B. Rovan and A. Slobodová, Deterministic versus nondeterministic space in terms of synchronized alternating machines. Theoret. Comput. Sci.132 (1994) 319-36.  
  15. K. Iwama, ASPACE o(log log n) is regular. SIAM J. Comput.22 (1993) 136-46.  
  16. B.E. Ladner, R.J. Lipton and L.R. Stockmeyer, Alternation bounded auxiliary pushdown automata. Inform. and Control62 (1984) 93-108.  
  17. C. Mereghetti and G. Pighizzini, A remark on middle space bounded alternating Turing machines. Inform. Process. Lett.56 (1995) 229-32.  
  18. C. Mereghetti and G. Pighizzini, Optimal simulations between unary automata, in Proc. Symp. Theoret. Aspects Comput. Sci. Springer-Verlag, Lecture Notes in Comput. Sci. 1373 (1998) 139-149 (to appear in SIAM J. Comput.).  
  19. W.J. Savitch, Relationships between nondeterministic and deterministic tape complexities. J. Comput. System Sci.4 (1970) 177-92.  
  20. I.H. Sudborough, Efficient algorithms for path system problems and applications to alternating and time-space complexity classes, in Proc. IEEE Symp. Found. of Comput. Sci. (1980) 62-73.  
  21. A. Szepietowski, Remarks on languages acceptable in log log n space. Inform. Process Lett.27 (1988) 201-3.  

NotesEmbed ?

top

You must be logged in to post comments.