A lower bound approach for automata involving clocks or counters

The main part of my talk will be about a more in-depth explanation

of a lower bound approach for the emptiness problem for automata involving clocks or counters developed jointly with Markus Lohrey.

It combines two known results from complexity theory, namely

(1) the leaf language characterization of various complexity classes like NP, PP, PSPACE, EXPSPACE and

(2) that numbers given in Chinese Remainder presentation can be transformed in binary representation in logarithmic space.

 

In the second part of my talk I will introduce a suitable programming language developed jointly with Mathieu Hilaire that serves as a handy interface for applying this approach to some concrete problems.