Lower space bounds for accepting shuffle languages

Andrzej Szepietowski

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1999)

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

How to cite

top

Szepietowski, Andrzej. "Lower space bounds for accepting shuffle languages." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 33.3 (1999): 303-307. <http://eudml.org/doc/92605>.

@article{Szepietowski1999,
author = {Szepietowski, Andrzej},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {shuffle languages},
language = {eng},
number = {3},
pages = {303-307},
publisher = {EDP-Sciences},
title = {Lower space bounds for accepting shuffle languages},
url = {http://eudml.org/doc/92605},
volume = {33},
year = {1999},
}

TY - JOUR
AU - Szepietowski, Andrzej
TI - Lower space bounds for accepting shuffle languages
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 1999
PB - EDP-Sciences
VL - 33
IS - 3
SP - 303
EP - 307
LA - eng
KW - shuffle languages
UR - http://eudml.org/doc/92605
ER -

References

top
  1. [1] J. L. Gischer, Shuffle languages, Petri nets and context sensitive grammars. Comm. ACM 24 (1981) 597-605. Zbl0471.68063MR628195
  2. [2] J. E. Hopcroft and J. D. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley, Reading MA (1979). Zbl0426.68001MR645539
  3. [3] M. Jantzen, Extending regular operations with iterated shuffle. TCS 38 (1985) 223-247. Zbl0574.68069MR807924
  4. [4] J. Jędrzejowicz, On the enlargement of the class of regular languages by shuffle closure. IPL 16 (1983) 51-54. Zbl0555.68043MR696841
  5. [5] J. Jędrzejowicz, Nesting of shuffle closure is important. IPL 25 (1987) 363-367. Zbl0633.68070MR905780
  6. [6] J. Jędrzejowicz, and A. Szepietowski, Shuffle languages are in P, Preprint No. 124, Mathematical Institute, University of Gdańsk, ul. Wita Stwosza 57, 80-952 Gdańsk, Poland, March 1997, Theoret. Comput. Sci., accepted. Zbl0952.68079MR1795235
  7. [7] W.E. Riddle, Software System modelling and analysis, Tech. Report, Dept. of Computer and Communication Sciences, University of Michigan RSSM25 (1976). 
  8. [8] A.C. Shaw, Software descriptions with flow expressions. IEEE Trans. Software Engrg SE-4 (1978) 242-254. Zbl0381.68035
  9. [9] A. Szepietowski, Turing Machines with Sublogarithmic Space, LNCS 843, Springer-Verlag, Berlin (1994). Zbl0998.68062MR1314820
  10. [10] M.K. Warmuth and D. Haussler, On the complexity of iterated shuffle. J. CSS 28 (1984) 345-358. Zbl0549.68039MR752437

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.