Termination and Complexity

Notes to students, before reading the documents below:

• Notations: In the lessons I will assume that you know these notations. You can practise by working on some online exercises - Anonymously or if you have an account (account details will be emailed to you).
• Lessons: These slides are rough sketches. I will give much more explanation and examples in class.
• Exercises: We will discuss some of these in class. Don’t worry, some are outside the scope of the lessons, and some are hard research questions (meaning that I don’t know the answer).

Preliminary slides:

• Notations for Rewriting 1x1 4x2
• Lesson 1: introduction, interpretations, matrix algebras, relative termination 1x1 4x2
• Lesson 2: polynomially growing matrix interpretations, relative termination and complexity 1x1 4x2
• Lesson 3: exotic semirings, exotic matrix interpretations, match-bounded rewriting 1x1 4x2
• Exercises