Grez Alejandro, Mazowiecki Filip, Pilipczuk Michał, Puppis Gabriele, Riveros Cristian
Pontificia Universidad Católica de Chile, Santiago, Chile.
Millennium Institute for Foundational Research on Data, Santiago, Chile.
Algorithmica. 2022;84(11):3223-3245. doi: 10.1007/s00453-022-01025-8. Epub 2022 Sep 5.
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.
我们研究自动机理论中经典成员问题的一个变体，该问题包括判定给定的输入单词是否被给定的自动机接受。我们通过参数化动态数据结构的视角来进行研究：我们假设自动机是固定的，其大小为参数，而输入单词如在流中那样被揭示，按照位置上的自然顺序一次一个符号。目标是设计一种动态数据结构，它在揭示下一个符号时能够被高效更新，同时保持对于由迄今已揭示符号组成的单词是否被自动机接受这一查询的答案。我们给出了处理与时间跨度交错的符号的定时自动机的这种动态接受问题的复杂度界限。主要贡献是一种动态数据结构，它能以每个输入符号分摊更新时间来维持固定单时钟定时自动机的接受情况。
