The standard Datalog features, whose expressiveness is well
understood on classical relational structures
[1]}, [2]}, need to be re-examined in the
presence of sequences; moreover, their interaction with the new
features needs to be understood as well. For example, consider
recursion versus equations, and the query that checks whether an
input sequence \(\$x\)  consists exclusively of \(a\) 's. (Path
variables are prefixed by a dollar sign.) With an equation we
can simply write \(\$x \cdot a = a \cdot \$x\)  (using the dot for
concatenation). Without equations (or other means to simulate
equations), however, this query can only
be expressed using recursion. For another example, consider
monadic versus higher-arity intermediate predicates.
Classically, there are well-known arity hierarchies for Datalog
[3]}. In our setting, however, a unary relation
can already hold arbitrary-length sequences, and indeed, using a
simple coding trick, we will see that the arity feature is
actually redundant.
