Shuffle languages are in P

✍ Scribed by Joanna Jȩdrzejowicz; Andrzej Szepietowski

• Book ID: 104326779
• Publisher: Elsevier Science
• Year: 2001
• Tongue: English
• Weight: 226 KB
• Volume: 250
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(99)00109-7

✦ Synopsis

In this paper we show that shu e languages are contained in one-way-NSPACE(log n) thus in P. We consider the class of shu e languages which emerges from the class of ÿnite languages through regular operations (union, concatenation, Kleene star) and shu e operations (shu e and shu e closure). For every shu e expression E we construct a shu e 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.