Please use this identifier to cite or link to this item: doi:10.22028/D291-37900
Title: Synthesizing minimal programs from traces of observable behaviour
Author(s): Beierle, Christoph
Language: English
Year of Publication: 1981
Place of publication: Bonn
Free key words: automatic program synthesis
example computation
identification in the limit
NP-completeness
observable behaviour
store traces
program synthesis problem
program synthesis algorithm
DDC notations: 004 Computer science, internet
Publikation type: Report
Abstract: Automatic synthesis of non-recursive flowchart programs from traces of observable behaviour is investigated. Our program synthesis algorithm described here can be applied to sets of sequences of stores yielding minimal programs being capable of reproducing these sequences. An efficient decision procedure for solvability of program synthesis problems is presented. An extension of PA admits four different types of input traces. For all four types program synthesis remains NP-complete even under various constraints.
Link to this record: urn:nbn:de:bsz:291--ds-379009
hdl:20.500.11880/35495
http://dx.doi.org/10.22028/D291-37900
Series name: Memo SEKI : SEKI-Projekt / Deutsches Forschungszentrum für Künstliche Intelligenz, DFKI
Series volume: 81,6
Date of registration: 23-Mar-2023
Faculty: SE - Sonstige Einrichtungen
Department: SE - DFKI Deutsches Forschungszentrum für Künstliche Intelligenz
Professorship: SE - Sonstige
Collections:SciDok - Der Wissenschaftsserver der Universität des Saarlandes

Files for this record:
File Description SizeFormat 
SEKI-MEMO-81-06_Beierle_SYNTHESIZING-MINIMAL-PROGRAMS-FROM-TRACES-OF-OBSERVABLE-BEHAVIOR.pdf9,98 MBAdobe PDFView/Open


Items in SciDok are protected by copyright, with all rights reserved, unless otherwise indicated.