Class ShuffleOperations


  • public final class ShuffleOperations
    extends java.lang.Object
    Automata operations involving shuffling.
    • Method Summary

      All Methods Static Methods Concrete Methods 
      Modifier and Type Method Description
      static Automaton shuffle​(Automaton a1, Automaton a2)
      Returns an automaton that accepts the shuffle (interleaving) of the languages of the given automata.
      static java.lang.String shuffleSubsetOf​(java.util.Collection<Automaton> ca, Automaton a, java.lang.Character suspend_shuffle, java.lang.Character resume_shuffle)
      Returns a string that is an interleaving of strings that are accepted by ca but not by a.
      • Methods inherited from class java.lang.Object

        clone, equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Method Detail

      • shuffle

        public static Automaton shuffle​(Automaton a1,
                                        Automaton a2)
        Returns an automaton that accepts the shuffle (interleaving) of the languages of the given automata. As a side-effect, both automata are determinized, if not already deterministic. Never modifies the input automata languages.

        Complexity: quadratic in number of states (if already deterministic).

        Author:
        Torben Ruby <ruby@daimi.au.dk>
      • shuffleSubsetOf

        public static java.lang.String shuffleSubsetOf​(java.util.Collection<Automaton> ca,
                                                       Automaton a,
                                                       java.lang.Character suspend_shuffle,
                                                       java.lang.Character resume_shuffle)
        Returns a string that is an interleaving of strings that are accepted by ca but not by a. If no such string exists, null is returned. As a side-effect, a is determinized, if not already deterministic. Only interleavings that respect the suspend/resume markers (two BMP private code points) are considered if the markers are non-null. Also, interleavings never split surrogate pairs.

        Complexity: proportional to the product of the numbers of states (if a is already deterministic).