Name
Abstract | ||
|---|---|---|
Functional MSO transductions, deterministic two-way transducers, as well as streaming string transducers are all equivalent models for regular functions. In this paper, we show that every regular function, either on finite words or on infinite words, captured by a deterministic two-way transducer, can be described with a regular transducer expression (RTE ). For infinite words, the two-way transducer uses Muller acceptance and ω-regular look-ahead. RTEs are constructed from constant functions using the combinators if-then-else (deterministic choice), Hadamard product, and unambiguous versions of the Cauchy product, the 2-chained Kleene-iteration and the 2-chained omega-iteration. Our proof works for transformations of both finite and infinite words, extending the result on finite words of Alur et al. in LICS'14. |
Year | DOI | Venue |
|---|---|---|
2022 | 10.1016/j.ic.2020.104655 | Information and Computation |
DocType | Volume | ISSN |
Journal | 282 | 0890-5401 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Vrunda Dave | 1 | 6 | 2.83 |
| Paul Gastin | 2 | 0 | 0.34 |
| Shankara Narayanan Krishna | 3 | 0 | 0.34 |