  Despite the recent advance of automated program verification, reasoning about
recursive data structures remains as a challenge for verification tools and
their backends such as SMT and CHC solvers. To address the challenge, we
introduce the notion of symbolic automatic relations (SARs), which combines
symbolic automata and automatic relations, and inherits their good properties
such as the closure under Boolean operations. We consider the satisfiability
problem for SARs, and show that it is undecidable in general, but that we can
construct a sound (but incomplete) and automated satisfiability checker by a
reduction to CHC solving. We discuss applications to SMT and CHC solving on
data structures, and show the effectiveness of our approach through
experiments.
