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 | Size | Format | |
---|---|---|---|---|
SEKI-MEMO-81-06_Beierle_SYNTHESIZING-MINIMAL-PROGRAMS-FROM-TRACES-OF-OBSERVABLE-BEHAVIOR.pdf | 9,98 MB | Adobe PDF | View/Open |
Items in SciDok are protected by copyright, with all rights reserved, unless otherwise indicated.