@article{ITA_1999__33_3_303_0, author = {Szepietowski, Andrzej}, title = {Lower space bounds for accepting shuffle languages}, journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications}, pages = {303--307}, publisher = {EDP-Sciences}, volume = {33}, number = {3}, year = {1999}, mrnumber = {1728429}, zbl = {0951.68067}, language = {en}, url = {http://www.numdam.org/item/ITA_1999__33_3_303_0/} }
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 SP - 303 EP - 307 VL - 33 IS - 3 PB - EDP-Sciences UR - http://www.numdam.org/item/ITA_1999__33_3_303_0/ LA - en ID - ITA_1999__33_3_303_0 ER -
%0 Journal Article %A Szepietowski, Andrzej %T Lower space bounds for accepting shuffle languages %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 1999 %P 303-307 %V 33 %N 3 %I EDP-Sciences %U http://www.numdam.org/item/ITA_1999__33_3_303_0/ %G en %F ITA_1999__33_3_303_0
Szepietowski, Andrzej. Lower space bounds for accepting shuffle languages. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 33 (1999) no. 3, pp. 303-307. http://www.numdam.org/item/ITA_1999__33_3_303_0/
[1] Shuffle languages, Petri nets and context sensitive grammars. Comm. ACM 24 (1981) 597-605. | MR | Zbl
,[2] Introduction to Automata Theory, Languages and Computation, Addison-Wesley, Reading MA (1979). | MR | Zbl
and ,[3] Extending regular operations with iterated shuffle. TCS 38 (1985) 223-247. | MR | Zbl
,[4] On the enlargement of the class of regular languages by shuffle closure. IPL 16 (1983) 51-54. | MR | Zbl
,[5] Nesting of shuffle closure is important. IPL 25 (1987) 363-367. | MR | Zbl
,[6] 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. | MR | Zbl
, and ,[7] Software System modelling and analysis, Tech. Report, Dept. of Computer and Communication Sciences, University of Michigan RSSM25 (1976).
,[8] Software descriptions with flow expressions. IEEE Trans. Software Engrg SE-4 (1978) 242-254. | Zbl
,[9] Turing Machines with Sublogarithmic Space, LNCS 843, Springer-Verlag, Berlin (1994). | MR | Zbl
,[10] On the complexity of iterated shuffle. J. CSS 28 (1984) 345-358. | MR | Zbl
and ,