Meno: David Zachar Edit distance on trees and their representations prof. RNDr. Branislav Rovan, PhD. 2010 INF tree distance, string distance, edit distance, coding trees to strings, encoding trees, euler string, binary tree code, level code, tree representations The goal of this thesis is to study information about the difference between two trees which we can obtain from the difference between their string representations. First we focus on ideas of computing this difference between two trees called distance presented in other papers. Then we discuss particular string encodings of trees. In this thesis we define a new string encoding of trees. Relation between tree distance of two trees and string distance of their representation given by this encoding is shown by proofs of lower and upper bounds for this encoding. From particular encoding of trees to strings it looks like we cannot get the exact information about tree distance from string distance of its representations. This thesis contains proof that for every encoding ψ, satisfying some natural properties, it is impossible to compute the exact tree distance from the string distance of codes coded by ψ. Formally, there exist trees F and G such that τ(F,G) = Ω(h)δ(ψ(F),ψ(G)) is true, where τ is a tree distance, δ is a string distance and h is the minimal height of trees F and G.

Súbory diplomovej práce: