Streamable regular transductions
Streamable regular transductions
复制标题
DOI：
10.1016/j.tcs.2019.11.018
复制
发表时间：
2020-02-06
影响因子：
1.1
通讯作者：
Stanford, Caleb
中科院分区：
文献类型：
--
作者：
Alur, Rajeev;Fisman, Dana;Stanford, Caleb
出于实时监控和数据处理应用程序，我们开发了一个正式的理论定量查询流数据，可以有效地进行评估。我们认为，明确的成本寄存器自动机（CRA）的模型，这是机器，联合收割机有限状态控制（用于识别规则模式）与有限的数据寄存器集（用于计算数值聚集）。CRA的定义由可以应用于寄存器的数值运算的集合参数化。这些机器产生了可流式正则转换（SR）类，以及当寄存器更新是无拷贝时的可流式线性正则转换（SLR）类，即每个寄存器在更新的右侧表达式中最多出现一次。我们给出了类SR的逻辑特征（分别为，SLR）使用从字符串到DAG（分别为，树）没有向后的边缘。此外，我们建立了两个类SR和SLR是封闭的操作下，设计查询语言相关。最后，我们研究了与加权自动机（WA）的关系，并表明，CRA在一个适当选择的操作集对应于WA，从而建立WA是一个特殊的情况下的CRA。(C)2019由Elsevier B.V.出版
Motivated by real-time monitoring and data processing applications, we develop a formal theory of quantitative queries for streaming data that can be evaluated efficiently. We consider the model of unambiguous Cost Register Automata (CRAs), which are machines that combine finite-state control (for identifying regular patterns) with a finite set of data registers (for computing numerical aggregates). The definition of CRAs is parameterized by the collection of numerical operations that can be applied to the registers. These machines give rise to the class of streamable regular transductions (SR), and to the class of streamable linear regular transductions (SLR) when the register updates are copyless, i.e. every register appears at most once in the right-hand-side expressions of the updates. We give a logical characterization of the class SR (resp., SLR) using MSO-definable transformations from strings to DAGs (resp., trees) without backward edges. Additionally, we establish that the two classes SR and SLR are closed under operations that are relevant for designing query languages. Finally, we study the relationship with weighted automata (WA), and show that CRAs over a suitably chosen set of operations correspond to WA, thus establishing that WA are a special case of CRAs. (C) 2019 Published by Elsevier B.V.