Arbology

Garant předmětu:

Jan Janoušek, Bořivoj Melichar

Lecturer:

Tutor:

Jan Janoušek, Bořivoj Melichar

Supervisor:

Department of Theoretical Computer Science

Synopsis:

Introduction to tree problems and their effective algorithmic solutions.

Algorithms presented on the basis of tree and pushdown automata as models of computation.

Practical algorithms used in compiler construction and XML processing are discussed in details.

Requirements:

Syllabus of lectures:

1.Basic definitions, tree languages, tree automata.

2.Top-down tree automata - nondeterministic, deterministic.

3.Bottom-up tree automata - nondeterministic, deterministic.

4.Tree pattern matching - algorithms based on tree automata.

5.Tree pattern matching - other known methods.

6.Tree automata and pushdown automata.

7.Tree pattern matching and pushdown automata.

8.Indexing trees.

9.Finding repetitions in trees.

10.Approximate tree pattern matching - Hamming distance.

11.Approximate tree pattern matching - Levenstein distance.

12.Automata and XML processing.

13.Covering a tree - code generation in compiler construction.

Syllabus of tutorials:

Study Objective:

Trees are one of the fundamental data structures used in Computer Science. The module deals with principles of effective algorithms working with trees for tasks such as acceptance and translation of tree languages, tree pattern matching, approximate tree pattern matching or indexing trees. . Various types of trees - ordered, unordered, ranked, unranked - are considered. The algorithms are presented on the basis of existing computational models for tree languages, types of tree automata (finite tree automata, tree walking automata, etc.) or pushdown automata. The module also demonstrates practical use of these algorithms for tasks such as various processing of XML data or instruction selection in code generators.

Study materials:

Cleophas, L.: Tree Algorithms. Two Taxonomies and a Toolkit, Technische Universiteit Eindhoven, Eindhoven, 2008

Gecseg, F, Steinby, M.: Tree Languages, In: Vol 3: Beyond Words. Handbook of Formal Languages. pp. 1 -- 68, Springer, Berlin, Heidelberg, 1997.

Hoffman, C. M., O'Donnell M. J.: Pattern Matching in Trees. Journal of ACM, vol. 29, pp. 68 -- 95, 1982.

Janousek, J., Melichar, B. On Regular Tree Languages and Deterministic Pushdown Automata. In Acta Informatica, Vol. 46, No. 7, pp. 533-547, Springer, 2009

Note:

Time-table for winter semester 2023/2024:

Time-table is not available yet

Time-table for summer semester 2023/2024:

Time-table is not available yet

The course is a part of the following study plans:

• Informatics (doctoral) (compulsory elective course)
• Informatics (compulsory elective course)