Lower Space Bounds for Accepting Shuffle Languages
RAIRO - Theoretical Informatics and Applications (2010)
- Volume: 33, Issue: 3, page 303-307
- ISSN: 0988-3754
Access Full Article
top
Abstract
topHow to cite
topSzepietowski, 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- J.L. Gischer, Shuffle languages, Petri nets and context sensitive grammars. Comm. ACM24 (1981) 597-605.
- J.E. Hopcroft and J.D. Ullman, Introduction to Automata Theory, Languages andComputation, Addison-Wesley, Reading MA (1979).
- M. Jantzen, Extending regular operations with iterated shuffle. TCS38 (1985) 223-247.
- J. Jedrzejowicz, On the enlargement of the class of regular languages by shuffle closure. IPL16 (1983) 51-54.
- J. Jedrzejowicz, Nesting of shuffle closure is important. IPL25 (1987) 363-367.
- 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.
- W.E. Riddle, Software system modelling and analysis, Tech. Report, Dept. of Computer and Communication Sciences, University of Michigan RSSM25 (1976).
- A.C. Shaw, Software descriptions with flow expressions. IEEE Trans. Software EngrgSE-4 (1978) 242-254.
- A. Szepietowski, Turing Machines with Sublogarithmic Space, LNCS 843, Springer-Verlag, Berlin (1994).
- M.K. Warmuth and D. Haussler, On the complexity of iterated shuffle. J. CSS28 (1984) 345-358.
NotesEmbed ?
topYou 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.