论文标题
一盘定时自动机的确定性
Determinisability of one-clock timed automata
论文作者
论文摘要
定时自动机的确定性成员资格问题询问是否可以通过确定的定时自动机识别非确定定时自动机识别的定时语言。我们表明，当输入自动机是无epsilon跃迁的一个单位非确定的定时自动机时，问题是可决定的。我们表明，在所有其他情况下，问题都是不可决定的，即，当1）输入非确定定时的自动机具有两个或更多时钟或更多时钟，或2）它使用Epsilon Transitions，或3）输出确定性自动机的时钟数量未固定。
The deterministic membership problem for timed automata asks whether the timed language recognised by a nondeterministic timed automaton can be recognised by a deterministic timed automaton. We show that the problem is decidable when the input automaton is a one-clock nondeterministic timed automaton without epsilon transitions and the number of clocks of the deterministic timed automaton is fixed. We show that the problem in all the other cases is undecidable, i.e., when either 1) the input nondeterministic timed automaton has two clocks or more, or 2) it uses epsilon transitions, or 3) the number of clocks of the output deterministic automaton is not fixed.
