ParseWords 1.01

documentation notebook

Eric Rowland
https://ericrowland.github.io/packages.html

Introduction

ParseWords is a package for studying parse words of pairs of binary trees under a certain grammar related to the four color theorem.
This introduction gets you started with a few features of the package; the next section provides a complete list of package symbols along with their usage messages and further examples.

ParseWords uses functions from my package BinaryTrees, so you will need to have BinaryTrees installed as well.

To use ParseWords, first you will need to load the package by evaluating the following cell. (If you need help, see loading a package.)

<<ParseWords`

Representing trees

A rooted tree is represented by an expression in which each vertex corresponds to a list containing its children.  For example, here is a 5-leaf binary tree:

{{{},{}},{{{},{}},{}}}

The Wolfram Language symbol TreeForm displays expressions graphically.  BareTreeForm uses TreeForm to draw trees without vertex labels:

BareTreeForm[{{{},{}},{{{},{}},{}}}]

BinaryTrees gives a list of all binary trees with a fixed number of leaves.

BinaryTrees[4]
BareTreeForm/@%

There are also a few parameterized families of trees supported.  These include left comb trees, crooked trees, and turn trees.

Table[BareTreeForm[LeftCombTree[n]],{n,8}]

Table[BareTreeForm[LeftCrookedTree[n]],{n,8}]

Table[BareTreeForm[LeftTurnTree[n,8-n]],{n,6}]

Parse words

A binary tree parses a ternary word w if there is a labeling of the vertices of the tree such that the leaves are labeled with the letters of w (left to right) and every  structure in the tree contains all three letters.  For example, here is a labeling that shows that this 6-leaf tree parses 011121:

TreeForm[LabelTree[{{},{{},{{},{{},{{},{}}}}}},{0,1,1,1,2,1}],ImageSize->200]

ParseWords finds all the parse words of a tree (up to permutations of the alphabet).

ParseWords[{{},{{},{{},{{},{{},{}}}}}}]

The four color theorem is equivalent to the statement that every pair of binary trees with the same number of leaves parse a common word.  When given multiple arguments, ParseWords finds the common parse words of several trees.

ParseWords[{{},{{},{{},{{},{{},{}}}}}},{{{},{}},{{{{},{}},{}},{}}}]

For some parameterized families of trees, the parse words can be written explicitly:

Table[ParseWords[LeftCombTree[n],RightCombTree[n]],{n,8}]

Table[ParseWords[LeftCombTree[n],RightCrookedTree[n]],{n,2,8}]

Package symbols

AllParseWords

?AllParseWords

AllParseWords[{{},{{},{{{},{}},{}}}}]

BottomLeafDisjointQ

?BottomLeafDisjointQ

BottomLeafDisjointQ[{{},{{},{{},{}}}},{{{{},{}},{}},{}}]

BottomLeafLabels

?BottomLeafLabels

BottomLeafLabels[{{},{{},{{{},{}},{}}}},{0,0,0,2,0}]

TreeForm[LabelTree[{{},{{},{{{},{}},{}}}},{0,0,0,2,0}],ImageSize->180]

CanonicalWord

?CanonicalWord

CanonicalWord[{2,0,0,1}]

ConsecutiveLeafPairs

?ConsecutiveLeafPairs

ConsecutiveLeafPairs[{{},{{},{{},{}}}},{{{{},{}},{}},{}}]

DecomposeTrees

?DecomposeTrees

BareTreeForm/@{{{{},{{},{{},{{{},{}},{}}}}},{}},{{},{{{},{{},{{},{{},{}}}}},{}}}}

DecomposeTrees[{{{},{{},{{},{{{},{}},{}}}}},{}},{{},{{{},{{},{{},{{},{}}}}},{}}}]

IndecomposableQ

?IndecomposableQ

IndecomposableQ[{{{},{{},{{},{{{},{}},{}}}}},{}},{{},{{{},{{},{{},{{},{}}}}},{}}}]

LabelLeaves

?LabelLeaves

LabelLeaves[{{},{{},{{{},{}},{}}}},{0,0,0,2,0}]

LabelTree

?LabelTree

LabelTree[{{},{{},{{{},{}},{}}}},{0,0,0,2,0}]

TreeForm[%,ImageSize->180]

MutuallyCrookedQ

?MutuallyCrookedQ

MutuallyCrookedQ[{{},{{},{}}},{{{},{}},{}}]

Find the pairs of 4-leaf binary trees that are mutually crooked:

(BareTreeForm/@#1&)/@Select[Subsets[BinaryTrees[4],{2}],MutuallyCrookedQ@@#1&]

ParentLabel

?ParentLabel

ParentLabel[{{},{{},{{{},{}},{}}}},{0,0,0,2,0},4]

TreeForm[LabelTree[{{},{{},{{{},{}},{}}}},{0,0,0,2,0}],ImageSize->180]

ParseWords

?ParseWords

ParseWords[{{},{{},{{{},{}},{}}}}]

Union[CanonicalWord/@AllParseWords[{{},{{},{{{},{}},{}}}}]]

Find the common parse words of a tree and its left–right reflection:

ParseWords[{{},{{},{{{},{}},{}}}},{{{{},{{},{}}},{}},{}}]

RootLabel

?RootLabel

RootLabel[{{},{{},{{{},{}},{}}}},{0,0,0,2,0}]

The label of the root is an invariant of the word:

DeleteCases[RootLabel[#,{0,1,2,0,2}]&/@BinaryTrees[5],_RootLabel]

SiblingLabel

?SiblingLabel

SiblingLabel[{{},{{},{{{},{}},{}}}},{0,0,0,2,0},4]

TreeForm[LabelTree[{{},{{},{{{},{}},{}}}},{0,0,0,2,0}],ImageSize->180]

WeaklyMutuallyCrookedQ

?WeaklyMutuallyCrookedQ

These two trees are weakly mutually crooked but not mutually crooked:

BareTreeForm/@{{{},{{},{{},{}}}},{{{{},{}},{}},{}}}

WeaklyMutuallyCrookedQ[{{},{{},{{},{}}}},{{{{},{}},{}},{}}]

MutuallyCrookedQ[{{},{{},{{},{}}}},{{{{},{}},{}},{}}]

Find the pairs of 4-leaf path trees that are mutually crooked:

(BareTreeForm/@#1&)/@Select[Subsets[PathTrees[4],{2}],WeaklyMutuallyCrookedQ@@#1&]