Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Structural_induction> ?p ?o. }
Showing items 1 to 40 of
40
with 100 items per page.
- Structural_induction abstract "Structural induction is a proof method that is used in mathematical logic (e.g., in the proof of Łoś' theorem), computer science, graph theory, and some other mathematical fields. It is a generalization of mathematical induction over natural numbers, and can be further generalized to arbitrary Noetherian induction. Structural recursion is a recursion method bearing the same relationship to structural induction as ordinary recursion bears to ordinary mathematical induction.Structural induction is used to prove that some proposition P(x) holds for all x of some sort of recursively defined structure such as lists or trees. A well-founded partial order is defined on the structures ("sublist" for lists and "subtree" for trees). The structural induction proof is a proof that the proposition holds for all the minimal structures, and that if it holds for the immediate substructures of a certain structure S, then it must hold for S also. (Formally speaking, this then satisfies the premises of an axiom of well-founded induction, which asserts that these two conditions are sufficient for the proposition to hold for all x.)A structurally recursive function uses the same idea to define a recursive function: "base cases" handle each minimal structure and a rule for recursion. Structural recursion is usually proved correct by structural induction; in particularly easy cases, the inductive step is often left out. The length and ++ functions in the example below are structurally recursive.For example, if the structures are lists, one usually introduces the partial order '<' in which L < M whenever list L is the tail of list M. Under this ordering, the empty list [] is the unique minimal element. A structural induction proof of some proposition P(l) then consists of two parts: A proof that P([]) is true, and a proof that if P(L) is true for some list L, and if L is the tail of list M, then P(M) must also be true.Eventually, there may exist more than one base case, and/or more than one inductive case, depending on how the function or structure was constructed. In those cases, a structural induction proof of some proposition P(l) then consists of: A) a proof that P(BC) is true for each base case BC, and B): a proof that if P(I) is true for some instance I, and M can be obtained from I by applying any one recursive rule once, then P(M) must also be true.".
- Structural_induction thumbnail Waldburg_Ahnentafel.jpg?width=300.
- Structural_induction wikiPageExternalLink 6649.
- Structural_induction wikiPageID "211399".
- Structural_induction wikiPageRevisionID "606042225".
- Structural_induction hasPhotoCollection Structural_induction.
- Structural_induction subject Category:Graph_theory.
- Structural_induction subject Category:Logic_in_computer_science.
- Structural_induction subject Category:Mathematical_induction.
- Structural_induction subject Category:Mathematical_logic.
- Structural_induction subject Category:Mathematical_proofs.
- Structural_induction subject Category:Wellfoundedness.
- Structural_induction type Abstraction100002137.
- Structural_induction type Argument106648724.
- Structural_induction type Communication100033020.
- Structural_induction type Evidence106643408.
- Structural_induction type Indication106797169.
- Structural_induction type MathematicalProof106647864.
- Structural_induction type MathematicalProofs.
- Structural_induction type Proof106647614.
- Structural_induction comment "Structural induction is a proof method that is used in mathematical logic (e.g., in the proof of Łoś' theorem), computer science, graph theory, and some other mathematical fields. It is a generalization of mathematical induction over natural numbers, and can be further generalized to arbitrary Noetherian induction.".
- Structural_induction label "Inducción estructural".
- Structural_induction label "Indukcja strukturalna".
- Structural_induction label "Indução estrutural".
- Structural_induction label "Structural induction".
- Structural_induction label "Strukturelle Induktion".
- Structural_induction label "Структурная индукция".
- Structural_induction label "结构归纳法".
- Structural_induction sameAs Strukturelle_Induktion.
- Structural_induction sameAs Inducción_estructural.
- Structural_induction sameAs Structurele_inductie.
- Structural_induction sameAs Indukcja_strukturalna.
- Structural_induction sameAs Indução_estrutural.
- Structural_induction sameAs m.01d_g5.
- Structural_induction sameAs Q1932759.
- Structural_induction sameAs Q1932759.
- Structural_induction sameAs Structural_induction.
- Structural_induction wasDerivedFrom Structural_induction?oldid=606042225.
- Structural_induction depiction Waldburg_Ahnentafel.jpg.
- Structural_induction isPrimaryTopicOf Structural_induction.