Streamable regular transductions
From MaRDI portal
Publication:2286735
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.
Recommendations
Cites work
- A comparison of tree transductions defined by monadic second order logic and by attribute grammars
- A generalised twinning property for minimisation of cost register automata
- Automata-based stream processing
- Better complexity bounds for cost register automata
- Complexity of Regular Functions
- Decision problems for additive regular functions
- Decision Problems of Finite Automata Design and Related Arithmetics
- Derivatives of quantitative regular expressions
- DReX: a declarative language for efficiently evaluating regular string transformations
- Expressiveness of streaming string transducers
- Finite state machines for strings over infinite alphabets
- Finite-memory automata
- Handbook of weighted automata
- scientific article; zbMATH DE number 941396 (Why is no real title available?)
- LTL with the freeze quantifier and register automata
- Macro tree transducers, attribute grammars, and MSO definable tree translations.
- Monadic second-order definable graph transductions: a survey
- MSO definable string transductions and two-way finite-state transducers
- Nested weighted automata
- On notions of regularity for data languages
- On the definition of a family of automata
- Quantitative languages
- Quantitative monitor automata
- Regular combinators for string transformations
- Regular functions and cost register automata (invited paper)
- Regular Programming for Quantitative Properties of Data Streams
- Regular transformations of infinite strings
- Streaming transducers for algorithmic verification of single-pass list-processing programs
- THE EQUALITY PROBLEM FOR RATIONAL SERIES WITH MULTIPLICITIES IN THE TROPICAL SEMIRING IS UNDECIDABLE
- Two-variable logic on data words
- Weak Second‐Order Arithmetic and Finite Automata
- What's decidable about weighted automata?
Cited in
(4)
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)
