On the definition of "Algebraic Automata"

Question
,
#1

BCGL22 defines the algebraic automaton problem as follows:

image
image821×185 20.8 KB

BCGL22 also references SCGGRS19 as the source of this definition.

However, in SCGGRS19, we find the following:

image
image1049×407 59.6 KB

The key difference between the two definitions is that in the latter, we also have a set of boundary constraints which are required to hold.

Two questions:

  1. Are the two definitions equivalent?
  2. If so, can the boundary constraints be “externalized” for the pre-processing done in BCGL22?

(By externalization, I mean having the boundary constraints be part of the \mathbb{x} instance, rather than the index \mathbb{i})

1 Like
#2

It also seems that without boundary conditions, the relation is “trivial” in the sense that any execution trace consisting of entirely 0 will be in the language.

#3

Hello,

For your first question, yes the definitions for algebraic automata in [BCGL22] and [BCGGRS19] are not exactly the same. Note that in definition 8.1 they actually define “interactive R1CS automata”, and doing so makes it easier to reduce from algebraic machines later on. As for [BCGL22], we don’t worry about the machines case.

For the second question, yes I agree the definition is vague here, we’ll make it clearer. The “z” in Definition 7.1 of [BCGL22] is actually the same as the “z” for R1CS (Definition 1.1), where z=(x,w) for a public x, and a non-zero x would make the problem nontrivial.

Hope these help.

3 Likes