Dyck edit distance of random strings

• Thesis title in Czech: Dyckova vzdálenost náhodných řetězců
• Thesis title in English: Dyck edit distance of random strings
• Key words: Dyckova vzdálenost|uzávorkované výrazy|náhodné řetězce
• English key words: Dyck edit distance|Parenthesized expressions|Random strings
• Academic year of topic announcement: 2024/2025
• Thesis type: diploma thesis
• Thesis language: angličtina
• Department: Computer Science Institute of Charles University (32-IUUK)
• Supervisor: prof. Mgr. Michal Koucký, Ph.D.
• Author: hidden - assigned and confirmed by the Study Dept.
• Date of registration: 15.05.2024
• Date of assignment: 15.05.2024
• Confirmed by Study dept. on: 15.05.2024
• Date and time of defence: 10.09.2024 09:00
• Date of electronic submission: 17.07.2024
• Date of submission of printed version: 18.07.2024
• Date of proceeded defence: 10.09.2024
• Opponents: doc. RNDr. Vít Jelínek, Ph.D.

Guidelines

Pro dva náhodně zvolené řetězce existuje řada prací zkoumajících jejich průměrnou editační vzdálenost. Blízko příbuzná je Dyckova vzdálenost, které pro daný řetězec sestávající z různých druhů závorek měří, kolik závorek je potřeba upravit, aby řetězec byl dobře uzávorkovaný. Cílem práce je nalézt a popsat základní vlastnosti Dyckovy vzdálenosti pro náhodně zvolené řetězce.

There is a sizeable literature on expected properties of edit distance of two randomly chosen strings. Closely related measure, Dyck edit distance, measures how many parenthesis one has to modify in a string consisting of various types of parenthesis in order to make it well parenthesized. The goal of this work is to establish basic properties of Dyck edit distance for a string chosen at randomly.

References

1) V. Chvátal and D. Sankoff. Longest common subsequences of two random sequences. J. Appl. Prob, 12:306–315, 1975.
2) V. Dančík. Expected Length of Longest Common Subsequences. PhD thesis, Department of Computer Science, University of Warwick, September 1994.
3) Kiwi, M., Loebl, M., Matoušek, J. (2004). Expected Length of the Longest Common Subsequence for Large Alphabets. LATIN 2004: Theoretical Informatics. LATIN 2004. LNCS 2976. 2004