Skip to content

MultisetSubstitutionSystem.md

Latest commit

 

History

History
77 lines (63 loc) · 4.39 KB

MultisetSubstitutionSystem.md

File metadata and controls

77 lines (63 loc) · 4.39 KB
Raw

MultisetSubstitutionSystem

States of the MultisetSubstitutionSystem are unordered multisets of tokens, which are arbitrary Wolfram Language expressions. Events take submultisets of these and replace them with other multisets. SubsetReplace evaluates this system, for example.

The left-hand sides of rules are written as Wolfram Language patterns. The first level of these patterns should match to a List, and is matched to a multiset of tokens, so {n__Integer, s_String} and {s_String, n__Integer} are equivalent aside from their effect on the event ordering and can match, e.g., {1, 2, "s"}, {2, "x", 3} and {"q", 1}.

The right-hand sides determine the result of the replacement similar to Replace. The top level of the output must be a List, and it is converted to a multiset of tokens to be inserted into the output state.

For example, to make a system that adds pairs of numbers:

In[] := #["ExpressionsEventsGraph", VertexLabels -> Placed[Automatic, After]] & @
  SetReplaceTypeConvert[{WolframModelEvolutionObject, 2}] @
    GenerateMultihistory[MultisetSubstitutionSystem[{a_, b_} /; a < b :> {a + b}],
                         {"MaxDestroyerEvents" -> 1, "MaxEventInputs" -> 2},
                         None,
                         EventOrderingFunctions[MultisetSubstitutionSystem],
                         {}] @ {1, 2, 3, 4}

Arbitrary Wolfram Language patterns are supported including conditions such as {a_ /; a > 0, b_} and {a_, b_} /; a + b == 3 and sequences that match multiple tokens at once in any order, e.g., {a__}. Any code is supported on the right-hand side as long as it always generates a list. For example:

In[] := #["ExpressionsEventsGraph", VertexLabels -> Placed[Automatic, After]] & @
  SetReplaceTypeConvert[{WolframModelEvolutionObject, 2}] @
    GenerateMultihistory[
      MultisetSubstitutionSystem[{a__} /; OrderedQ[{a}] && PrimeQ[Plus[a]] :> First /@ FactorInteger[Plus[a]]],
      {"MinEventInputs" -> 2, "MaxEventInputs" -> 4},
      None,
      EventOrderingFunctions[MultisetSubstitutionSystem],
      {}] @ {1, 2, 3, 4}

Note, however, that the system cannot recognize if the code on the right-hand side is nondeterministic, so only the first output will be used for each assignment of pattern variables.

MultisetSubstitutionSystem supports "MaxGeneration", "MaxDestroyerEvents", "MinEventInputs" and "MaxEventInputs" for event selection. It supports "MaxEvents" as a stopping condition. Only a single event ordering {"InputCount", "SortedInputTokenIndices", "InputTokenIndices", "RuleIndex", "InstantiationIndex"} is implemented at the moment.

MultisetSubstitutionSystem produces {MultisetSubstitutionSystem, 0} objects.

Current Limitations

  • The current version does no introspection of the rules, so it is slow since it has to enumerate all subsets of tokens in the multihistory for every new event. "MaxEventInputs" can be used as a workaround.
  • Token deduplication is not implemented. The only value supported is None.
  • Only {"InputCount", "SortedInputTokenIndices", "InputTokenIndices", "RuleIndex", "InstantiationIndex"} is implemented for event ordering.