Flat Matching

Temur Kutsia

Research Institute for Symbolic Computation (RISC)
Johannes Kepler University Linz
A-4232 Castle of Hagenberg
Austria

kutsia@risc.uni-linz.ac.at

This is a companion notebook to the paper:
	Temur Kutsia. Flat Matching. http://www.risc.jku.at/people/tkutsia/papers/Kutsia_JSC_2008.pdf.
The notebook contains implementation of the flat matching procedure 𝔉 and the flat matching algorithms  (Subscript[𝔉, NE]) and  (Subscript[𝔉, Mma]) from the paper and, in addition, the algorithm  (Subscript[𝔉, FR]) that computes a finite representation of the solution set in the form of regular expressions over substiutions. Sequence variables are represented as •var[•seq[varname]] and individual and function variables are represented as •var[varname]. The goal was to provide a test implementation for experiments. Efficiency was not an issue.

In the examples part, the fourth problem in each example demonstrates how substitutions for Mathematica flat matching have been computed in Example 10 in the paper. The patterns x_ and y_  correspond respectively to the individual variables x and y in the paper,  the pattern y___ corresponds to the sequence variable y, and the pattern F_ corresponds to the function variable F. Comparing outputs on these problems to those called with the option Modification->Mma (i.e.to the implementation of (Subscript[𝔉, Mma])), one can see how the behaviour of Mathematica’s flat matching is imitated by (Subscript[𝔉, Mma]).

The code has been tested on  Mathematica 5.2 and Mathematica 6.0. Initial version from April 18, 2008.

Version 0.1 from June 23, 2013: Fixed a bug related to multiple occurrences of function variables, when matching to a flat function symbol with the option Modification->Mma. The version has been tested on Mathematica 9.0.

Main Function: MatchFlat

MatchFlat imposes control on application of  matching rules. When the option NE is set to False (default),  MatchFlat corresponds to the flat matching procedure  𝔉 in the paper. When  the value of NE is True, then  MatchFlat corresponds to  (Subscript[𝔉, NE]). Search is conducted in the breadth-first manner.

Possible values of the options: FlatSymbols -> L where L is a list of function symbols, SearchDepth -> Integer, Verbose -> True or False, Modification -> None (corresponds to  𝔉 ), NE (corresponds to  (Subscript[𝔉, NE])),  Mma  (corresponds to  (Subscript[𝔉, Mma]) ) and FR (finite representation of an infinite minimal complete set of matchers)

Options[MatchFlat]={FlatSymbols->{},SearchDepth->60, Verbose->False, Modification->None};
Clear[MatchFlat];
MatchFlat[patt_≪data_,opt___]:=Module[{flatteningRules,multiSetOfMatchingProblems,solutions={},depthCounter=0},
{$FlatSymbols,$SearchDepth, $Verbose,$Modification}={FlatSymbols,SearchDepth,Verbose,Modification}/.{opt}/.Options[MatchFlat];
flatteningRules=Map[Rule[#[x___,#[y___],z___],#[x,y,z]]&,$FlatSymbols];
multiSetOfMatchingProblems={system[{patt≪data},{}]};
While[multiSetOfMatchingProblems=!={}∧depthCounter<$SearchDepth,
(*Print[multiSetOfMatchingProblems];*)
matchingProblem=multiSetOfMatchingProblems[[1]]//.flatteningRules;
If[matchingProblem[[1]]==={},
AppendTo[solutions,matchingProblem[[2]]];
If[$Verbose, Print[matchingProblem[[2]]]];
multiSetOfMatchingProblems=Rest[multiSetOfMatchingProblems],
newMatchingProblems=TransformSystem[matchingProblem];
(*"Print["newMatchingProblems ",newMatchingProblems];*)
multiSetOfMatchingProblems=Join[Rest[multiSetOfMatchingProblems],newMatchingProblems]];
depthCounter++];
If[multiSetOfMatchingProblems=!={},Print["Search depth exceeded."]];
Clear[$FlatSymbols,$SearchDepth, $Verbose,$Modification];
solutions];

Transformation Rules

Clear[TransformSystem];

The first argument of system in the rules below is a flag. Its possible values are 0 and 1. When the value is 0, any rule can be applied without restrition. When the value is 1, there is a restriction on using the first alternative with the substitution {x->Sequence[f[],x]} in the section Sequence Variable Projection (SVP), Sequence Variable Widening (SVW), Sequence Variable Widening under Flat Head (SVW-FH), and Sequence Variable Widening 2 under Flat Head (SVW-FH2). It prevents looping and represents the solution set by finite means.

Trivial (T)

TransformSystem[system[_ : 0,{t_≪t_,rest___},σ_]]:={system[{rest},σ]};

Identifying f[] and f

This is formulated as a convention in the paper, not as an explicit rule.

TransformSystem[system[_ : 0,{f_[]≪f_|f_≪f_[],rest___},σ_]]:={system[{rest},σ]};

Solve in Mathematica (S-Mma)

TransformSystem[system[_ : 0,{x_?IVarQ≪t_,rest___}/;FreeQ[{rest},x],σ_]]:={system[{rest}/.{x->t},ComposeSubst[σ,{x->t}]]}/;$Modification===Mma;
TransformSystem[system[_ : 0,{x_?IVarQ≪t_,eqs1___,x_≪t_,eqs2___},σ_]]:={system[{x≪t,eqs1,eqs2},σ]}/;$Modification===Mma;
TransformSystem[system[_ : 0,{x_?IVarQ≪t1_,___,x_≪t2_,___}/;t1=!=t2,_]]:={}/;$Modification===Mma;
TransformSystem[system[_ : 0,{x_?IVarQ≪t_,rest___},σ_]]:={system[{rest,x≪t},σ]}/;$Modification===Mma;

Solve (S)

TransformSystem[system[_ : 0,{x_?IVarQ≪t_,rest___},σ_]]:={system[{rest}/.{x->t},ComposeSubst[σ,{x->t}]]};

Failure: Symbol Clash

This rule is not explicitly formulated in the paper. There it is covered by the decision algorithm.

TransformSystem[system[_ : 0,{f_[s___]≪g_[t___]|f_[s___]≪g_?ConstantQ|f_?ConstantQ≪g_[t___]|f_?ConstantQ≪g_?ConstantQ,___}/;f=!=g∧!FVarQ[f],_]]:={};

Failure: Empty Left Side (ELS)

TransformSystem[system[_ : 0,{_[]≪_[__],___},_]]:={};

Function Variable Elimination in Mathematica (FVE-Mma)

When this rule is applicable, the FVE rule below does not apply.

TransformSystem[system[_ : 0,{f_?FVarQ[s___]≪g_?FlatQ[t___],rest___},σ_]]:=Module[{freshFreeSymbol=Unique["h"]},
{system[{freshFreeSymbol[s]≪freshFreeSymbol[t],rest},ComposeSubst[σ,{f->g}]]}]/;$Modification===Mma && ((f/.σ )===f);

TransformSystem[system[_ : 0,{f_?FVarQ[s___]≪g_?FlatQ[t___],rest___},σ_]]:=Module[{freshFreeSymbol=Unique["h"]},
{system[{freshFreeSymbol[s]≪freshFreeSymbol[t],rest},σ]}]/;$Modification===Mma && ((f/.σ )===g);

TransformSystem[system[_ : 0,{f_?FVarQ[s___]≪g_?FlatQ[t___],rest___},σ_]]:={}/;$Modification===Mma ;

Function Variable Elimination (FVE)

This rule applies when either $Modification == None or $Modification == NE, or $Modification == Mma and g is not flat.

TransformSystem[system[_ : 0,{f_?FVarQ[s___]≪g_[t___],rest___},σ_]]:={system[{g[s]≪g[t],rest}/.{f->g},ComposeSubst[σ,{f->g}]]};

Failure: Size of the Right Side is Smaller than the Minimal Size of the Left Side

This rule is not explicitly formulated in the paper. There it is covered by the decision algorithm. It subsumes the rule ERS.

TransformSystem[system[_ : 0,{s_≪t_,___},_]]/;(LeafCount[s/.{•var[_]:>Sequence[]}]>LeafCount[t]):={};

Sequence Variable Projection (SVP), Sequence Variable Widening (SVW), Sequence Variable Widening under Flat Head (SVW-FH), and Sequence Variable Widening 2 under Flat Head (SVW-FH2)

The first alternative here work for (Subscript[𝔉, FR]) only. This is the only place where the value of the flag can be changed from 0 to 1, and also the only place where the flag value is taken into account.

TransformSystem[system[flag_:0,{f_[x_?SVarQ,s___]≪f_[t___],rest___},σ_]]:=Module[{tlength=Length[f[t]],newSystems={},i,suspisiosEquations},
AppendTo[newSystems,system[{f[s]≪f[t],rest}/.{x:>Sequence[]},ComposeSubst[σ,{x->sequence[]}]]];
If[tlength>0,AppendTo[newSystems,system[{f[x,Sequence@@({s}/.{x->Sequence[f[t][[1]],x]})]≪Drop[f[t],1],Sequence@@({rest}/.{x->Sequence[f[t][[1]],x]})},ComposeSubst[σ,{x->sequence[f[t][[1]],x]}]]]];
If[FlatQ[f],
suspisiosEquations={f[x,Sequence@@({s}/.{x->Sequence[f[],x]})]≪f[t],Sequence@@({rest}/.{x->Sequence[f[],x]})};
If[flag===0,
If[suspisiosEquations==={f[x,s]≪f[t],rest},
AppendTo[newSystems,system[1,suspisiosEquations,σ∘(SuperPlus[{x->sequence[f[],x]}])]],
AppendTo[newSystems,system[0,suspisiosEquations,ComposeSubst[σ,{x->sequence[f[],x]}]]]
]];
For[i=1,i≤tlength,i++,
AppendTo[newSystems,system[{f[x,Sequence@@({s}/.{x->Sequence[Take[f[t],i],x]})]≪Drop[f[t],i],Sequence@@({rest}/.{x->Sequence[Take[f[t],i],x]})},ComposeSubst[σ,{x->sequence[Take[f[t],i],x]}]]]]];
newSystems]/;$Modification===FR;

Since these rules can be applied on the same matching problem in different ways for 𝔉,  (Subscript[𝔉, NE]) and  (Subscript[𝔉, Mma]) , they are combined here in a single rule. SVW-FH2 replaces SVW-FH when $Modification is set to NE.

TransformSystem[system[_:0,{f_[x_?SVarQ,s___]≪f_[t___],rest___},σ_]]:=Module[{tlength=Length[f[t]],newSystems={},i,shortestSequenceUnderFlatSymbol},
AppendTo[newSystems,system[{f[s]≪f[t],rest}/.{x:>Sequence[]},ComposeSubst[σ,{x->sequence[]}]]];
If[tlength>0,AppendTo[newSystems,system[{f[x,Sequence@@({s}/.{x->Sequence[f[t][[1]],x]})]≪Drop[f[t],1],Sequence@@({rest}/.{x->Sequence[f[t][[1]],x]})},ComposeSubst[σ,{x->sequence[f[t][[1]],x]}]]]];
If[$Modification=!=Mma∧FlatQ[f],
If[$Modification===NE,shortestSequenceUnderFlatSymbol=1,shortestSequenceUnderFlatSymbol=0];
For[i=shortestSequenceUnderFlatSymbol,i≤tlength,i++,
AppendTo[newSystems,system[{f[x,Sequence@@({s}/.{x->Sequence[Take[f[t],i],x]})]≪Drop[f[t],i],Sequence@@({rest}/.{x->Sequence[Take[f[t],i],x]})},ComposeSubst[σ,{x->sequence[Take[f[t],i],x]}]]]]];
newSystems];

Individual Variable Elimination in Mathematica (IVE-Mma), and Individual Variable Elimination under Flat Head in Mathematica (IVE-FH-Mma)

Since these rules can be applied on the same matching problem in different ways, they are combined here in a single rule.

TransformSystem[system[_:0,{f_[x_?IVarQ,s___]≪f_[t___],rest___},σ_]]:=Module[{tlength=Length[f[t]],newSystems={},i},
If[tlength>0∧!FlatQ[f],AppendTo[newSystems,system[{x≪f[t][[1]],f[s]≪Drop[f[t],1],rest},σ]]];
If[FlatQ[f],
For[i=1,i≤tlength,i++,
AppendTo[newSystems,system[{x≪Take[f[t],i],f[s]≪Drop[f[t],i],rest},σ]]]];
newSystems]/;$Modification===Mma;

Individual Variable Elimination (IVE) and Individual Variable Elimination under Flat Head (IVE-FH)

Since these rules can be applied on the same matching problem in different ways, they are combined here in a single rule.

TransformSystem[system[_:0,{f_[x_?IVarQ,s___]≪f_[t___],rest___},σ_]]:=Module[{tlength=Length[f[t]],newSystems={},i,shortestTermUnderFlatSymbol},
If[tlength>0,AppendTo[newSystems,system[{x≪f[t][[1]],f[s]≪Drop[f[t],1],rest},σ]]];
If[FlatQ[f],
For[i=0,i≤tlength,i++,
AppendTo[newSystems,system[{x≪Take[f[t],i],f[s]≪Drop[f[t],i],rest},σ]]]];
newSystems];

Decomposition (Dec)

TransformSystem[system[_:0,{f_[s1_/;Not[VarQ[s1]],s___]≪f_[t1_,t___],rest___},σ_]]:={system[{s1≪t1,f[s]≪f[t],rest},σ]};

Failure: Default Failure Rule that Catches All Remaining Cases

TransformSystem[_]:={};

Auxiliary Functions

Variable and Constant Recognizers

Clear[VarQ];
VarQ[_•var]:=True;
VarQ[_]:=False;

Clear[IVarQ];
IVarQ[•var[_Symbol]]:=True;
IVarQ[_]:=False;

Clear[SVarQ];
SVarQ[•var[•seq[_Symbol]]]:=True;
SVarQ[_]:=False;

Clear[FVarQ];
FVarQ[x_]:=IVarQ[x];

Clear[FlatQ];
FlatQ[f_]:=MemberQ[$FlatSymbols,f];

Clear[ConstantQ];
ConstantQ[f_Symbol]:=True;
ConstantQ[f_Integer]:=True;
ConstantQ[_]:=False;

Substitution Composition

Clear[ComposeSubst];
ComposeSubst[{},subst_]:=subst;
ComposeSubst[SmallCircle[substs1___,{},subst2___],subst_]:=ComposeSubst[SmallCircle[substs1,subst2],subst];
ComposeSubst[SmallCircle[substs___,(SuperPlus[(subst1_)])],subst2_]:=SmallCircle[substs,(SuperPlus[(subst1)]),subst2];
ComposeSubst[SmallCircle[substs___,subst1_],subst2_]:=SmallCircle[substs,ComposeSubst[subst1,subst2]];
ComposeSubst[subst1_,subst2_]:=Module[{tmp=MapAt[(#/.subst2)&,Transpose[subst1/.Rule->List],2],patt, ans},
patt:=Alternatives@@First[tmp];
ans=DeleteCases[Join[Inner[Rule,Sequence@@tmp,List],DeleteCases[subst2,_[patt,_]]],_[x_,x_]];
ans=ans/.{sequence->Sequence}/.{Sequence->sequence};
ans];

Constructor sequence for Sequences in Substitutions

Clear[sequence];
sequence[x___,sequence[y___],z___]:=sequence[x,y,z];
sequence[x_]:=x

sequence/:MakeBoxes[sequence[x___],StandardForm]:=MakeBoxes[BracketingBar[x],StandardForm];

Examples

Example 10 from the Paper

Below we assume that the function symbol ff is flat. It is achieved by evaluating the following cell:

SetAttributes[ff,Flat]

It will be used in the problems for Mathematica native flat matching, computed by using ReplaceList.

Problem 1

MatchFlat[f[•var[x]]≪f[a],FlatSymbols->{f}]

MatchFlat[f[•var[x]]≪f[a],FlatSymbols->{f},Modification->NE]

MatchFlat[f[•var[x]]≪f[a],FlatSymbols->{f},Modification->Mma]

ReplaceList[ff[a],ff[x_]:>{"x"->x}]

MatchFlat[f[•var[x]]≪f[a],FlatSymbols->{f},Modification->FR]

Problem 2

MatchFlat[f[•var[•seq[y]]]≪f[a],FlatSymbols->{f}]

MatchFlat[f[•var[•seq[y]]]≪f[a],FlatSymbols->{f},Modification->NE]

MatchFlat[f[•var[•seq[y]]]≪f[a],FlatSymbols->{f},Modification->Mma]

ReplaceList[ff[a],ff[y___]:>{"y"->sequence[y]}]

MatchFlat[f[•var[•seq[y]]]≪f[a],FlatSymbols->{f},Modification->FR]

Problem 3

MatchFlat[f[•var[x],a]≪f[a],FlatSymbols->{f}]

MatchFlat[f[•var[x],a]≪f[a],FlatSymbols->{f},Modification-> NE]

MatchFlat[f[•var[x],a]≪f[a],FlatSymbols->{f},Modification-> Mma]

ReplaceList[ff[a],ff[x_,a]:>{"x"->x}]

MatchFlat[f[•var[x],a]≪f[a],FlatSymbols->{f},Modification-> FR]

Problem 4

MatchFlat[f[•var[•seq[y]],a]≪f[a],FlatSymbols->{f}]

MatchFlat[f[•var[•seq[y]],a]≪f[a],FlatSymbols->{f},Modification-> NE]

MatchFlat[f[•var[•seq[y]],a]≪f[a],FlatSymbols->{f},Modification-> Mma]

ReplaceList[ff[a],ff[y___,a]:> {"y"->sequence[y]}]

MatchFlat[f[•var[•seq[y]],a]≪f[a],FlatSymbols->{f},Modification-> FR]

Problem 5

MatchFlat[f[•var[x],•var[y]]≪f[a,b,c],FlatSymbols->{f}]

MatchFlat[f[•var[x],•var[y]]≪f[a,b,c],FlatSymbols->{f},Modification-> NE]

MatchFlat[f[•var[x],•var[y]]≪f[a,b,c],FlatSymbols->{f},Modification-> Mma]

ReplaceList[ff[a,b,c],ff[x_,y_]:> {"x"->x,"y"->y}]

MatchFlat[f[•var[x],•var[y]]≪f[a,b,c],FlatSymbols->{f},Modification-> FR]

Problem 6

MatchFlat[f[•var[x],•var[•seq[y]]]≪f[a,b,c],FlatSymbols->{f},SearchDepth->700]//Sort

MatchFlat[f[•var[x],•var[•seq[y]]]≪f[a,b,c],FlatSymbols->{f},Modification-> NE,SearchDepth->200]//Sort

MatchFlat[f[•var[x],•var[•seq[y]]]≪f[a,b,c],FlatSymbols->{f},Modification-> Mma,SearchDepth->200]//Sort

ReplaceList[ff[a,b,c],ff[x_,y___]:> {"x"->x,"y"->sequence[y]}]

MatchFlat[f[•var[x],•var[•seq[y]]]≪f[a,b,c],FlatSymbols->{f},SearchDepth->900,Modification-> FR]//Sort

Problem 7

MatchFlat[f[•var[x],g[•var[x]]]≪f[a,g[a]],FlatSymbols->{f}]

MatchFlat[f[•var[x],g[•var[x]]]≪f[a,g[a]],FlatSymbols->{f},Modification-> NE]

MatchFlat[f[•var[x],g[•var[x]]]≪f[a,g[a]],FlatSymbols->{f},Modification-> Mma]

ReplaceList[ff[a,g[a]],ff[x_,g[x_]]:> {"x"->x}]

MatchFlat[f[•var[x],g[•var[x]]]≪f[a,g[a]],FlatSymbols->{f},Modification-> FR]

Problem 8

MatchFlat[f[•var[•seq[y]],g[•var[•seq[y]]]]≪f[a,g[a]],FlatSymbols->{f}]

MatchFlat[f[•var[•seq[y]],g[•var[•seq[y]]]]≪f[a,g[a]],FlatSymbols->{f},Modification-> NE]

MatchFlat[f[•var[•seq[y]],g[•var[•seq[y]]]]≪f[a,g[a]],FlatSymbols->{f},Modification-> Mma]

ReplaceList[ff[a,g[a]],ff[y___,g[y___]]:> {"y"->sequence[y]}]

MatchFlat[f[•var[•seq[y]],g[•var[•seq[y]]]]≪f[a,g[a]],FlatSymbols->{f},Modification-> FR]

Problem 9

MatchFlat[f[•var[x],g[•var[x]]]≪f[a,g[f[a]]],FlatSymbols->{f}]

MatchFlat[f[•var[x],g[•var[x]]]≪f[a,g[f[a]]],FlatSymbols->{f},Modification-> NE]

MatchFlat[f[•var[x],g[•var[x]]]≪f[a,g[f[a]]],FlatSymbols->{f},Modification-> Mma]

ReplaceList[ff[a,g[ff[a]]],ff[x_,g[x_]]:> {"x"->x}]

MatchFlat[f[•var[x],g[•var[x]]]≪f[a,g[f[a]]],FlatSymbols->{f},Modification-> FR]

Problem 10

MatchFlat[f[•var[•seq[y]],g[•var[•seq[y]]]]≪f[a,g[f[a]]],FlatSymbols->{f}]

MatchFlat[f[•var[•seq[y]],g[•var[•seq[y]]]]≪f[a,g[f[a]]],FlatSymbols->{f},Modification-> NE]

MatchFlat[f[•var[•seq[y]],g[•var[•seq[y]]]]≪f[a,g[f[a]]],FlatSymbols->{f},Modification-> Mma]

ReplaceList[ff[a,g[ff[a]]],ff[y___,g[y___]]:> {"y"->sequence[y]}]

MatchFlat[f[•var[•seq[y]],g[•var[•seq[y]]]]≪f[a,g[f[a]]],FlatSymbols->{f},Modification-> FR]

Problem 11 (Former Problem 13)

MatchFlat[•var[F][•var[x],g[•var[x]]]≪f[a,g[a]],FlatSymbols->{f}]

MatchFlat[•var[F][•var[x],g[•var[x]]]≪f[a,g[a]],FlatSymbols->{f},Modification-> NE]

MatchFlat[•var[F][•var[x],g[•var[x]]]≪f[a,g[a]],FlatSymbols->{f},Modification-> Mma]

ReplaceList[ff[a,g[a]],F_[x_,g[x_]]:> {"F"->F,"x"->x}]

MatchFlat[•var[F][•var[x],g[•var[x]]]≪f[a,g[a]],FlatSymbols->{f},Modification-> FR]

Problem 12 (Former Problem 14)

MatchFlat[•var[F][•var[•seq[y]],g[•var[•seq[y]]]]≪f[a,g[a]],FlatSymbols->{f}]

MatchFlat[•var[F][•var[•seq[y]],g[•var[•seq[y]]]]≪f[a,g[a]],FlatSymbols->{f},Modification-> NE]

MatchFlat[•var[F][•var[•seq[y]],g[•var[•seq[y]]]]≪f[a,g[a]],FlatSymbols->{f},Modification-> Mma]

ReplaceList[ff[a,g[a]],F_[y___,g[y___]]:> {"F"->F,"y"->sequence[y]}]

MatchFlat[•var[F][•var[•seq[y]],g[•var[•seq[y]]]]≪f[a,g[a]],FlatSymbols->{f},Modification-> FR]

Problem 13 (Former Problem 15)

MatchFlat[•var[F][•var[x],g[•var[x]]]≪f[a,g[f[a]]],FlatSymbols->{f}]

MatchFlat[•var[F][•var[x],g[•var[x]]]≪f[a,g[f[a]]],FlatSymbols->{f},Modification-> NE]

MatchFlat[•var[F][•var[x],g[•var[x]]]≪f[a,g[f[a]]],FlatSymbols->{f},Modification-> Mma]

ReplaceList[ff[a,g[a]],F_[x_,g[ff[x_]]]:> {"F"->F,"x"->x}]

MatchFlat[•var[F][•var[x],g[•var[x]]]≪f[a,g[f[a]]],FlatSymbols->{f},Modification-> FR]

Problem 14 (Former Problem 16)

MatchFlat[•var[F][•var[•seq[y]],g[•var[•seq[y]]]]≪f[a,g[f[a]]],FlatSymbols->{f}]

MatchFlat[•var[F][•var[•seq[y]],g[•var[•seq[y]]]]≪f[a,g[f[a]]],FlatSymbols->{f},Modification-> NE]

MatchFlat[•var[F][•var[•seq[y]],g[•var[•seq[y]]]]≪f[a,g[f[a]]],FlatSymbols->{f},Modification-> Mma]

ReplaceList[ff[a,g[a]],F_[y___,g[ff[y___]]]:> {"F"->F,"y"->sequence[y]}]

MatchFlat[•var[F][•var[•seq[y]],g[•var[•seq[y]]]]≪f[a,g[f[a]]],FlatSymbols->{f},Modification-> FR]

Other Problems That Do Not Appear in the Paper

Former Problem 11

MatchFlat[f[•var[x],g[•var[x]]]≪f[g[f[]]],FlatSymbols->{f}]

MatchFlat[f[•var[x],g[•var[x]]]≪f[g[f[]]],FlatSymbols->{f},Modification-> NE]

MatchFlat[f[•var[x],g[•var[x]]]≪f[g[f[]]],FlatSymbols->{f},Modification-> Mma]

ReplaceList[ff[g[ff[]]],ff[x_,g[x_]]:> {"x"->x}]

Former Problem 12

MatchFlat[f[•var[•seq[y]],g[•var[•seq[y]]]]≪f[g[f[]]],FlatSymbols->{f}]

MatchFlat[f[•var[•seq[y]],g[•var[•seq[y]]]]≪f[g[f[]]],FlatSymbols->{f},Modification-> NE]

MatchFlat[f[•var[•seq[y]],g[•var[•seq[y]]]]≪f[g[f[]]],FlatSymbols->{f},Modification-> Mma]

ReplaceList[ff[g[ff[]]],ff[y___,g[y___]]:> {"y"->sequence[y]}]

f replaced with •var[F] in Problem 11

MatchFlat[•var[F][•var[x],g[•var[x]]]≪f[g[f[]]],FlatSymbols->{f}]

MatchFlat[•var[F][•var[x],g[•var[x]]]≪f[g[f[]]],FlatSymbols->{f},Modification-> NE]

MatchFlat[•var[F][•var[x],g[•var[x]]]≪f[g[f[]]],FlatSymbols->{f},Modification-> Mma]

ReplaceList[ff[g[ff[]]],F_[x_,g[x_]]:> {"F"->F,"x"->x}]

f replaced with •var[F] in Problem 12

MatchFlat[•var[F][•var[•seq[y]],g[•var[•seq[y]]]]≪f[g[f[]]],FlatSymbols->{f}]

MatchFlat[•var[F][•var[•seq[y]],g[•var[•seq[y]]]]≪f[g[f[]]],FlatSymbols->{f},Modification-> NE]

MatchFlat[•var[F][•var[•seq[y]],g[•var[•seq[y]]]]≪f[g[f[]]],FlatSymbols->{f},Modification-> Mma]

ReplaceList[ff[g[ff[]]],F_[y___,g[y___]]:> {"F"->F,"y"->sequence[y]}]

New Problem 1 (Not in the Paper)

MatchFlat[f[•var[•seq[x]],•var[•seq[y]]]≪f[a,b,c],FlatSymbols->{f},SearchDepth->8000]//Length

MatchFlat[f[•var[x],•var[•seq[y]]]≪f[a,b,c],FlatSymbols->{f},SearchDepth->8000,Modification-> NE]

MatchFlat[f[•var[•seq[x]],•var[•seq[y]]]≪f[a,b,c],FlatSymbols->{f},SearchDepth->8000,Modification-> Mma]//Length

ReplaceList[ff[a,b,c],ff[x_,y___]:> {"x"->sequence[x],"y"->sequence[y]}]

MatchFlat[f[•var[•seq[x]],•var[•seq[y]]]≪f[a,b,c],FlatSymbols->{f},SearchDepth->8000,Modification-> FR]//Length

New Problem 2 (Not in the Paper, fixed a bug with multiple occurrence of•var[F] in Modification-> Mma)

MatchFlat[g[•var[F][•var[x],g[•var[x]]],•var[F][•var[x],g[•var[x]]]]≪g[f[a,g[f[a]]],f[a,g[f[a]]]],FlatSymbols->{f}]

MatchFlat[g[•var[F][•var[x],g[•var[x]]],•var[F][•var[x],g[•var[x]]]]≪g[f[a,g[f[a]]],f[a,g[f[a]]]],FlatSymbols->{f},Modification-> NE]

MatchFlat[g[•var[F][•var[x],g[•var[x]]],•var[F][•var[x],g[•var[x]]]]≪g[f[a,g[f[a]]],f[a,g[f[a]]]],FlatSymbols->{f},Modification-> Mma]

ReplaceList[g[ff[a,g[ff[a]]],ff[a,g[ff[a]]]],g[f_[x_,g[x_]],f_[x_,g[x_]]]:> {"x"->sequence[x]}]

MatchFlat[g[•var[F][•var[x],g[•var[x]]],•var[F][•var[x],g[•var[x]]]]≪g[f[a,g[f[a]]],f[a,g[f[a]]]],FlatSymbols->{f},Modification-> FR]

New Problem 3 (Not in the Paper, fixed a bug with multiple occurrence of•var[F] in Modification-> Mma)

MatchFlat[g[•var[F][•var[•seq[y]],g[•var[•seq[y]]]],•var[F][•var[•seq[y]],g[•var[•seq[y]]]]]≪g[f[a,g[f[a]]],f[a,g[f[a]]]],FlatSymbols->{f}]

MatchFlat[g[•var[F][•var[•seq[y]],g[•var[•seq[y]]]],•var[F][•var[•seq[y]],g[•var[•seq[y]]]]]≪g[f[a,g[f[a]]],f[a,g[f[a]]]],FlatSymbols->{f},Modification-> NE]

MatchFlat[g[•var[F][•var[•seq[y]],g[•var[•seq[y]]]],•var[F][•var[•seq[y]],g[•var[•seq[y]]]]]≪g[f[a,g[f[a]]],f[a,g[f[a]]]],FlatSymbols->{f},Modification-> Mma]

ReplaceList[g[ff[a,g[ff[a]]],ff[a,g[ff[a]]]],g[f_[x___,g[x___]],f_[x___,g[ff[x___]]]]:> {"f"->f,"x"->sequence[x]}]

MatchFlat[g[•var[F][•var[•seq[y]],g[•var[•seq[y]]]],•var[F][•var[•seq[y]],g[•var[•seq[y]]]]]≪g[f[a,g[f[a]]],f[a,g[f[a]]]],FlatSymbols->{f},Modification-> FR]

New Problem 4 (Not in the Paper)

MatchFlat[g[•var[F][•var[•seq[x]],g[f[•var[•seq[x]]]]],•var[F][•var[•seq[x]],g[f[•var[•seq[x]]]]]]≪g[f[a,g[f[a]]],f[a,g[f[a]]]],FlatSymbols->{f},SearchDepth->200]

MatchFlat[g[•var[F][•var[•seq[x]],g[f[•var[•seq[x]]]]],•var[F][•var[•seq[x]],g[f[•var[•seq[x]]]]]]≪g[f[a,g[f[a]]],f[a,g[f[a]]]],FlatSymbols->{f},Modification-> NE]

MatchFlat[g[•var[F][•var[•seq[x]],g[f[•var[•seq[x]]]]],•var[F][•var[•seq[x]],g[f[•var[•seq[x]]]]]]≪g[f[a,g[f[a]]],f[a,g[f[a]]]],FlatSymbols->{f},Modification-> Mma]

ReplaceList[g[ff[a,g[ff[a]]],ff[a,g[ff[a]]]],g[f_[x___,g[ff[x___]]],f_[x___,g[ff[x___]]]]:> {"f"->f,"x"->sequence[x]}]

MatchFlat[g[•var[F][•var[•seq[x]],g[f[•var[•seq[x]]]]],•var[F][•var[•seq[x]],g[f[•var[•seq[x]]]]]]≪g[f[a,g[f[a]]],f[a,g[f[a]]]],FlatSymbols->{f},SearchDepth->100000,Modification-> FR]//Length

Cleaning Up

ClearAttributes[ff,Flat]

Clear[sequence]