Some Mealy machines generating a particular transduction monoid.
This course provides a gentle introduction into complexity theory, the theory of computations that are restricted by various resource bounds (time, space, energy, ...). We start with a brief tour of the computational universe at large and then home in on the low complexity classes that are most relevant in theoretical computer science such as NP and PSPACE. Time permitting, we may take a look some non-traditional models of computation such as cellular automata or infinite time Turing machines.
sutner@cs
Office hours: Thursday 16:30–18:00
zscully@cs
Office hours: Wednesday 15:00–17:00
tto@andrew
Office hours: Thursday 12:30–14:30
borgera@andrew
Office hours: Friday 14:00–16:00