Summary
Some problems involve checking many conditions on data that can be very large and complicated, but described in a simple way. The authors show that when these descriptions follow certain mathematical rules called edge operations, it is possible to solve the problems efficiently, in polynomial time. They provide new methods to convert complex descriptions into simpler forms that can be handled quickly by computers. These results also help recognize special structures called graphoids, which relate to graph theory and automata, without needing restrictive assumptions. This work answers some open questions about which cases of these constraint problems can be solved quickly and how to represent their solutions compactly.
finite automataconstraint satisfactionpolynomial timeedge operationfew subpowersMal'tsev operationgraphoid automataautomata compilationgraph-widthinvariant relations
Abstract
Finite automata can describe relations of unbounded arity that are exponentially larger than their descriptions. We prove that constraint satisfaction for such relations is solvable in polynomial time whenever their length slices are preserved by a common fixed edge operation on a finite domain. The algorithm computes compact representations of the complete solution relation and its projections. Its main ingredient is a polynomial-time compilation of nondeterministic finite automata into the fork witnesses and small projections required by the few-subpowers algorithm. In the Mal'tsev case, a direct proof is polynomial also when the domain and operation table are supplied as input, answering the Mal'tsev tractability question for automatic constraint satisfaction. We also characterize all invariant relations of a family of 3-edge algebras with neither Mal'tsev nor near-unanimity terms. Their normal forms combine Boolean activity constraints with affine value spaces and yield canonical quadratic-bit representations constructible from NFAs or arbitrary generators. For graphoid automata, these results give polynomial-time recognition without a graph-width restriction, effective boundary composition, and comparison of finite graph relations. The quadratic boundary bounds are optimal in the worst case. A fixed three-state example separates polynomial-time recognition from hard exact counting.