## Modular Descriptions of Regular Functions

## Paul Gastin

LSV, ENS Paris-Saclay, CNRS, Université Paris-Saclay, France paul.gastin@ens-paris-saclay.fr

Abstract

We discuss various formalisms to describe string-to-string transformations. Many are based on automata and can be seen as operational descriptions, allowing direct implementations when the input scanner is deterministic. Alternatively, one may use more human friendly descriptions based on some simple basic transformations (e.g., copy, duplicate, erase, reverse) and various combinators such as function composition or extensions of regular operations.

2012 ACM Subject Classification Theory of computation → Transducers

Keywords and phrases string-to-string transducers, sequential functions, rational functions, regular functions, regular transducer expressions

We investigate string-to-string functions which are ubiquitous. A preprocessing that erases comments from a program, or a micro-computation that replaces a binary string with its increment, or a syntactic fix that reorders the arguments of a function to comply with a different syntax, are all examples of string-to-string transformations/functions. We discuss various ways of describing such functions and survey some of the main results.

Operationally, we need to parse the input string and to produce an output word. The simplest such mechanism is to use a deterministic finite-state automaton (1DFA) to parse the input from left to right and to produce the output along the way. These are called sequential transducers, or one-way input-deterministic transducers (1DFT), see e.g. [6, Chapter IV], [18, Chapter V] or [15]. Transitions are labelled with pairs a | u where a is a letter read from the input string and u is the word, possibly empty, to be appended to the output string. Sequential transducers allow for instance to strip comments from a latex file, see Figure 1. Transformations that can be realized by a sequential transducer are called sequential functions. A very important property of sequential functions is that they are closed under composition. This can be easily seen by taking a cartesian product of the two sequential transducers, synchronizing the output of the first transducer with the input of the second one. Also, each sequential function f can be realized with a canonical minimal sequential transducer A f which can be computed from any sequential transducer B realizing f . As a consequence, equivalence is decidable for sequential transducers.

With a sequential transducer, it is also possible to increment an integer written in binary if the string starts with the least significant bit (lsb), see Figure 2 left. On the other hand, increment is not a sequential function when the lsb is on the right. There are two possibilities to overcome this problem.

The first solution is to give up determinism when reading the input string. One-way input-nondeterministic finite-state transducers (1NFT) do not necessarily define functions. It

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.01137v1-figure-387ca9a3-d855-43b7-9bf1-d30f39b1b398.jpg)

/negationslash

Figure 1 A sequential transducer stripping comments from a latex file, where a, b, c ∈ Σ are letters from the input alphabet with b / ∈ {\ , % } and c = \ n .

Figure 2 Transducers incrementing a binary number.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.01137v1-figure-5d26079b-2b98-4e66-ab43-782d70a47fcb.jpg)

is decidable in PTIME whether a 1NFT defines a function [19, 17]. We give a proof below 1 which is mostly inspired from [6, Chapter IV].

We are interested in functional 1NFT (f1NFT). This is in particular the case when the transducer is inputunambiguous . Actually, one-way, input-unambiguous, finite-state transducers (1UFT) have the same expressive power as f1NFT [21]. We prove this result below when discussing regular look-ahead. For instance, increment with lsb on the right is realized by the 1UFT on Figure 2 right. Transformations realized by f1NFT are called rational functions. They are easily closed under composition. The equivalence problem is undecidable for 1NFT [16] but decidable in PTIME for f1NFT [19, 17]. This follows directly from the decidability of the functionality of 1NFTs: consider two f1NFTs A 1 and A 2 , first check whether dom ( A 1 ) = dom ( A 2 ), then check whether A /unionmulti 1 A 2 is functional. It is also decidable in PTIME whether a f1NFT defines a sequential function, i.e., whether it can be realized by a 1DFT [8, 21].

Interestingly, any rational function h can be written as r ◦ g ◦ r ◦ f where f, g are sequential functions and r is the reverse function mapping w = a a 1 2 · · · a n to w r = a n · · · a a 2 1 [13]. We provide a sketch of proof below. 2

1 Let A be a 1NFT with m states. We show that, if A is functional on all words of length ≤ 2 m 2 , then A is functional. Let w = a a 1 2 . . . a n ∈ dom ( A ) with n &gt; 2 m 2 . By induction, we assume that A is functional on all words of length &lt; n . Consider two accepting runs for w : p 0 a 1 -→ p 1 a 2 -→ p 2 · · · p n -1 a n - -→ p n and q 0 a 1 -→ q 1 a 2 -→ q 2 · · · q n -1 a n - -→ q n . Since n is large enough, we find 0 ≤ i &lt; j &lt; k ≤ n with ( p , q i i ) = ( p , q j j ) = ( p k , q k ). We split the input word w = w w w w 1 2 3 4 in four factors w 1 = a 1 · · · a i , w 2 = a i +1 · · · a j , w 3 = a j +1 · · · a k and w 4 = a k +1 · · · a n and we consider the ouputs x x x x 1 2 3 4 and y y y y 1 2 3 4 of the two accepting runs: p 0 w 1 | x 1 - - - -→ p i w 2 | x 2 - - - -→ p j w 3 | x 3 - - - -→ p k w 4 | x 4 - - - -→ p n and q 0 w 1 | y 1 - - - -→ q i w 2 | y 2 - - - -→ q j w 3 | y 3 - - - -→ q k w 4 | y 4 - - - -→ q n . The three repeated pairs allow us to consider shortcuts in the accepting paths. First we skip w w 2 3 and we get two accepting runs for the shorter word w w 1 4 : p 0 w 1 | x 1 - - - -→ p i = p k w 4 | x 4 - - - -→ p n and q 0 w 1 | y 1 - - - -→ q i = q k w 4 | y 4 - - - -→ q n . By induction, the outputs must be equal: x x 1 4 = y y 1 4 . Wlog we assume that y 1 is a prefix of x 1 and we obtain x 1 = y z 1 and zx 4 = y 4 for some z . Second, we skip w 3 and by induction the ouputs on the shorter word w w w 1 2 4 should be equal: x x x 1 2 4 = y y y 1 2 4 . Therefore, y zx x 1 2 4 = y y zx 1 2 4 and zx 2 = y z 2 . Similarly, skipping w 2 we get x x x 1 3 4 = y y y 1 3 4 and zx 3 = y z 3 . Finally, x x x x 1 2 3 4 = y zx x x 1 2 3 4 = y y zx x 1 2 3 4 = y y y zx 1 2 3 4 = y y y y 1 2 3 4 . Hence, A is functional on w

- 2 Assume that h is realized by a 1UFT B . Consider the unique accepting run q 0 a 1 | u 1 - - - -→ q 1 · · · q n -1 a n | u n - - - -→ q n of B on some input word w = a 1 · · · a n . We have h w ( ) = u 1 · · · u n . Let A be the DFA obtained with the subset construction applied to the input NFA induced by B . Consider the run X 0 a 1 -→ X 1 · · · X n -1 a n - -→ X n of A on w . We have q i ∈ X i for all 0 ≤ i ≤ n . The first sequential function f adorns the input word with the run of A : f ( w ) = ( X ,a 0 1 ) · · · ( X n -1 , a n ). The sequential transducer C realizing g is defined as follows. For each state q of B there is a transition δ = q ( X,a ) - - - -→ p in C if there is a unique p ∈ X such that δ ′ = p a - → q is a transition in B . Moreover, if δ ′ outputs u in B then δ outputs u r in C .

Notice that q n ( X n -1 ,a n ) | u r n - - - - - - - - -→ q n -1 · · · q 1 ( X ,a 0 1 ) | u r 1 - - - - - - -→ q 0 is a run of C producing u r n · · · u r 1 = h w ( ) r . The result follows.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.01137v1-figure-f9f2da35-efbc-45a2-a5e1-fb286b7f33f2.jpg)

- Figure 3 Two-way transducer incrementing a binary number.

In classical automata, whether or not a transition can be taken only depends on the input letter being scanned. This can be enhanced using regular look-ahead or look-behind. For instance, the f1NFT on the right of Figure 2 can be made deterministic using regular look-ahead. In state 1, when reading digit 0, we move to state 2 if the suffix belongs to 1 ∗ and we stay in state 1 otherwise, i.e., if the suffix belongs to 1 ∗ 0 { 0 1 , } ∗ . Similarly, we choose to start in the initial state 2 (resp. 1) if the word belongs to 1 ∗ (resp. 1 ∗ 0 0 1 { , } ∗ ). More generally, any f1NFT can easily be made deterministic using regular look-ahead: we consider an arbitrary total order &lt; on the set of states of the f1NFT and we select the least accepting path for the lexicographic ordering. If from state p reading a we have the choice between several transitions leading to states q 1 &lt; q 2 &lt; q 3 · · · , we select the least i such that the suffix can be accepted from q i . This query is indeed regular. We deduce that regular look-ahead increases the expressive power of one-way deterministic transducers.

Notice that a one-way transducer which is deterministic thanks to regular look-ahead can be easily transformed into a 1UFT. For instance, if a non-deterministic choice between p a,L 1 - - -→ q 1 and p a,L 2 - - -→ q 2 is resolved by the disjoint regular look-ahead L 1 and L 2 , then the 1UFT goes to q 1 (or q 2 ) and spans a copy of the automaton for L 1 (or L 2 ) to check that the suffix satisfies the correct look-ahead. We have actually proved that f1NFT and 1UFT have the same expressive power: starting with a f1NFT, we get a deterministic transducer using regular look-ahead, then we turn it into a 1UFT.

Remember that increment with lsb on the right is not a sequential function. The first solution was to use f1NFT or 1UFT as in Figure 2 right. The other solution is to keep input-determinism but to allow the transducer to move its input head in both directions, i.e., left or right (two-way). So we consider two-way input-deterministic finite-state transducers (2DFT) [1]. To realize increment of binary numbers with the lsb on the right with a 2DFT, one has to locate the last 0 digit, replace it with 1, keep unchanged the digits on its left and replace all 1's on its right with 0's. This is realized by the 2DFT of Figure 3. We use /turnstileleft , /turnstileright / ∈ Σ for the end-markers so the input tape contains /turnstileleft w /turnstileright when given the input word w ∈ Σ . ∗

Transformations realized by 2DFTs are called regular functions. They form a very robust class. Remarkably, regular functions are closed under composition [9], which is now a non trivial result. Actually, a 2DFT can be transformed into a reversible one of exponential size [11]. In a reversible transducer, computation steps can be deterministically reversed. As a consequence, the composition of two 2DFTs can be achieved with a single exponential blow-up. Also, contrary to the one-way case, input-nondeterminism does not add expressive power as long as we stay functional: given a f2NFT, one may construct an equivalent 2DFT [14]. Similarly, regular look-ahead and look-behind do not increase the expressive power of regular functions [14]. Moreover, the equivalence problem for regular functions is still

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.01137v1-figure-3471f5ba-5239-410a-b55d-8ec17ad733c7.jpg)

- Figure 4 One-way register transducer incrementing a binary number.
- Figure 5 Streaming string transducer incrementing a binary number.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.01137v1-figure-a725af78-2e0d-4cfc-8f88-918e69370b2c.jpg)

decidable [10].

Regular functions are also those that can be defined with MSO transductions [14], but we will not discuss this here.

By using registers, we obtain yet another formalism defining string-to-string transformations. For instance incrementing a binary number with lsb on the right is realized by the one-way register transducer on Figure 4. It uses two registers X,Y initialized with the empty string and 1 respectively and updated while reading the binary number. Register X keeps a copy of the binary number read so far, while Y contains its increment. The final output of the transducer is the string contained in register Y . This register automaton is a special case of ' simple programs ' defined in [9]. In these simple programs, a register may be reset to the empty string, copied to another register, or updated by appending a finite string. The input head is two-way and most importantly simple programs may be composed. Simple programs coincide in expressive power with 2DFTs [9], hence define once again the class of regular functions.

Notice that when reading digit 0, the transducer of Figure 4 copies the string stored in X into Y without resetting X to ε . By restricting to one-way register automata with copyless updates (e.g., not of the form Y := X 1; X := X 0 where the string contained in X is duplicated) but allowing concatenation of registers in updates (e.g., Z := Z X X 0 ; := ε ), we obtain another kind of machines, called copyless streaming string transducers (SST), once again defining the same class of regular functions [3]. Continuing our example, incrementing a binary number with lsb on the right can be realized with the SST on Figure 5. It uses three registers X,Y,Z initialized with the empty string and updated while reading the binary number. Register X keeps a copy of the last sequence of 1's while register Y contains a sequence of 0's of same length. Now register Z keeps a copy of the input read so far up to, and excluding, the last 0. Hence, the increment of the binary number read so far is given by Z Y 1 which is the final output of the transducer. If the input number is 1 n then the computation ends in state 1 with Y = 0 n and Z = . Hence the final ouput is ε Z Y 1 = 10 n . Similarly, if the input number is of the form w 01 n then the run ends in state 2 with Z = w and Y = 0 n : the final output is Z Y 1 = w 10 n .

The above machines provide a way of describing string-to-string transformations which is not modular. Describing regular functions in such devices is difficult, and it is even more difficult to understand what is the function realized by a 2DFT or an SST. We discuss now

more compositional and modular descriptions of regular functions. Such a formalism, called regular list functions, was described in [7]. It is based on function composition together with some natural functions over lists such as reverse, append, co-append, map, etc. Here we choose to look at combinators derived from regular expressions.

The idea is to start from basic functions, e.g., (1 | 0) means 'read 1 and output 0', and to apply simple combinators generalizing regular expressions [4, 2, 12, 5]. For instance, using the Kleene iteration, (1 | 0) ∗ describes a function which replaces a sequence of 1's with a sequence of 0's of same length. Similarly, copy := ((0 | 0) + (1 | 1)) ∗ describes a regular function which simply copies an input binary string to the output. Now, incrementing a binary number with lsb on the right is described with the expression increment0 := copy · (0 | 1) · (1 | 0) ∗ , assuming that the input string contains at least one 0 digit. If the input string belongs to 1 , we may use the expression ∗ increment1 := ( ε | 1) · (1 | 0) ∗ . Notice that such a regular transducer expression (RTE) defines simultaneously the domain of the regular function as a regular expression, e.g., dom increment0 ( ) = (0 + 1) ∗ 01 , and the output to be produced. ∗ The input regular expression explains how the input should be parsed. If the input regular expression is ambiguous, parsing the input word is not unique and the expression may be non functional. For instance, copy · (1 | 0) ∗ is ambiguous. The input word w = 1011 may be parsed as 10 · 11 or 101 · 1 or 1011 · ε resulting in the outputs 1000 or 1010 or 1011 respectively. On the other end, increment := increment0 + increment1 has an unambiguous input regular expression.

Simple RTEs are defined by the syntax

$$f, g \, \vdots = \left ( u, v \right ) \, | \, f + g \, | \, f \cdot g \, | \, f ^ { * }$$

where u is a finite input word, v is a finite output word, and the rational operations should be unambiguous. For instance, f ∗ is unambiguous if for all input words w , there is at most one factorization w = u u 1 2 · · · u n with u i ∈ dom ( f ). Simple RTEs define precisely the rational functions (f1NFT or 1UFT). This follows from a more general result: the equivalence of weighted automata and rational series, usually referred to as the Kleene-Schützenberger theorem [20], applied to the semiring of rational languages and restricted to unambiguous weighted automata.

↦

↦

A 2DFT may easily duplicate the input word, defining the function w → w # , which w cannot be computed with a sequential transducer or a f1NFT. In addition to the classical regular combinators (+ for disjoint union, · for unambiguous concatenation or Cauchy product, ∗ for unambiguous Kleene iteration), we add the Hadamard product ( f /circledot g )( w ) = f w ( ) · g w ( ) where the input word is read twice, first producing the output computed by f then the output computed by g . Hence the function duplicating its input can be simply written as duplicate := ( copy · ( ε | #)) /circledot copy . The Hadamard product also allows to exchange two strings u # v → vu where u, v ∈ { 0 1 , } ∗ . Let erase := ((0 | ε ) + (1 | ε )) ∗ and

$$\text{exchange} \coloneqq \left ( \text{erase} \cdot \left ( \# \left | \, \varepsilon \right ) \cdot \text{copy} \right ) \odot \left ( \text{copy} \cdot \left ( \# \left | \, \varepsilon \right ) \cdot \text{erase} \right ).$$

A 2DFT may also scan its input back and forth in pieces. This was used in the 2DFT of Figure 3 to locate the last 0 of the input. This is also needed to realize the regular function h defined by

↦

$$h \colon u _ { 1 } \# u _ { 2 } \# u _ { 3 } \# \cdots u _ { n } \# \mapsto u _ { 2 } u _ { 1 } \# u _ { 3 } u _ { 2 } \# \cdots u _ { n } u _ { n - 1 } \#$$

where u , . . . , u 1 n ∈ { 0 1 , } ∗ and n &gt; 1. It is easy to build a 2DFT realizing h , but this regular function cannot be expressed using the regular combinators +, · , ∗ , /circledot . On the other hand, we show that h can be expressed with the help of composition. First, we iterate the function

## Modular Descriptions of Regular Functions

duplicate on a #-separated sequence of binary words with the RTE f := ( duplicate · (# | #)) . ∗ We have

↦

$$f \colon u _ { 1 } \# u _ { 2 } \# u _ { 3 } \# \cdots u _ { n } \# \mapsto u _ { 1 } \# u _ { 1 } \# u _ { 2 } \# u _ { 2 } \# u _ { 3 } \# u _ { 3 } \# \cdots u _ { n } \# u _ { n } \#$$

when u , . . . , u 1 n are binary strings. Next, we erase the first u 1 and the last u n and we exchange the remaining consecutive pairs with the RTE

$$g \coloneqq erase \cdot ( \# \, | \, \varepsilon ) \cdot ( \text{exchange} \cdot ( \# \, | \, \# ) ) ^ { * } \cdot erase \cdot ( \# \, | \, \varepsilon ) \,.$$

↦

↦

We have g ◦ f : u 1 # u 2 # u 3 # · · · u n # → u u 2 1 # u u 3 2 # · · · u u n n -1 #. Hence, h = g ◦ f . Another crucial feature of 2DFTs is their ability to reverse the input, i.e., to implement the function reverse : a a 1 2 · · · a n → a n · · · a a 2 1 . We add the basic function reverse to our expressions and we obtain RTEs with composition, Hadamard product and reverse (chr-RTE) following the syntax:

$$f, g \, \vdots = \, \text{reverse} \, | \, ( u, v ) \, | \, f + g \, | \, f \cdot g \, | \, f ^ { * } \, | \, f \odot g \, | \, f \circ g$$

where u is a finite input word, v is a finite output word, and the rational operations +, · , ∗ should be unambiguous. It turns out that regular functions (2DFTs) are exactly those that can be described with chr-RTEs. Further, we may remove the Hadamard product if we provide duplicate as a basic function. Indeed, we can easily check that f /circledot g = ( f · (# | ε ) · g ) ◦ duplicate . We obtain RTEs with composition, duplicate and reverse (cdr-RTE) following the syntax:

$$f, g \, \left \| \colon = \, \text{reverse} \, \left | \, \text{duplicate} \, \left | \, ( u, v ) \, \right | \, f + g \, \left | \, f \cdot g \, \right | \, f ^ { * } \, \left | \, f \circ g \,.$$

Once again, cdr-RTEs define exactly the class of regular functions. We believe that both chr-RTE and cdr-RTE form very convenient, compositional and modular formalisms for defining regular functions.

An alternative solution to the fact that the regular function h defined above cannot be described using the regular combinators +, · , ∗ , /circledot was proposed in [4]. Instead of using composition, they introduced a 2-chained Kleene iteration: [ K,f ] 2+ first unambiguously parses an input word as w = u u 1 2 · · · u n with u , . . . , u 1 n ∈ K and then apply f to all consecutive pairs of factors, resulting in the output f ( u u 1 2 ) f ( u u 2 3 ) · · · f ( u n -1 u n ). For instance, with the functions defined above, we can easily check that h = [ K,f ] 2+ with K = 0 1 { , } ∗ # and f := exchange · (# | #).

We show that the 2-chained Kleene iteration [ K,f ] 2+ can be expressed if we allow composition of functions in addition to the regular combinators +, · , ∗ , /circledot . First, consider an unambiguous regular expression for the regular language K in which we replace each atomic letter a with ( a | a ). We obtain a simple RTE f K with domain K and which is the identity on its domain K . Now consider the function g K defined by the simple RTE g K = ( f K · ( ε | #)) . When an input word ∗ w can be unambiguously parsed as w = u u 1 2 · · · u n with u , . . . , u 1 n ∈ K , we get g K ( w ) = u 1 # u 2 # · · · u n #. As above, we consider the function g := ( duplicate · (# | #)) ∗ so that ( g ◦ g K )( w ) = u 1 # u 1 # u 2 # u 2 # u 3 # u 3 # · · · u n # u n #. With a further composition, we erase the first u 1 and the last u n and we apply f to the remaining consecutive pairs with the RTE

$$h \coloneqq \text{erase} \cdot ( \# \left | \, \varepsilon ) \cdot ( f \circ ( \text{copy} \cdot ( \# \left | \, \varepsilon ) \cdot \text{copy} \cdot ( \# \left | \, \varepsilon ) ) ) ^ { * } \cdot \text{erase} \cdot ( \# \left | \, \varepsilon ) \,.$$

We obtain [ K,f ] 2+ = h ◦ g ◦ g K . Therefore, regular functions described by RTEs using combinators +, · , ∗ , /circledot , 2+ can be expressed with ch-RTEs using combinators +, · , ∗ , /circledot , ◦ or cd-RTEs using duplicate instead of the Hadamard product.

Since the regular function reverse cannot be expressed with the regular combinators +, · , ∗ , /circledot and 2+, reversed versions of Kleene star and 2-chained Kleene iteration were also introduced in [4]. The reversed Kleene star r -∗ parses the input word from left to right but produces the output in reversed order. For instance, f r -∗ ( w ) = f ( u n ) · · · f ( u 2 ) f ( u 1 ) if the input word is unambiguously parsed as w = u u 1 2 · · · u n with u i ∈ dom ( f ). Hence, reversing a binary string is described with the expression ((0 | 0) + (1 | 1)) r -∗ .

Conversely, the reversed Kleene star can be expressed with the basic function reverse and composition: f r -∗ = ( f ◦ reverse ) ∗ ◦ reverse . Indeed, assume that an input word is unambiguously parsed as w = u u 1 2 · · · u n when applying f r -∗ resulting in f u ( n ) · · · f u ( 2 ) f u ( 1 ). Then, reverse ( w ) = w r is unambiguously parsed as u r n · · · u u r 2 r 1 when applying ( f ◦ reverse ) ∗ . The result follows since ( f ◦ reverse )( u r ) = f ( u ).

There is also a reversed version of the two-chained Kleene iteration. With the above notation, we get [ K,h ] r -2+ ( w ) = h u ( n -1 u n ) · · · h u u ( 2 3 ) h u u ( 1 2 ) when the input word can be unambiguously parsed as w = u u 1 2 · · · u n with u , . . . , u 1 n ∈ K .

Once again, we obtain an equivalent formalism for describing regular functions: the regular transducer expressions using +, · , /circledot , ∗ , r -∗ , 2+, r -2+ as combinators [4, 2, 12, 5]:

$$f, g \, \left \colon = \left ( u, v \right ) \left | \, f + g \, \left | \, f \cdot g \, \right | \, f ^ { * } \, \left | \, f \odot g \, \right | \, f ^ { r \, * } \, \left | \, [ K, f ] ^ { 2 + } \, \left | \, [ K, f ] ^ { r \, - 2 + } \,.$$

To conclude, we have seen various formalisms for describing string to string transformations. With increasing expressive power, we have sequential functions (1DFT), rational functions (f1NFT or 1UFT or 1DFT with regular look-ahead or simple RTE), and regular functions. Each class of functions is closed under composition and its equivalence problem is decidable. The robust and expressive class of regular functions can be described with various machine models such as 2DFT or 2UFT or f2NFT or SST. It also admits compositional descriptions based on regular combinators. We believe that using function composition instead of the technically involved 2-chained Kleene iteration makes the descriptions much easier. Hence, we advocate the use of chr-RTEs or cdr-RTEs as described above.

## References

- 1 A.V. Aho and J.D. Ullman. A characterization of two-way deterministic classes of languages. Journal of Computer and System Sciences , 4(6):523-538, Dec 1970.
- 2 Rajeev Alur, Loris D'Antoni, and Mukund Raghothaman. DReX: A declarative language for efficiently evaluating regular string transformations. In Sriram K. Rajamani and David Walker, editors, Proceedings of the 42nd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages - POPL '15 , pages 125-137. ACM Press, 2015.
- 3 Rajeev Alur and Jyotirmoy V. Deshmukh. Nondeterministic streaming string transducers. In Luca Aceto, Monika Henzinger, and Jiří Sgall, editors, Automata, Languages and Programming , pages 1-20, Berlin, Heidelberg, 2011. Springer Berlin Heidelberg.
- 4 Rajeev Alur, Adam Freilich, and Mukund Raghothaman. Regular combinators for string transformations. In Thomas A. Henzinger and Dale Miller, editors, Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the TwentyNinth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), CSL-LICS '14, Vienna, Austria, July 14 - 18, 2014 , pages 9:1-9:10. ACM, 2014.
- 5 Nicolas Baudru and Pierre-Alain Reynier. From two-way transducers to regular function expressions. In Mizuho Hoshi and Shinnosuke Seki, editors, Developments in Language Theory , pages 96-108, Cham, 2018. Springer International Publishing.
- 6 Jean Berstel. Transductions and Context-Free Languages . Leitfäden der angewandten Mathematik und Mechanik. Vieweg+Teubner Verlag, 1979.

## Modular Descriptions of Regular Functions

- 7 Mikołaj Bojańczyk, Laure Daviaud, and Shankara Narayanan Krishna. Regular and first-order list functions. In Anuj Dawar and Erich Grädel, editors, Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science - LICS '18 , pages 125-134. ACM Press, 2018.
- 8 Christian Choffrut. Une caractérisation des fonctions séquentielles et des fonctions sousséquentielles en tant que relations rationnelles. Theoretical Computer Science , 5(3):325-337, Dec 1977.
- 9 Michal P. Chytil and Vojtěch Jákl. Serial composition of 2-way finite-state transducers and simple programs on strings. In Arto Salomaa and Magnus Steinby, editors, Automata, Languages and Programming: Fourth Colloquium, University of Turku, Finland July 18-22, 1977 , pages 135-147, Berlin, Heidelberg, 1977. Springer Berlin Heidelberg.
- 10 Karel Culik and Juhani Karhumäki. The equivalence of finite valued transducers (on HDT0L languages) is decidable. Theoretical Computer Science , 47:71-84, 1986.
- 11 Luc Dartois, Paulin Fournier, Ismaël Jecker, and Nathan Lhote. On reversible transducers. In Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl, editors, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) , volume 80 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 113:1-113:12, Dagstuhl, Germany, 2017. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.
- 12 Vrunda Dave, Paul Gastin, and Shankara Narayanan Krishna. Regular Transducer Expressions for Regular Transformations. In Martin Hofmann, Anuj Dawar, and Erich Grädel, editors, Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic In Computer Science (LICS'18) , pages 315-324, Oxford, UK, July 2018. ACM Press.
- 13 C. C. Elgot and J. E. Mezei. On relations defined by generalized finite automata. IBM Journal of Research and Development , 9(1):47-68, Jan 1965.
- 14 Joost Engelfriet and Hendrik Jan Hoogeboom. MSO definable string transductions and two-way finite-state transducers. ACM Transactions on Computational Logic , 2(2):216-254, Apr 2001.
- 15 Emmanuel Filiot and Pierre-Alain Reynier. Transducers, logic and algebra for functions of finite words. SIGLOG News , 3(3):4-19, 2016.
- 16 T. V. Griffiths. The unsolvability of the equivalence problem for lambda-free nondeterministic generalized machines. Journal of the ACM , 15(3):409-413, Jul 1968.
- 17 Eitan M. Gurari and Oscar H. Ibarra. A note on finite-valued and finitely ambiguous transducers. Mathematical Systems Theory , 16(1):61-66, Dec 1983.
- 18 Jacques Sakarovitch. Elements of Automata Theory . Cambridge University Press, 2009.
- 19 M. P. Schützenberger. Sur les relations rationnelles. In Automata Theory and Formal Languages 2nd GI Conference Kaiserslautern, May 20-23, 1975 , pages 209-213. Springer Berlin Heidelberg, 1975.
- 20 Marcel Paul Schützenberger. On the definition of a family of automata. Information and Control , 4(2-3):245-270, Sep 1961.
- 21 A. Weber and R. Klemm. Economy of description for single-valued transducers. Information and Computation , 118(2):327-340, May 1995.
Paul Gastin
Modular Descriptions of Regular Functions
We discuss various formalisms to describe string-to-string transformations.
Many are based on automata and can be seen as operational descriptions,
allowing direct implementations when the input scanner is deterministic.
Alternatively, one may use more human friendly descriptions based on some
simple basic transformations (e.g., copy, duplicate, erase, reverse) and
various combinators such as function composition or extensions of regular
operations.