# 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

## Access Full Article

top## Abstract

top## How to cite

topGeffert, 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- M. Alberts, Space complexity of alternating Turing machines, in Proc. Fund. Comput. Theory. Springer-Verlag, Lecture Notes in Comput. Sci. 199 (1985) 1-7. Zbl0574.68040
- H. Alt and K. Mehlhorn, A language over a one symbol alphabet requiring only O(log log n) space. SIGACT News7 (1975) 31-33.
- 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. Zbl1193.68119
- A. Bertoni, C. Mereghetti and G. Pighizzini, Space and reversal complexity of nonregular languages. Technical Report, University of Milano (1998). Zbl0810.68089
- A.K. Chandra, D.C. Kozen and L.J. Stockmeyer, Alternation. J. Assoc. Comput. Math.28 (1981) 114-33.
- P. van Emde Boas, Machine models and simulations, edited by J. van Leeuwen, Handbook of Theoretical Computer Science. Elsevier Science (1989). Zbl0900.68265
- R. Freivalds, On the work time of deterministic and nondeterministic Turing machines. Latv. Mat. Ezhegodnik 23 (1979) 158-65 (in Russian). Zbl0462.68028
- V. Geffert, Nondeterministic computations in sublogarithmic space and space constructibility. SIAM J. Comput.20 (1991) 484-98. Zbl0762.68022
- V. Geffert, A hierarchy that does not collapse: Alternations in low level space. RAIRO: Theoret. Informatics Appl.28 (1994) 465-512. Zbl0884.68054
- V. Geffert, C. Mereghetti and G. Pighizzini, Sublogarithmic bounds on space and reversals. SIAM J. Comput.28 (1999) 325-40. Zbl0914.68068
- 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.
- 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.
- J.E. Hopcroft and J.D. Ullman, Some results on tape-bounded Turing machines. J. Assoc. Comput. Mach.16 (1969) 168-77. Zbl0188.33501
- J. Hromkovic, B. Rovan and A. Slobodová, Deterministic versus nondeterministic space in terms of synchronized alternating machines. Theoret. Comput. Sci.132 (1994) 319-36. Zbl0821.68056
- K. Iwama, ASPACE o(log log n) is regular. SIAM J. Comput.22 (1993) 136-46.
- B.E. Ladner, R.J. Lipton and L.R. Stockmeyer, Alternation bounded auxiliary pushdown automata. Inform. and Control62 (1984) 93-108. Zbl0589.68058
- C. Mereghetti and G. Pighizzini, A remark on middle space bounded alternating Turing machines. Inform. Process. Lett.56 (1995) 229-32. Zbl0875.68395
- 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.). Zbl0980.68048
- W.J. Savitch, Relationships between nondeterministic and deterministic tape complexities. J. Comput. System Sci.4 (1970) 177-92. Zbl0188.33502
- 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.
- A. Szepietowski, Remarks on languages acceptable in log log n space. Inform. Process Lett.27 (1988) 201-3. Zbl0652.68055

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.