Thu, 16 Jul 2009 22:26:00 -0700 (PDT)

Related articles |
---|

on definition of soundness and completeness bxin@acm.org (Bin Xin) (2009-06-23) |

Re: on definition of soundness and completeness gene.ressler@gmail.com (Gene) (2009-07-05) |

Re: on definition of soundness and completeness gopi.onthemove@gmail.com (gopi) (2009-07-16) |

From: | gopi <gopi.onthemove@gmail.com> |

Newsgroups: | comp.compilers |

Date: | Thu, 16 Jul 2009 22:26:00 -0700 (PDT) |

Organization: | Compilers Central |

References: | 09-06-078 |

Keywords: | analysis, theory |

Posted-Date: | 17 Jul 2009 14:41:45 EDT |

*> Soundness property (of F) can be claimed when: F \vdash P \implies I*

*> \models P.*

*>*

*> and conversely,*

*>*

*> Completeness property (of F) can be claimed when: I \models P \implies*

*> F \vdash*

This agrees with the concepts of soundness and completeness I am

familiar with. Going back to basics, When the formal system is an

algorithm, this translates to something like this in simple english:

An algorithm is said to be sound if for every problem P, every

solution the algorithm finds is a correct solution.

An algorithm is said to be complete if for every problem P, if a

solution exists, the algorithm will find it (in finite time).

These are fairly important properties (for example in the AI

Planning / Planner space), and I will be surprised if any one gets

them wrong !

Gopi

---

Sankhya Technologies Private Limited

http://www.sankhya.com

Mobile: +91 94408 78042

US (Voice-Mail)

(408) 556-9757

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.