Inductive programming: Difference between revisions

Revision as of 03:42, 24 January 2014

Revision as of 07:15, 7 February 2014

Line 7:

Inductive programming incorporates all approaches which are concerned with learning programs or algorithms from incomplete ([[formal specification|formal]]) specifications. Possible inputs in an IP system are a set of training inputs and corresponding outputs or an output evaluation function, describing the desired behavior of the intended program, [[Tracing (software)|traces]] or action sequences which describe the process of calculating specific outputs, [[Constraint (mathematics)|constraints]] for the program to be induced concerning its time efficiency or its complexity, various kinds of background knowledge such as standard [[data type]]s, predefined functions to be used, program schemes or templates describing the data flow of the intended program, heuristics for guiding the search for a solution or other biases.

Output of an IP system is a program in some arbitrary programming or language containing conditionals and loop or recursive control structures, or any other kind of [[Turing completeness|Turing-complete]] [[Knowledge representation and reasoning|representation]] language.

In many applications the output program must be correct with respect to the examples and partial specification, and this leads to the consideration of inductive programming as a special area inside automatic programming or [[program synthesis]],<ref>{{cite journal|first1=A.W.|last1=Biermann|title=Automatic programming|editor1-first=S.C.|editor1-last=Shapiro|publisher=Wiley|journal=Encyclopedia of artificial intelligence|pages=18–35|year=1992}}</ref><ref>{{cite journal|first1=C.|last1=Rich|first2=R.C.|last2=Waters|title=Approaches to automatic programming|editor1-first=M.C.|editor1-last=Yovits|publisher=Academic Press|journal=Advances in computers|volume=37|year=1993}}</ref> usually opposed to 'deductive' program synthesis,<ref>{{cite book|editor1-first=M.L.|editor1-last=Lowry|editor1-first=R.D.|editor2-last=McCarthy|title=Automatic software design|year=1991}}</ref><ref>{{cite journal|first1=Z.|last1=Manna|first2=R.|last2=Waldinger|title=Fundamentals of deductive program synthesis|journal=IEEE Trans Softw Eng|volume=18(8)|pages=674–704|year=1992}}</ref><ref>{{cite journal|first1=P.|last1=Flener|title=Achievements and prospects of program synthesis|editor1-first=A.|editor1-last=Kakas|editor2-first=F.|editor2-last=Sadri|publisher=Springer|journal=Computational logic: logic programming and beyond; essays in honour of Robert A. Kowalski|volume=LNAI 2407|pages=310–346|year=2002}}</ref> where the specification is usually complete.