Universal quantification makes automatic structures hard to decide

Christoph Haase, Radoslaw Piórkowski

Automatic structures are first-order structures whose universe and relations can be represented as regular languages. It follows from the standard closure properties of regular lan…