Lower Space Bounds for Accepting Shuffle Languages

Andrzej Szepietowski

RAIRO - Theoretical Informatics and Applications (2010)

  • Volume: 33, Issue: 3, page 303-307
  • ISSN: 0988-3754

Abstract

top
In [6] it was shown that shuffle languages are contained in one-way-NSPACE(log n) and in P. In this paper we show that nondeterministic one-way logarithmic space is in some sense the lower bound for accepting shuffle languages. Namely, we show that there exists a shuffle language which is not accepted by any deterministic one-way Turing machine with space bounded by a sublinear function, and that there exists a shuffle language which is not accepted with less than logarithmic space even if we allow two-way nondeterministic Turing machines.

How to cite

top

Szepietowski, Andrzej. "Lower Space Bounds for Accepting Shuffle Languages." RAIRO - Theoretical Informatics and Applications 33.3 (2010): 303-307. <http://eudml.org/doc/222065>.

@article{Szepietowski2010,
abstract = { In [6] it was shown that shuffle languages are contained in one-way-NSPACE(log n) and in P. In this paper we show that nondeterministic one-way logarithmic space is in some sense the lower bound for accepting shuffle languages. Namely, we show that there exists a shuffle language which is not accepted by any deterministic one-way Turing machine with space bounded by a sublinear function, and that there exists a shuffle language which is not accepted with less than logarithmic space even if we allow two-way nondeterministic Turing machines. },
author = {Szepietowski, Andrzej},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {shuffle languages},
language = {eng},
month = {3},
number = {3},
pages = {303-307},
publisher = {EDP Sciences},
title = {Lower Space Bounds for Accepting Shuffle Languages},
url = {http://eudml.org/doc/222065},
volume = {33},
year = {2010},
}

TY - JOUR
AU - Szepietowski, Andrzej
TI - Lower Space Bounds for Accepting Shuffle Languages
JO - RAIRO - Theoretical Informatics and Applications
DA - 2010/3//
PB - EDP Sciences
VL - 33
IS - 3
SP - 303
EP - 307
AB - In [6] it was shown that shuffle languages are contained in one-way-NSPACE(log n) and in P. In this paper we show that nondeterministic one-way logarithmic space is in some sense the lower bound for accepting shuffle languages. Namely, we show that there exists a shuffle language which is not accepted by any deterministic one-way Turing machine with space bounded by a sublinear function, and that there exists a shuffle language which is not accepted with less than logarithmic space even if we allow two-way nondeterministic Turing machines.
LA - eng
KW - shuffle languages
UR - http://eudml.org/doc/222065
ER -

References

top
  1. J.L. Gischer, Shuffle languages, Petri nets and context sensitive grammars. Comm. ACM24 (1981) 597-605.  Zbl0471.68063
  2. J.E. Hopcroft and J.D. Ullman, Introduction to Automata Theory, Languages andComputation, Addison-Wesley, Reading MA (1979).  Zbl0426.68001
  3. M. Jantzen, Extending regular operations with iterated shuffle. TCS38 (1985) 223-247.  Zbl0574.68069
  4. J. Jedrzejowicz, On the enlargement of the class of regular languages by shuffle closure. IPL16 (1983) 51-54.  Zbl0555.68043
  5. J. Jedrzejowicz, Nesting of shuffle closure is important. IPL25 (1987) 363-367.  Zbl0633.68070
  6. J. Jedrzejowicz and A. Szepietowski, Shuffle languages are inP, Preprint No. 124, Mathematical Institute, University of Gdansk, ul. Wita Stwosza 57, 80-952 Gdansk, Poland, March 1997, Theoret. Comput. Sci., accepted.  
  7. W.E. Riddle, Software system modelling and analysis, Tech. Report, Dept. of Computer and Communication Sciences, University of Michigan RSSM25 (1976).  
  8. A.C. Shaw, Software descriptions with flow expressions. IEEE Trans. Software EngrgSE-4 (1978) 242-254.  Zbl0381.68035
  9. A. Szepietowski, Turing Machines with Sublogarithmic Space, LNCS 843, Springer-Verlag, Berlin (1994).  Zbl0998.68062
  10. M.K. Warmuth and D. Haussler, On the complexity of iterated shuffle. J. CSS28 (1984) 345-358.  Zbl0549.68039

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.