Regular combinators for string transformations

DOI10.1145/2603088.2603151MaRDI QIDQ4635591zbMATH OpenOpenAlexFDO

Authors Adam Freilich, Mukund Raghothaman, Rajeev Alur

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)

Full work available at URL https://arxiv.org/abs/1402.3021, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.763.5335

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70)

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.

Recommendations

• Modular descriptions of regular functions
• From two-way transducers to regular function expressions
• From two-way transducers to regular function expressions

Cited in

(15)

• From two-way transducers to regular function expressions
• Complexity of regular functions
• Streamable regular transductions
• String-to-string interpretations with polynomial-size output
• Efficient construction of reversible transducers from regular transducer expressions
• Transducers of polynomial growth
• Sequentiality of string-to-context transducers
• Affine extensions of integer vector addition systems with states
• Modular descriptions of regular functions
• DReX: a declarative language for efficiently evaluating regular string transformations
• scientific article; zbMATH DE number 7407773 (Why is no real title available?)
• Better complexity bounds for cost register automata
• Better complexity bounds for cost register automata
• Regular Programming for Quantitative Properties of Data Streams
• The many facets of string transducers (invited talk)

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)