论文标题
确定性明显推动自动机的同步
Synchronization of Deterministic Visibly Push-Down Automata
论文作者
论文摘要
我们将有限自动机的单词同步（将自动机的所有状态映射到同一状态）的概念概括到确定性的明显推动自动机。在这里，同步的单词W不仅将所有状态映射到同一状态，而且还可以满足阅读w后每次运行的堆栈内容的某些条件。我们考虑了这些堆栈约束的三种类型：阅读W后，堆栈（1）在每次运行中为空，（2）在每次运行中包含相同的堆栈符号序列，或（3）包含一个任意序列，与其他运行无关。我们表明，与一般确定性推挤自动机相比，确定性的明显推动自动机是可决定的，是否存在与这些堆栈约束中的每个堆栈约束的同步单词，即问题在exptime中。在约束（1）的约束下，问题甚至在P中。对于确定性的子类非常明显地向下自动机的子类，对于所有三种约束，问题在P中。我们进一步研究了同步问题的变体，其中限制了由同步单词引起的堆栈高度行为的弯曲数，以及同步顺序传感器变体的问题的问题，该变体通过一个单词，通过同步的状态同步并在所有运行中产生同样的输出。
We generalize the concept of synchronizing words for finite automata, which map all states of the automata to the same state, to deterministic visibly push-down automata. Here, a synchronizing word w does not only map all states to the same state but also fulfills some conditions on the stack content of each run after reading w. We consider three types of these stack constraints: after reading w, the stack (1) is empty in each run, (2) contains the same sequence of stack symbols in each run, or (3) contains an arbitrary sequence which is independent of the other runs. We show that in contrast to general deterministic push-down automata, it is decidable for deterministic visibly push-down automata whether there exists a synchronizing word with each of these stack constraints, i.e., the problems are in EXPTIME. Under the constraint (1) the problem is even in P. For the sub-classes of deterministic very visibly push-down automata the problem is in P for all three types of constraints. We further study variants of the synchronization problem where the number of turns in the stack height behavior caused by a synchronizing word is restricted, as well as the problem of synchronizing a variant of a sequential transducer, which shows some visibly behavior, by a word that synchronizes the states and produces the same output on all runs.
