Extending regular expressions with iterated shuffle. (English) Zbl 0574.68069

By using the result operations (union, product, and star), the shuffle operation {Russian{Sh}}, and its closure, the iterated shuffle \(†\), the three slip-families \(Shuf:=(v,\text{Russian{Sh}},†)(Fin)\), \(ER:=(v,\cdot,*,†)(Fin)\) and \(SE:=(v,\cdot,*,\text{Russian{Sh}},†)(Fin)\) are studied. While there exists a simple one-counter language L, whose iterated shuffle \(L^{†}\) is an NP-complete set [M. K. Warmuth and D. Haussler, J. Comput. Syst. Sci. 28, 345-358 (1984; Zbl 0549.68039)], it is here shown that the family ER defines only sets that are acceptable by some multicounter language in quasi-realtime, thus are acceptable in nondeterministic logarithmic space and consequently are in P. The result obtained corrects Corollary 3.11 in the author’s paper in Theor. Comput. Sci. 14, 127-154 (1981; Zbl 0477.68034), generalizes Theorem 5.1 in the paper of Warmuth and Haussler (loc. cit.), and adds to the research by Shaw, Riddle, Kimura, Araki and Tokura, Slutzki, and others.


68Q45 Formal languages and automata
68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
Full Text: DOI


[1] Araki, T.; Kagimasa, T.; Tokura, N., Relations of flow languages to Petri net languages, Theoret. comput. sci., 15, 51-75, (1981) · Zbl 0473.68075
[2] Araki, T.; Tokura, N., Flow languages equal recursively enumerable languages, Acta inform., 15, 209-217, (1981) · Zbl 0456.68093
[3] Berstel, J., Transductions and context-free languages, (1979), Teubner Stuttgart · Zbl 0424.68040
[4] Czaja, L., Parallel systems schemas and their relation to automata, Inform. process. lett., 10, 153-158, (1980) · Zbl 0442.68056
[5] Eilenberg, S.; Schützenberger, M.P., Rational sets in commutative monoids, J. algebra, 13, 173-191, (1969) · Zbl 0206.02703
[6] Ginsburg, S., Algebraic and automata-theoretic properties of formal languages, (1975), North-Holland Amsterdam · Zbl 0325.68002
[7] Gisher, J., Shuffle languages, Petri nets, and context-sensitive grammars, Comm. ACM, 24, 597-605, (1981) · Zbl 0471.68063
[8] Greibach, S.A., Remarks on blind and partially blind one-way multicounter machines, Theoret. comput. sci., 7, 311-324, (1978) · Zbl 0389.68030
[9] Hack, M., Petri net languages, ()
[10] Haussler, D.; Zeiger, H.P., Very special languages and representations of recursively enumerable languages via computation histories, Inform. control, 47, 201-212, (1980) · Zbl 0457.68086
[11] Jantzen, M., On the hierarchy of Petri net languages, R.A.I.R.O., Inform. théor., 13, 19-30, (1979) · Zbl 0404.68076
[12] Jantzen, M., Eigenschaften von petrinetzsprachen, ()
[13] Jantzen, M., On zerotesting—bounded multicounter machines, (), 158-169 · Zbl 0411.68070
[14] Jantzen, M., The power of synchronizing operations on strings, Theoret. comput. sci., 14, 127-154, (1981) · Zbl 0477.68034
[15] Jantzen, M., Extending regular expressions with iterated shuffle, Tech. rept., FB-informatik, univ. Hamburg, IFI-HH-B-99/84, (1984) · Zbl 0574.68069
[16] Jedrzejowicz, J., On the enlargement of the class of regular languages by the shuffle closure, Inform. process. lett., 16, 51-54, (1983) · Zbl 0555.68043
[17] Kimura, T., An algebraic system for process structuring and interprocess communication, (), 92-100
[18] Kimura, T., Formal description of communication behaviour, ()
[19] Ogden, W.F.; Riddle, W.E.; Rounds, W.C., Complexity of expressions allowing concurrency, (), 185-194
[20] Riddle, W.E., Modelling and analysis of supervisor systems, ()
[21] Riddle, W.E., Software systems modelling and analysis, () · Zbl 0408.68031
[22] Shaw, A.C., Systems design and documentation using path descriptions, (), 180-181
[23] Shaw, A.C., Software description with flow expressions, IEEE trans. software engrg., 3, 4, 242-254, (1978) · Zbl 0381.68035
[24] Slutzki, G., Non-sychronizing concurrent processes and their languages, (1979), Dept. of Computer and Information Sciences, Univ. of Delaware Newark, unpublished manuscript
[25] Slutzki, G., Descriptional complexity of concurrent processes, (), 601-611
[26] Warmuth, M.K.; Haussler, D., On the complexity of iterated shuffle, J. comput. syst. sci., 28, 345-358, (1984) · Zbl 0549.68039
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.