Tags:Automatic Structures, Ordered Decision Diagrams and Symbolic Computation

Abstract:

In this work we introduce the notion of decisional width of a finite relational structure and the notion of regular-decisional width for regular classes of finite structures. We show that the validity problem for regular-decisional classes of structures is decidable. Building on this decidability result, we show that the problem of counting satisfying assignments for a first-order formula in a structure of constant width is fixed-parameter tractable with respect to the width parameter and can be solved in quadratic time with respect to the size of the representation.

On the Width of Regular Classes of Finite Structures