R1CS subset of PFCSes.
PFCSes generalize R1CSes; a subset of PFCSes corresponds to R1CSes. Here we characterize that subset.
We provide two related characterizations.
One is that of a PFCS that is an R1CS,
i.e. it has no definitions and all the constraints are in R1CS form.
Another is that of a PFCS that has definitions,
but all its equality constraints are in R1CS form,
and all its relation applications have constants or variables as arguments.
The latter kind of PFCS can be regarded as a structured R1CS:
the constraints are all in R1CS form in the end,
but they may be organized hierarchically, via defined relations.
We use the prefix
Our characterization of R1CS monomials, polynomials, and equality constraints is a natural one, but not necessarily the only one possible. In particular, PFCS expressions are trees, and there are many tree shapes that represent linear polynomials, besides the left-associated ones that we use here.