Symbolic Automatic Relations and Their Applications to SMT and CHC Solving
summary
Defines symbolic automatic relations that combine symbolic automata and automatic relations and proves they are closed under Boolean ops; shows satisfiability is undecidable in general but constructs a sound, incomplete checker by a reduction to CHC solving on integers. Implements a tool that encodes SAR-formulas to CHCs and runs backends Spacer, HoIce, Eldarica, and reports solving more instances on IsaPlanner, SAR_SMT and CHC benchmarks within 60s.
AI-written summary · about