Streamable regular transductions

DOI10.1016/J.TCS.2019.11.018zbMATH Open1436.68157arXiv1807.03865OpenAlexW2990158651WikidataQ126783690 ScholiaQ126783690MaRDI QIDQ2286735FDOQ2286735

Rajeev Alur, Caleb Stanford, Konstantinos Mamouras, Mukund Raghothaman, Dana Fisman

Publication date: 22 January 2020

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: 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 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.

Full work available at URL: https://arxiv.org/abs/1807.03865

zbMATH Keywords

weighted automataregular functionsquantitative automatastream processingcost register automataMSO transductions

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05)

Cites Work

• Title not available (Why is that?)
• DReX: a declarative language for efficiently evaluating regular string transformations
• Handbook of weighted automata
• Monadic second-order definable graph transductions: a survey
• LTL with the freeze quantifier and register automata
• Streaming transducers for algorithmic verification of single-pass list-processing programs
• Two-variable logic on data words
• On the definition of a family of automata
• THE EQUALITY PROBLEM FOR RATIONAL SERIES WITH MULTIPLICITIES IN THE TROPICAL SEMIRING IS UNDECIDABLE
• Weak Second‐Order Arithmetic and Finite Automata
• Decision Problems of Finite Automata Design and Related Arithmetics
• Finite-memory automata
• On notions of regularity for data languages
• What’s Decidable about Weighted Automata?
• Quantitative languages
• Expressiveness of streaming string transducers
• Finite state machines for strings over infinite alphabets
• Macro tree transducers, attribute grammars, and MSO definable tree translations.
• Nested Weighted Automata
• A comparison of tree transductions defined by monadic second order logic and by attribute grammars
• Streaming Tree Transducers
• MSO definable string transductions and two-way finite-state transducers
• Regular Functions and Cost Register Automata
• Quantitative monitor automata
• Derivatives of Quantitative Regular Expressions
• Regular Programming for Quantitative Properties of Data Streams
• Decision Problems for Additive Regular Functions
• Complexity of Regular Functions
• Regular combinators for string transformations
• A Generalised Twinning Property for Minimisation of Cost Register Automata
• Better complexity bounds for cost register automata
• Automata-Based Stream Processing
• Regular Transformations of Infinite Strings

Cited In (3)

• Regular Programming for Quantitative Properties of Data Streams
• Algebraic quantitative semantics for efficient online temporal monitoring
• Semantic Foundations for Deterministic Dataflow and Stream Processing

This page was built for publication: Streamable regular transductions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2286735)