Regular combinators for string transformations
From MaRDI portal
Publication:4635591
DOI10.1145/2603088.2603151zbMATH Open1401.68141arXiv1402.3021OpenAlexW2079179697MaRDI QIDQ4635591FDOQ4635591
Mukund Raghothaman, Rajeev Alur, Adam Freilich
Publication date: 23 April 2018
Published in: Proceedings of the Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) (Search for Journal in Brave)
Abstract: We focus on (partial) functions that map input strings to a monoid such as the set of integers with addition and the set of output strings with concatenation. The notion of regularity for such functions has been defined using two-way finite-state transducers, (one-way) cost register automata, and MSO-definable graph transformations. In this paper, we give an algebraic and machine-independent characterization of this class analogous to the definition of regular languages by regular expressions. When the monoid is commutative, we prove that every regular function can be constructed from constant functions using the combinators of choice, split sum, and iterated sum, that are analogs of union, concatenation, and Kleene-*, respectively, but enforce unique (or unambiguous) parsing. Our main result is for the general case of non-commutative monoids, which is of particular interest for capturing regular string-to-string transformations for document processing. We prove that the following additional combinators suffice for constructing all regular functions: (1) the left-additive versions of split sum and iterated sum, which allow transformations such as string reversal; (2) sum of functions, which allows transformations such as copying of strings; and (3) function composition, or alternatively, a new concept of chained sum, which allows output values from adjacent blocks to mix.
Full work available at URL: https://arxiv.org/abs/1402.3021
Cited In (15)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Better complexity bounds for cost register automata
- Better complexity bounds for cost register automata
- Regular Programming for Quantitative Properties of Data Streams
- From Two-Way Transducers to Regular Function Expressions
- Title not available (Why is that?)
- Regular transducer expressions for regular transformations
- Title not available (Why is that?)
- Streamable regular transductions
- Efficient construction of reversible transducers from regular transducer expressions
- Transducers of polynomial growth
- Decidable weighted expressions with Presburger combinators
- Title not available (Why is that?)
- Complexity of regular functions
This page was built for publication: Regular combinators for string transformations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4635591)
