On the?Determinization of?Event-Clock Input-Driven Pushdown Automata
On the?Determinization of?Event-Clock Input-Driven Pushdown Automata
复制标题
关于事件时钟输入驱动下推自动机的确定
DOI：
10.1007/978-3-031-09574-0_16
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Okhotin Alexander
中科院分区：
文献类型：
--
作者：
Ogawa Mizuhito;Okhotin Alexander
事件时钟模型下的输入驱动下推自动机(也称为可视下推自动机和嵌套字自动机)的时间扩展是由Nguyen和Ogawa(“事件时钟可见下推自动机”，2009)提出的，他们证明了这个模型可以用区域构造的方法来确定。本文提出了一种新的直接确定自动机的方法：将具有不同时钟约束的ANN状态非确定自动机转化为具有状态、堆栈符号和与原自动机相同的时钟约束的确定自动机。该构造被证明是关于状态数目和堆叠符号数目的渐近最优的。
A timed extension of input-driven pushdown automata (also known as visibly pushdown automata and as nested word automata) under the event-clock model was introduced by Nguyen and Ogawa (“Event-clock visibly pushdown automata”, 2009), who showed that this model can be determinized using the method of region construction. This paper proposes a new, direct determinization procedure for these automata: ann-state nondeterministic automaton withkdifferent clock constraints is transformed to a deterministic automaton withstates,stack symbols and the same clock constraints as in the original automaton. The construction is shown to be asymptotically optimal with respect to both the number of states and the number of stack symbols.