Towards the Complexity of Controls for Timed Automata with a Small Number of Clocks ∗

Control of timed systems has become a very active re-search area. In this paper, we revisit the complexity of safety and reachability control problems for timed automata. Gen-erally, these problems turn out to be EXPTIME-complete and we aim at finding tractable subclasses which admit ef-ficient control. To this purpose, we consider the control for timed automata with a small number of clocks. We first show that for three clock TAs, the complexity has climbed up to EXPTIME-complete; We then propose efficient algo-rithms to control one-clock TAs and show that in this setting, the control problems become P-complete, both in the known and unknown switch condition assumptions; In the end, we prove the PSPACE-hardness of control for two-clock TAs.