The path-tree parse-word and level-restriction conjecture
The path-tree parse-word and level-restriction conjecture
Let , and let and be -leaf path trees such that leaf is on level in and leaf is on level in . A pair is mutually crooked if it cannot be obtained by duplicating a leaf in a pair of -leaf trees, and weakly mutually crooked if it cannot be obtained by triplicating a leaf in a pair of -leaf trees. A parse word is a word that parses both trees. Path-tree parse-word and level-restriction conjecture. The following assertions hold: (i) if and have no parse word of the form or , then they have a unique parse word up to permutation of the alphabet; (ii) if they have no parse word of the form and are mutually crooked, then they have a parse word of the form ; (iii) if they have no parse word of the form , then the only possibilities for the pair of levels of leaves in and in are and for some ; if they are weakly mutually crooked, one has , and if they are mutually crooked, one has . These claims are proposed as tools toward proving that every pair of binary trees has a parse word; the supplied text gives no resolution.
Sources & referencesView supporting material
Primary source
Bobbe Cooper, Eric Rowland and Doron Zeilberger, “Toward a language theoretic proof of the four color theorem”, arXiv:1006.1324 (2011).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.