Research map / Learning theory and algorithms / Combinatorial and search optimization

Symbolic Functional Decomposition: A Reconfiguration Approach

AAAI 2025 · Learning theory and algorithms › Combinatorial and search optimization · approach: Logic and answer set programming theory · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Introduces a symbolic, automata-based framework (OBDDs, circuits, second-order finite automata) for functional decomposition and reconfiguration, showing fixed-parameter linear-time solvability in OBDD width, circuit size, and automaton size.

Problem

Decomposing a Boolean function f into a circuit combination g(f_1..f_k) of factor functions from a restricted class F, with optional constraints on intermediate functions (reconfiguration), in a symbolic (OBDD) representation.

Approach

Represents all intermediate functions symbolically as OBDDs of bounded width, encodes consistency with the circuit and the function class via regular languages over layer alphabets, and reduces decomposition to emptiness/membership in a regular language built from selectors, product and projection constructions.

Key results

• FunctionalReconfiguration solvable in time 2^{O(m·w^2 log w)}·|A|^k·|D|.
• FunctionalDecomposition solvable in time 2^{p^{O(2^m)}}·|A|^k·|D|, linear in |D| for fixed parameters.
• OBDD factorization solvable in time 2^{w^{O(2^k)}}·|D|.

Limitations

• Running time is doubly exponential-type in the circuit parameters (tower-like dependence on depth or circuit size).
• Dependence on automaton size is |A|^k, which grows quickly with the number of factors.
• Results are theoretical; no implementation or empirical evaluation is reported.

Experimental setup

Metrics: running time complexity (fixed-parameter linear time)

Builds on: second-order finite automata OBDD minimization DFA factorization

Closest papers by meaning

• Tensor Decomposition Meets Knowledge Compilation: A Study Comparing Tensor Trains with OBDDs (AAAI 2025 · similarity 0.83)
• Rethinking Circuit Completeness in Language Models: AND, OR, and ADDER Gates (NeurIPS 2025 · similarity 0.82)
• An And-Sum Circuit with Signed Edges That Is More Succinct than SDD (AAAI 2025 · similarity 0.82)
• Composing Biases by Using CP to Decompose Minimal Functional Dependencies for Acquiring Complex Formulae (AAAI 2024 · similarity 0.81)
• A Compositional Atlas for Algebraic Circuits (NeurIPS 2024 · similarity 0.81)
• Submodel Enumeration for CTL Is Hard (AAAI 2024 · similarity 0.81)