Zum Inhalt springen

Nur-Lesen-Fassung: Das Forschungsinformationssystem (FIS) ist aus Sicherheitsgründen vorübergehend durch diese Nur-Lesen-Fassung ersetzt. Alle öffentlichen Inhalte und Volltexte sind weiterhin abrufbar; Anmeldung, Bearbeitung, Einreichung und Statistiken stehen nicht zur Verfügung. Bei Fragen: fis@uni-bamberg.de

Start › Publikationen › A Divide, Align and Conquer Strategy For Program Synthesis

Publikation

A Divide, Align and Conquer Strategy For Program Synthesis

Witt, Jonas; Dumančić, Sebastijan; Guns, Tias; u. a. (2025): A Divide, Align and Conquer Strategy For Program Synthesis, in: Journal of artificial intelligence research : JAIR ; an international electronic and print journal, AI Access Found., Jg. 82, S. 1961–1997, doi: 10.1613/jair.1.16847.

Details

Fakultät/Lehrstuhl
Autorin(nen)/Autor(en)
Witt, Jonas
Dumančić, Sebastijan
Guns, Tias
Von
... ; Dumančić, Sebastijan; ...
Titel der Zeitschrift
Journal of artificial intelligence research : JAIR ; an international electronic and print journal
ISSN
1943-5037
1076-9757
Verlagsangabe
AI Access Found.
Erscheinungsjahr
2025
Jahrgang
82
Sprache(n)
Englisch
DOI
URL
Abstract

A major bottleneck in search-based program synthesis, which learns programs from input/output examples, is the synthesis of large programs. As the size of the target program increases, so does the search depth, which leads to an exponentially growing number of candidate programs. Humans mitigate the combinatorial explosion that arises from deep program search: they build complex programs from smaller parts. We introduce a new strategy for program synthesis called Divide, Align & Conquer (DA&C) that exploits the compositionality of real-world domains to guide the synthesis towards useful subprograms. Divide decomposes each example using a segmentation procedure that is synthesized as part of the learning problem. Align matches the components in the decomposed input/output examples to steer the search toward combinations that lead to the synthesis of useful subprograms, and Conquer then solves a standalone synthesis problem on each pair of aligned input/output components. We show how replacing a deep program search with a linear number of much smaller synthesis tasks leads us to efficiently discover useful subprograms that are then combined into a solution program. Our agent outperforms current Inductive Logic Programming (ILP) methods on string transformation tasks even with minimal knowledge priors. Unlike existing methods, the predictive accuracy of our agent monotonically increases for additional examples. It approximates an average time complexity of O(m) in the size m of subprograms for highly structured and, hence, decomposable domains such as strings. Finally, we demonstrate the scalability of our technique on highdimensional abstract visual reasoning tasks from the Abstract Reasoning Corpus (ARC) for which ILP methods were previously infeasible. We are competitive with state-of-the-art agents outside of ILP, despite generating only 0.2% as many candidate programs from a knowledge prior of only 11 generic geometric primitives.

Freie Schlagwort(e)
program synthesis
cognitive modeling
inductive logic programming
DDC-Klassifikation
150 Psychologie
RVK-Klassifikation
CM 3000
Dokumenttyp
Artikel in einer Zeitschrift / Postprint
URI
Datum der Freischaltung
14.08.2026

Permalink: https://fis.uni-bamberg.de/handle/uniba/116834 · Daten als JSON · Zitieren: BibTeX · RIS

Datenstand: 16.11.2026

Eingeschränkter Lesezugriff: Anmeldung, Bearbeitung und Einreichung sind vorübergehend deaktiviert.