Although many theoretical questions for stack-based automata have already been answered, there are at least as many that are yet not really understood.

The LIFOUNDATIONS project studies three fundamental themes:

- the subclass problem, i.e. to decide if a given stack-based automaton admits a simpler behavior for some subclass of stack-based automata.
- the complexity problem, to classify the computational complexity of the computing power of a given stack-based automata.
- the equivalence problem, to decide if two given stack-based automata behave equivalently.

For further questions, please contact Stefan Göller.

- Arnaud Carayol
- Stefan Göller (PI)
- PhD student to start in 2018 (3 year funding).

- On long words avoiding Zimin patterns (Arnaud Carayol and Stefan Göller, STACS 2017).