{"id":2188,"date":"2012-09-30T07:23:44","date_gmt":"2012-09-30T07:23:44","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=2188"},"modified":"2013-03-08T05:48:11","modified_gmt":"2013-03-08T05:48:11","slug":"a-formal-proof-of-sasaki-murao-algorithm","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/a-formal-proof-of-sasaki-murao-algorithm\/","title":{"rendered":"Rese\u00f1a: A formal proof of Sasaki-Murao algorithm"},"content":{"rendered":"<p>La semana pasada se present\u00f3 en el <a href=\"http:\/\/www.map2012.uni-konstanz.de\">MAP2012<\/a> (<i>Mathematics, Algorithms and Proofs 2012<\/i>) un trabajo de aplicaci\u00f3n de bibliotecas de razonamiento formalizado en <a href=\"http:\/\/coq.inria.fr\">Coq<\/a> a la verificaci\u00f3n de un algoritmo de \u00e1lgebra computacional. <\/p>\n<p>El t\u00edtulo del trabajo es <a href=\"http:\/\/www.cse.chalmers.se\/~siles\/papers\/sasaki-murao.pdf\">A formal proof of Sasaki-Murao algorithm<\/a> y sus autores son <a href=\"http:\/\/www.cse.chalmers.se\/~coquand\">Tierry Coquand<\/a>, <a href=\"http:\/\/www.cse.chalmers.se\/~mortberg\">Anders M\u00f6rtberg<\/a> y <a href=\"http:\/\/www.cse.chalmers.se\/~siles\">Vincent Siles<\/a> (de la Univ. de Gotemburgo, Suecia).<\/p>\n<p>El resumen del trabajo es<\/p>\n<blockquote><p>\nThe Sasaki-Murao algorithm computes the determinant of any square matrix over a commutative ring in polynomial time. The algorithm itself can be written as a short and simple functional program, but its correctness involves non-trivial mathematics. We here represent this algorithm in Type Theory with a new correctness proof, using the Coq proof assistant and the SSReflect extension.\n<\/p><\/blockquote>\n<p>El c\u00f3digo Coq de la formalizaci\u00f3n se encuentra <a href=\"http:\/\/www.cse.chalmers.se\/~siles\/coq\/formalisation.html\">aqu\u00ed<\/a>  y las transparencias de la presentaci\u00f3n se encuentran <a href=\"http:\/\/www.cse.chalmers.se\/~mortberg\/talks\/anders-map2012.pdf\">aqu\u00ed<\/a>.<\/p>\n<p>Este trabajo es parte del proyecto <a href=\"http:\/\/wiki.portal.chalmers.se\/cse\/pmwiki.php\/ForMath\/ForMath\">ForMath: Formalisation of Mathematics<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>La semana pasada se present\u00f3 en el MAP2012 (Mathematics, Algorithms and Proofs 2012) un trabajo de aplicaci\u00f3n de bibliotecas de razonamiento formalizado en Coq a la verificaci\u00f3n de un algoritmo de \u00e1lgebra computacional. El t\u00edtulo del trabajo es A formal proof of Sasaki-Murao algorithm y sus autores son Tierry Coquand, Anders M\u00f6rtberg y Vincent Siles&#8230;<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[100],"tags":[45,273,285,275],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_likes_enabled":false,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/2188"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/comments?post=2188"}],"version-history":[{"count":3,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/2188\/revisions"}],"predecessor-version":[{"id":2773,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/2188\/revisions\/2773"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=2188"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=2188"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=2188"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}