Shuffle languages are in P (Q1589415): Difference between revisions

From MaRDI portal
ReferenceBot (talk | contribs)
Changed an Item
Created claim: Wikidata QID (P12): Q127186276, #quickstatements; #temporary_batch_1722518518227
 
Property / Wikidata QID
 
Property / Wikidata QID: Q127186276 / rank
 
Normal rank

Latest revision as of 14:23, 1 August 2024

scientific article
Language Label Description Also known as
English
Shuffle languages are in P
scientific article

    Statements

    Shuffle languages are in P (English)
    0 references
    12 December 2000
    0 references
    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.
    0 references
    complexity
    0 references
    polynomial-time complexity
    0 references
    shuffle languages
    0 references
    shuffle
    0 references
    automata
    0 references

    Identifiers