Dynamic Data Structures for Timed Automata Acceptance.
Dynamic Data Structures for Timed Automata Acceptance.
复制标题
定时自动机的动态数据结构。
DOI：
10.1007/s00453-022-01025-8
复制
发表时间：
2022
期刊：
影响因子：
1.1
通讯作者：
中科院分区：
文献类型：
--
作者：
我们研究了自动机理论中的经典成员问题的一个变体，它包括决定给定的输入词是否被给定的自动机接受。我们通过参数化动态数据结构的镜头这样做：我们假设自动机是固定的，它的大小是参数，而输入的单词是在流中显示的，一次一个符号，遵循位置的自然顺序。我们的目标是设计一个动态的数据结构，可以有效地更新后，揭示下一个符号，同时保持查询的答案，由符号组成的词是否透露到目前为止，被自动机接受。我们提供了复杂的界限，这个动态接受问题的时间自动机，处理符号交织的时间跨度。主要贡献是一个动态的数据结构，保持接受一个固定的一个时钟定时自动机与摊销更新时间每个输入符号。
We study a variant of the classical membership problem in automata theory, which consists of deciding whether a given input word is accepted by a given automaton. We do so through the lenses of parameterized dynamic data structures: we assume that the automaton is fixed and its size is the parameter, while the input word is revealed as in a stream, one symbol at a time following the natural order on positions. The goal is to design a dynamic data structure that can be efficiently updated upon revealing the next symbol, while maintaining the answer to the query on whether the word consisting of symbols revealed so far is accepted by the automaton. We provide complexity bounds for this dynamic acceptance problem for timed automata that process symbols interleaved with time spans. The main contribution is a dynamic data structure that maintains acceptance of a fixed one-clock timed automaton with amortized update time per input symbol.
登录
查看更多内容
影响因子：
1.1
作者：
Babu, Ajesh;Limaye, Nutan;Varma, Girish
通讯作者：
Varma, Girish
影响因子：
1.8
作者：
Grez, Alejandro;Riveros, Cristian;Vansummeren, Stijn
通讯作者：
Vansummeren, Stijn
影响因子：
--
作者：
Leucker, Martin;Schallhart, Christian
通讯作者：
Schallhart, Christian
影响因子：
1.1
作者：
Idris, Muhammad;Ugarte, Martin;Lehner, Wolfgang
通讯作者：
Lehner, Wolfgang
影响因子：
1.3
作者：
Alman, Josh;Mnich, Matthias;Williams, Virginia Vassilevska
通讯作者：
Williams, Virginia Vassilevska