Shuffle languages are in P. (English) Zbl 0952.68079

In this paper we show that shuffle languages are contained in one-way-NSPACE\((\log n)\) thus in P. We consider the class of shuffle languages which emerges from the class of finite languages through regular operations (union, concatenation, Kleene star) and shuffle operations (shuffle and shuffle closure). For every shuffle expression \(E\) we construct a shuffle automaton which accepts the language generated by \(E\) and we show that the automaton can be simulated by a one-way nondeterministic Turing machine in logarithmic space.


68Q45 Formal languages and automata
Full Text: DOI


[1] Garg, V.K.; Ragunath, M.T., Concurrent regular expressions and their relationship to Petri nets, Theoret. comput. sci., 96, 285-304, (1992) · Zbl 0745.68080
[2] Gischer, J.L., Shuffle languages, Petri nets and context sensitive grammars, Commun. ACM, 1981, (1924)
[3] Hopcroft, J.E.; Ullman, J.D., Introduction to automata theory, languages and computation, (1979), Addison-Wesley Reading, MA · Zbl 0196.01701
[4] Jantzen, M., The power of synchronizing operations on strings, Theoret. comput. sci., 14, 127-154, (1981) · Zbl 0477.68034
[5] Jantzen, M., Extending regular operations with iterated shuffle, Theoret. comput. sci., 38, 223-247, (1985) · Zbl 0574.68069
[6] Jȩdrzejowicz, J., On the enlargement of the class of regular languages by shuffle closure, Inform. process. lett., 16, 51-54, (1983) · Zbl 0555.68043
[7] Jȩdrzejowicz, J., Nesting of shuffle closure is important, Inform. process. lett., 25, 363-367, (1987) · Zbl 0633.68070
[8] J. Jȩdrzejowicz, Shuffle Operation in Formal Languages, Wydawnictwo Uniwersytetu Gdanskiego, 1996.
[9] Mayer, A.J.; Stockmeyer, L.J., The complexity of word problems – this time with interleaving, Inform. comput., 115, 293-311, (1994)
[10] W.F. Ogden, W.E. Riddle, C. Rounds, Complexity of expressions allowing concurrency, in: Proc. 5th Ann ACM Symp. on Principles of Programming Languages, 1978, pp. 185-194.
[11] Riddle, W.E., Software system modelling and analysis, tech. report, dept. of computer and communication sciences, (1976), Univ. of Michigan RSSM25
[12] A.C. Shaw, Software descriptions with flow expressions, IEEE Trans. Software Eng. SE-4 (1978) 242-254. · Zbl 0381.68035
[13] Warmuth, M.K.; Haussler, D., On the complexity of iterated shuffle, J. Comput. Systems Sci., 1984, (1928)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.