Regular combinators for string transformations

Rajeev Alur, Adam Freilich, Mukund Raghothaman

TL;DR

This paper introduces a new set of "combinators" – essentially building blocks – that allow us to algebraically define and construct all "regular string transformations." These transformations map strings to values in a monoid (like numbers or other strings) and are crucial for tasks like document processing. The work provides a machine-independent, regular-expression-like way to describe these complex functions.

What Problem Does This Paper Address?

The paper tackles the challenge of formally characterizing "regular string transformations." Think of these as functions that take strings as input and produce outputs like numbers (e.g., counting occurrences) or other strings (e.g., reordering words). While regular languages (like those described by regular expressions) are well-understood, their functional counterparts – regular transformations – have been harder to pin down with a clean, algebraic definition. Existing definitions often rely on specific machine models like two-way finite-state transducers or cost register automata, which can be complex. The authors aim to provide an algebraic characterization analogous to regular expressions for languages, making these transformations easier to understand, manipulate, and reason about. This is particularly important for applications in document processing where complex string manipulations are common.

Methods

The core of the paper is the introduction of a set of "combinators" that act like operators to build regular functions. For commutative monoids (where order doesn't matter, like addition of numbers), they use analogs of union, concatenation, and Kleene star:

  • Choice (▷): Similar to union, but enforces unambiguous parsing.
  • Split Sum (⊕): Analogous to concatenation, but requires a unique split of the input string.
  • Iterated Sum (∑): The analog of Kleene star, allowing for repeated application and summation.

For non-commutative monoids (where order matters, like string concatenation), they introduce additional combinators:

  • Left-Additive Split Sum (⊕) and Iterated Sum: These allow for operations like string reversal.
  • Sum (+): Enables transformations like string copying.
  • Function Composition (∘) or Chained Sum: This is a novel contribution, allowing output values from adjacent blocks to interact, crucial for complex transformations like the "shuffle" example.

The paper then formally defines copyless cost register automata (CCRA) as the machine model for regularity and proves that functions expressible by their combinators are precisely those computable by CCRAs. They also introduce additive cost register automata (ACRA) for the commutative case and explore concepts like "shapes" and "expression vectors" to bridge the gap between automata and algebraic expressions.

Datasets

Not discussed in the paper. The paper focuses on theoretical characterization and does not involve empirical evaluation on specific datasets.

Key Insights and Ideas

  • Algebraic Characterization of Regular Functions: The most significant insight is providing a regular-expression-like algebraic framework for defining regular string transformations, moving beyond purely machine-based definitions.
  • The Power of Unambiguity: The combinators (especially split sum and iterated sum) enforce unique parsing, ensuring that combining functions results in a well-defined partial function. This is a key difference from simple set operations.
  • Chained Sum for Complex Interactions: The introduction of "chained sum" is a novel and powerful tool for capturing transformations where outputs from adjacent processed segments need to interact in specific ways, which simple composition or summation cannot achieve.
  • Bridging Machines and Algebra: The paper effectively connects the operational semantics of copyless cost register automata with the declarative power of algebraic combinators, offering a unified view of regular functions.
  • Importance of Non-Commutativity: The work highlights the necessity of additional combinators (left-additive versions, composition/chained sum) when dealing with non-commutative monoids, which are common in practical string processing.

Key Results

  • Commutative Monoids: Every regular function over a commutative monoid can be constructed from constant functions using choice, split sum, and iterated sum.
  • General Monoids: Every regular function over any monoid can be constructed using choice, sum, split sum, iterated sum, function composition (or chained sum), and their left-additive versions.
  • Equivalence with CCRAs: The paper formally defines copyless cost register automata (CCRA) and proves that the set of functions expressible by their combinators is exactly the set of functions computable by CCRAs.
  • Constructive Proofs: The paper provides constructive proofs showing how to translate between function expressions and CCRA machines, and how to build complex functions from simpler ones.

Limitations and Future Work

  • Minimality of Combinators: The authors conjecture that the set of combinators they identified is minimal for capturing all regular functions, but this remains an open problem.
  • Congruence and Myhill-Nerode: Developing a notion of congruence and a Myhill-Nerode-style characterization for regular functions is an open research question.
  • Extensions to Infinite Strings and Trees: The paper suggests exploring similar algebraic characterizations for transformations of infinite strings or trees.
  • Practical Language Development: The authors plan to develop a declarative language for document processing based on these regular combinators.

Summary updated

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.
BibTeX
@inproceedings{alur2014regular,
  author = {Rajeev Alur and Adam Freilich and Mukund Raghothaman},
  title = {{Regular combinators for string transformations}},
  booktitle = {CSL-LICS},
  year = {2014},
  url = {https://openreview.net/forum?id=ipKTlmPH16E},
}

Loading related content...

Figure