RECORD
On the growth rate of polyregular functions
Logic in Computer Science · Submitted 22 Dec 2022
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim We prove that a polyregular function has output size $\mathcal O(n^k)$ if and only if it can be defined by an MSO interpretation of dimension $k$, i.e. a string-to-string transformation where every output position is interpreted, using monadic second-order logic MSO, in some $k$-tuple of input positions.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
We consider polyregular functions, which are certain string-to-string functions that have polynomial output size. We prove that a polyregular function has output size $\mathcal O(n^k)$ if and only if it can be defined by an MSO interpretation of dimension $k$, i.e. a string-to-string transformation where every output position is interpreted, using monadic second-order logic MSO, in some $k$-tuple of input positions. We also show that this characterization does not extend to pebble transducers, another model for describing polyregular functions: we show that for every $k \in \{1,2,\ldots\}$ there is a polyregular function of quadratic output size which needs at least $k$ pebbles to be computed.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | We consider polyregular functions, which are certain string-to-string functions that have polynomial output size. | background 0.99 | 0.09 | 0.03 | asserted 0.97 |
| s1 | We prove that a polyregular function has output size $\mathcal O(n^k)$ if and only if it can be defined by an MSO interpretation of dimension $k$, i.e. a string-to-string transformation where every output position is interpreted, using monadic second-order logic MSO, in some $k$-tuple of input positions. | result 0.98 | 0.95 | 0.83 | asserted 1.00 |
| s2 | We also show that this characterization does not extend to pebble transducers, another model for describing polyregular functions: we show that for every $k \in \{1,2,\ldots\}$ there is a polyregular function of quadratic output size which needs at least $k$ pebbles to be computed. | result 0.72 | 0.96 | 0.14 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v3
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
We consider polyregular functions, which are certain string-to-string functions that have polynomial output size. We prove that a polyregular function has output size $\mathcal O(n^k)$ if and only if it can be defined by an MSO interpretation of dimension $k$, i.e. a string-to-string transformation where every output position is interpreted, using monadic second-order logic MSO, in some $k$-tuple of input positions. We also show that this characterization does not extend to pebble transducers, another model for describing polyregular functions: we show that for every $k \in \{1,2,\ldots\}$ there is a polyregular function of quadratic output size which needs at least $k$ pebbles to be computed.
Human review
How the literature uses it
4 arXiv papers cite this in 10 sentences
Papers citing it · 6 sentences without a confident label
Uses its method or tool 1 paper
-
(Our use of the blocks of $$s is inspired by the coding of atom-oblivious functions in the Deatomization Theorem of [ref] , cf. Remark [ref].)
Refutations of pebble minimization via output languages · Proof of Theorem [ref] · 0.96
Compares with it 1 paper
-
This result is an analogue of the various “pebble minimization theorems” that were shown for word-to-word polyregular functions [ref] .
Z-polyregular functions · Introduction · 0.90
Cites it as support 1 paper
-
Definitely not, as Bojańczyk recently showed [ref] : no number of pebbles suffices to compute all polyregular functions with quadratic growth (but those of linear growth require a single pebble).
Refutations of pebble minimization via output languages · Introduction · 0.99
Cites it as background 1 paper
-
These were a central topic of the work of Douéneau-Tabot in his Ph.D. thesis [ref] , proving optimization results for pebble transducers [ref] that fail in the general case [ref] .
$\mathbb{N}$-polyregular functions arise from well-quasi-orderings · Introduction · 0.92
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.