PaperlayerView exact revision on arXiv

Source-linked AI summary

Automatic constraints with few subpowers and graphoid recognition

Antonios Kalampakas

arXiv:2609.07891v1cs.LOcs.FL

TL;DR

Finite automata can describe relations exponentially larger than their descriptions, posing a challenge for constraint algorithms that operate on explicit tuples. The paper compiles NFAs into witnesses and compact representations, and proves polynomial-time tractability when the relations’ length slices share an edge operation. It also gives a quadratic-bit normal form for a specific 3-edge family and applies the results to graphoid recognition, while separating recognition from exact counting.

  • Problem

    Automata can succinctly describe relations with exponentially many tuples, beyond the direct reach of algorithms polynomial in the number of allowed tuples.

    Source: §1 · p. 1

  • Method

    The paper compiles NFAs into fork and bounded-projection witnesses, then uses algebraic algorithms to represent solution relations and projections compactly.

    Source: §1 · p. 2, §2 · p. 5

  • Results

    The paper proves polynomial-time constraint solving for shared edge-preserved slices, gives canonical quadratic-bit representations for a 3-edge family, and shows a three-state graphoid automaton with polynomial-time recognition but #P-complete counting.

    Source: §1 · p. 2, §7 · p. 21

  • Takeaways & Limitations

    For graphoid automata, the results provide polynomial-time recognition without a graph-width restriction and effective operations on compact boundary summaries.

    Source: §1 · p. 2, §6 · p. 18

    Extending the compilation beyond NFAs requires descriptions that permit polynomial-time extraction of all fork and bounded-projection witnesses.

    Source: §8 · p. 22

Abstract

from arXiv · show

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.

1. Introduction

Finite automata succinctly describe relations too large for tuple-by-tuple algorithms, so the paper connects automaton representations to algebraic structure. It compiles automata into the witnesses needed for polynomial-time constraint algorithms, then gives an explicit normal form for a family of 3-edge algebras and applies the results to graphoid recognition.

1. Introduction

  • Nondeterministic finite automata provide fork witnesses and bounded-projection witnesses, the information required by the few-subpowers algorithm.Fork witnesses are found using synchronous products; independent accepting suffixes complete the words.Source: §1 · pp. 1–2
  • The resulting algorithm handles arbitrarily many constraints, unbounded arities, and repeated scope variables, while representing the full solution relation and its projections compactly.For fixed domain and an ℓ-edge operation, a relation on k output coordinates uses O(kℓ−1) tuples; for Mal’tsev operations, O(k) tuples and O(k2) bits suffice.Source: §1 · p. 2
  • The Mal’tsev result answers an automatic constraint satisfaction tractability question and extends the conclusion to fixed finite algebras with few subpowers.Its model uses explicit scopes and relations formed by intersecting a regular language with a power of the finite domain.Source: §1 · p. 2
  • The 3-edge family’s invariant relations combine Boolean activity constraints with compatible affine value spaces, yielding canonical quadratic-bit encodings from NFAs or arbitrary generators.The normal form also supports a calculus using 2-SAT and Gaussian elimination; its quadratic bound is optimal.Source: §1 · p. 2
  • For graphoid automata, the theorem gives polynomial-time recognition without a graph-width restriction and supports effective composition of compact boundary summaries.A fixed three-state example separates polynomial-time recognition from hard exact counting.Source: §1 · p. 3
  • The main contributions are a polynomial-time compilation of automata for edge-preserved slices and an explicit normal form for a family of 3-edge algebras.The family has neither Mal’tsev nor near-unanimity terms.Source: §1 · pp. 2–3

2. Regular constraints and witness extraction

The section develops two complementary ways to extract useful witnesses from an NFA: forks record values that can follow a shared prefix, while bounded projections record possible values on selected coordinates. Both constructions run in polynomial time and provide the information needed for compact representations.

2. Regular constraints and witness extraction

  • A fork at coordinate i records two accepted words that agree before i and have prescribed letters at i.The definition includes diagonal forks, where the prescribed letters coincide.Source: §2 · p. 4
  • A layered synchronous product computes common prefixes, and stored accepting suffixes complete a witness pair for each realized fork.Keeping one pair per fork retains at most 2rd2 words, with a polynomial-time construction.Source: §2 · p. 4
  • Layered reachability with prescribed letters decides whether a selected-coordinate tuple occurs in the relation and returns a full accepted-word witness.For any fixed number c of selected coordinates, witnesses for all realized projections onto at most c coordinates can be computed in polynomial time.Source: §2 · pp. 4–5
  • Projection witnesses capture values on a small coordinate set, while fork witnesses capture exchanges after a common prefix; together they support compact generation for edge operations.Fork witnesses also permit compact generation for Mal’tsev operations.Source: §2 · p. 5

3. The Mal’tsev case

For Mal’tsev-preserved automatic constraints, the paper compiles each NFA relation into a compact frame and updates frames using equality, products, and projections. This yields polynomial-time satisfiability and compact representations of the complete solution relation and ordered boundary projections, including when the domain and operation table are inputs.

3. The Mal’tsev case

  • Frames exactly preserve a relation’s fork signature, and for a Mal’tsev-closed relation their generated closure is the full relation.Automaton fork extraction therefore gives a compact representation without calling the operation table during compilation.Source: §3 · p. 5
  • Frame operations support small projections, prefix restrictions, equality updates, Cartesian products, and arbitrary ordered projections with repeated coordinates.Small projections and equality updates suffice for the polynomial-time calculus.Source: §3 · pp. 6–7
  • Theorem 3.7 decides satisfiability and computes frames for the full solution relation and any explicit ordered boundary list in polynomial time.The theorem applies both to fixed domain and operation and when the domain and full Mal’tsev table are input, subject to the preservation promise.Source: §3 · p. 7
  • Each new constraint is incorporated by taking a product, imposing coordinate equalities, and projecting back, even for unbounded scopes and repeated variables.The algorithm uses only binary equality updates; the final frame is empty exactly when the instance is unsatisfiable.Source: §3 · p. 7
  • For a fixed NFA whose slices are preserved by a Mal’tsev operation, automatic constraint satisfaction is in P, answering the cited tractability question.With the operation table supplied as input, the algorithm remains polynomial under the promise that the operation preserves the supplied relations.Source: §3 · pp. 7–8

4. Edge operations and few subpowers

For fixed finite domains and edge operations, automatic constraint satisfaction is polynomial-time solvable when each used length slice is preserved, with compact representations of solutions and boundary relations. The key step compiles automata-described slices into the witnesses required by the few-subpowers algorithm.

4. Edge operations and few subpowers

  • Automaton slices are compiled into compact edge representations by retaining minority-fork witnesses and witnesses for every projection on fewer than ℓ coordinates.These representations generate the entire slice under the edge operation; the construction uses polynomially many reachability tests for fixed domain and ℓ.Source: §4 · p. 9
  • Compact representations support polynomial-time products, coordinate identifications, and arbitrary ordered projections, including projections with repeated coordinates.Products combine witnesses from each factor, while identifications use equality and ordered projections are reduced to identification followed by prefix projection.Source: §4 · pp. 9–10
  • A fixed finite domain and ℓ-edge operation yield polynomial-time constraint solving and compact solution and boundary relations when the used slices are preserved.Repeated variables are allowed in scopes and boundary lists; a length-k boundary relation has a representation with at most Bℓ,d(k) tuples.Source: §4 · p. 10
  • The result also applies to slices invariant under a fixed finite algebra with few subpowers, since its term operations preserve them and an edge term exists.This is a fixed-algebra statement, not a uniform procedure for discovering edge terms from arbitrary input algebras; with fixed D and e, the polynomial exponent may depend on ℓ.Source: §4 · pp. 8, 10
  • Boundary-relation inclusion and equality are decidable in polynomial time, failed inclusion yields a witness tuple, and solutions can be enumerated with polynomial delay and space.These conclusions also hold semiuniformly in the Mal’tsev setting described by the cited theorem.Source: §4 · p. 10
  • For fixed operation arity, preservation of every length slice by a complete DFA is polynomial-time decidable, but general NFA algorithms rely on the preservation promise.The DFA test searches a synchronous product for a path whose input copies accept while the output copy rejects.Source: §4 · pp. 10–11

5. Canonical quadratic representations for a 3-edge family

For the fixed prime-field 3-edge family, invariant relations have canonical representations combining Boolean activity constraints with affine value spaces, computable from NFAs or explicit generators and composable for solution relations and boundary projections. For Γp, pp-definability is characterized by ep-closure, with normal forms yielding polynomial-time short definitions and a quadratic worst-case bit bound.

The 3-edge family

  • The operation ep is a 3-edge operation whose algebra has neither a Mal’tsev term nor a near-unanimity term.Its derived term µp preserves activity from its first input and masks the second input’s value by that activity.Source: §5 · p. 11

Invariant-relation structure

  • Invariant relations pair a majority-closed activity relation Q with affine value fibres compatible with activity masks; their value spaces factor across coordinate classes with equal activity functions.The canonical affine space has an affine factor on always-active coordinates and linear factors on variable activity classes; inactive coordinates carry zero values.Source: §5 · pp. 11–12

Canonical normal forms

  • Every ep-closed relation has a canonical O(k^2)-bit normal form, computable in polynomial time from a preserving NFA or an explicit tuple set.The code stores unary and binary activity projections and a reduced row-echelon description of the affine value space.Source: §5 · p. 13

Computing normal forms

  • NFA compilation computes activity projections by pinned reachability and the exact affine hull by searching for accepted words that violate its defining equations.Each successful search increases affine dimension, so at most k additions and O(k^2) equation tests are needed; preservation is used to reconstruct the relation from these data.Source: §5 · p. 13

Normal-form calculus

  • Products, intersections, coordinate identifications, and ordered projections are polynomial-time operations on normal forms, yielding canonical representations of automatic-instance solutions on any ordered boundary.The stated conservative total bound is O((N + k + 1)^5), where N is instance size and k is boundary length.Source: §5 · pp. 15–16

5. Canonical quadratic representations for a 3-edge family

  • Over Γp, pp-definable relations are exactly the ep-closed relations, with polynomial-time definitions using O(k^2) atoms and auxiliary variables from their normal forms.The quadratic normal-form bit bound is optimal in the worst case.Source: §5 · p. 17
  • The construction uses activity constraints and Gaussian elimination, realizing affine and homogeneous equations as chains of Sp constraints.Each addition constraint equates its three activity bits, so a homogeneous chain is either inactive or active and enforces its equation when active.Source: §5 · p. 17
  • For fixed p, the canonical normal-form encoding requires Ω(k^2) bits in the worst case.Distinct invariant relations arise from distinct matrices; an injective encoding must distinguish them, and odd arities follow by appending an active coordinate fixed to zero.Source: §5 · pp. 17–18
  • The canonical table-and-matrix code uses O(k^2) bits, versus O(k^2 log(k + 2)) bits for an ordinary encoding of the resulting formula.Applying Proposition 5.6 after the construction from generators in Theorem 5.4 gives the short-definition algorithm for this family.Source: §5 · p. 18

6. Graphoid automata and effective boundaries

A shared edge operation yields polynomial-time graphoid recognition and compact boundary relations without a graph-width restriction. Boundary composition and comparison are effective, with quadratic encodings optimal for the stated families and worst-case exact relations.

6. Graphoid automata and effective boundaries

  • A common edge operation preserving transitions and boundary-language slices gives polynomial-time recognition without a width restriction and compact representations of boundary relations and accepting runs.For an ℓ-edge operation, a boundary of length k has a representation with O(k^(ℓ−1)) tuples and O(k^ℓ) bits; for Mal’tsev operations, O(k²) bits suffice for fixed D.Source: §6 · p. 18
  • Serial and parallel composition, boundary identification, and inclusion or equality comparison of finite graph relations are computable in polynomial time.A failed inclusion has a computable boundary counterexample; comparison is limited to finite graph relations of the same boundary type.Source: §6 · p. 19
  • For the prime-field family, canonical O(k²)-bit boundary codes compose by 2-SAT and Gaussian elimination, and quadratic size is optimal over the fixed alphabet Γp.An equivalent graph with O(k²) vertices and edges can be constructed over Γp; the original transition alphabet need not contain all these relations.Source: §6 · p. 19
  • Any injective binary encoding of all k-coordinate boundary relations for a fixed two-state Mal’tsev graphoid automaton requires Ω(k²) bits in the worst case.This is an information bound for exact relations, not a lower bound on the time for one recognition query or on encodings of a restricted family.Source: §6 · p. 20

7. A three-state separation from counting

A fixed three-state graphoid automaton has polynomial-time recognition but #P-complete exact counting. The separation arises because compact solution support does not generally capture extension multiplicities.

7. A three-state separation from counting

  • The Mal’tsev example preserves a five-element relation that is not a group coset and has first-coordinate fiber sizes 1, 2, and 2.Group-coset projections have uniform nonempty fiber sizes, unlike this relation.Source: §7 · pp. 20–21
  • A fixed three-state graphoid automaton has polynomial-time recognition but #P-complete counting of accepting vertex assignments, even with empty boundaries and only unary and ternary transitions.The hardness follows from the weighted Boolean counting dichotomy [DGJ09] through a count-preserving reduction.Source: §7 · p. 21
  • Replacing each weighted Boolean factor with a ternary constraint and a fresh variable preserves the integer count because fresh-variable extension choices are independent.The resulting unweighted instance has exactly Zf satisfying assignments.Source: §7 · p. 21
  • A compact support relation cannot generally be supplemented with one uniform multiplicity to recover all extension counts.The example realizes the gap between tractable recognition and hard exact counting in the graphoid model.Source: §7 · pp. 21–22

8. Concluding remarks

The paper’s compact boundary relations enable exact graphoid comparison and composition without a width assumption. It also identifies limits and open directions for the representation methods.

8. Concluding remarks

  • The automaton compilation extracts witnesses for compact-representation algorithms, after which arbitrary scopes are assembled through products and binary equalities.The resulting algorithm’s complexity is measured in the succinct input size.Source: §8 · p. 22
  • For the prime-field family, activity fibres and common-activity classes yield optimal quadratic-bit codes constructible from NFAs or arbitrary generators.The result is specific to this family; equally small effective encodings for arbitrary 3-edge algebras remain open.Source: §8 · p. 22
  • Graphoid boundary relations support exact finite-graph comparison and composition without a width assumption, with quadratic encoding bounds optimal in the worst case.Further restrictions on transition languages may allow faster updates or smaller representations.Source: §8 · p. 22
  • Beyond NFAs, compilation applies when a representation permits polynomial-time extraction of all fork witnesses and bounded-projection witnesses.This would extend the compilation theorem while leaving its algebraic part unchanged.Source: §8 · p. 22
Loading 2609.07891v1…