(in Polish) Well-Quasi-Orders and Applications 1000-2M26WQO
1) Various definitions and examples of wqo, upward- and downward-closed sets as well as ideals.
2) Closure properties of wqo (Higman's Lemma, Kruskal's Lemma, Rado's counterexample).
3) Solution sets of systems of linear/polynomial equations, and how to solve such systems using Gröbner bases.
4) Definition and examples of well structured transition systems (e.g. lossy channel systems, reset vector addition systems) and an algorithm for the coverability problem, with complexity analysis via a length function theorem for N^d.
5) Definition and examples of amalgamation systems (e.g. branching/grammar vector addition systems) and problems solvable via amalgamation systems, including emptiness, separability, semilinearity and boundedness.
6) Particularly complex is semilinearity: Definition of optimal over- and underapproximations and how to solve the semilinearity problem assuming optimal over- and underapproximations are computable.
7) Definition and examples of weak and uniform pumps as well as uniform sets, and how to compute a decomposition into uniform sets.
8) How to compute an optimal over- and underapproximation from a decomposition into uniform sets.
Course coordinators
Requirements
Learning outcomes
Knowledge:
The student knows the definition of well-quasi-orders and some applications thereof, including Gröbner bases and termination of algorithms.
The student knows the closure properties of wqos and basic length function theorems.
The student knows the definition of well-structured transition systems and amalgamation systems.
Skills:
The student can model the execution of a rank-based algorithm as a bad sequence in some wqo and subsequently use the wqo to analyze the complexity of the algorithm.
The student can recognize classes of WSTS and amalgamation systems.
The student can combine WSTS, amalgamation systems and the different types of approximations to solve complex questions about the behaviour of automata.
Competency:
The student understands the mathematical tool of wqo and can apply them both in computer science and its applications.
Assessment criteria
Oral exam and star assignments.
In the case of a PhD student an additional requirement: solving at least one star
assignment or presenting a recent research article closely related to a chosen topic.
Additional information
Information on level of this course, year of study and semester when the course unit is delivered, types and amount of class hours - can be found in course structure diagrams of apropriate study programmes. This course is related to the following study programmes: