@article{Jantzen:TCS:1985,
    Abstract = {It is shown that every finite expression which uses the operations union, product, Kleene star, and iterated shuffle in any order, starting with finite sets, defines a language which can be recognized non-deterministically by some multicounter machine in quasirealtime. It is known that this family is in general not closed with respect to iterated shuffle. As a consequence of the characterization each such language is in NSPACE(log n) and thus in P. However, if P ≠ NP, then also neither P nor NSPACE(log n) are closed under iterated shuffle. The proof uses the new concept of so-called shuffle schemes and a number of results on algebraic language theory.},
    Author = {Jantzen, Matthias},
    File = {Extending regular expressions with iterated shuffle - 1-s2.0-030439758590221X-main - a - k.pdf},
    ISSN = {0304-3975},
    Journal = {Theoretical Computer Science},
    Pages = {223--247},
    Title = {Extending regular expressions with iterated shuffle},
    URL = {http://www.sciencedirect.com/science/article/pii/030439758590221X},
    Volume = {38},
    Year = {1985},
    bdsk-url-1 = {http://www.sciencedirect.com/science/article/pii/030439758590221X},
    bdsk-url-2 = {https://doi.org/10.1016/0304-3975(85)90221-X},
    date-added = {2020-10-23 16:36:05 +0200},
    date-modified = {2020-10-23 16:36:05 +0200},
    doi = {10.1016/0304-3975(85)90221-X}
}

@article{Jantzen:TCS:1985, Abstract = {It is shown that every finite expression which uses the operations union, product, Kleene star, and iterated shuffle in any order, starting with finite sets, defines a language which can be recognized non-deterministically by some multicounter machine in quasirealtime. It is known that this family is in general not closed with respect to iterated shuffle. As a consequence of the characterization each such language is in NSPACE(log n) and thus in P. However, if P ≠ NP, then also neither P nor NSPACE(log n) are closed under iterated shuffle. The proof uses the new concept of so-called shuffle schemes and a number of results on algebraic language theory.}, Author = {Jantzen, Matthias}, File = {Extending regular expressions with iterated shuffle - 1-s2.0-030439758590221X-main - a - k.pdf}, ISSN = {0304-3975}, Journal = {Theoretical Computer Science}, Pages = {223--247}, Title = {Extending regular expressions with iterated shuffle}, URL = {http://www.sciencedirect.com/science/article/pii/030439758590221X}, Volume = {38}, Year = {1985}, bdsk-url-1 = {http://www.sciencedirect.com/science/article/pii/030439758590221X}, bdsk-url-2 = {https://doi.org/10.1016/0304-3975(85)90221-X}, date-added = {2020-10-23 16:36:05 +0200}, date-modified = {2020-10-23 16:36:05 +0200}, doi = {10.1016/0304-3975(85)90221-X} }