| Meno: | David
|
|---|
| Priezvisko: | Zachar
|
|---|
| Názov: | Edit distance on trees and their representations
|
|---|
| Vedúci: | prof. RNDr. Branislav Rovan, PhD.
|
|---|
| Rok: | 2010
|
|---|
| Blok: | INF
|
|---|
| Kµúčové slová: | tree distance, string distance, edit distance, coding trees to strings, encoding trees, euler string, binary tree code, level code, tree representations
|
|---|
| Abstrakt: | 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.
|
|---|