Till sidans topp

Sidansvarig: Webbredaktion
Sidan uppdaterades: 2012-09-11 15:12

Tipsa en vän
Utskriftsversion

A syntactical proof of th… - Göteborgs universitet Till startsida
Webbkarta
Till innehåll Läs mer om hur kakor används på gu.se

A syntactical proof of the marriage lemma

Artikel i vetenskaplig tidskrift
Författare Thierry Coquand
Publicerad i Theoretical Computer Science
Volym 290
Nummer/häfte 1
Sidor 1107-1113
ISSN 0304-3975
Publiceringsår 2003
Publicerad vid Institutionen för data- och informationsteknik, datavetenskap, programmeringslogik (GU)
Sidor 1107-1113
Språk en
Länkar dx.doi.org/10.1016/S0304-3975(02)00...
Ämneskategorier Datavetenskap (datalogi)

Sammanfattning

We give a proof of the classical Marriage Lemma (Amer. J. Math. 72 (1950) 214) using completeness of hyperresolution. This argument is purely syntactical, and extends directly to the infinite case. As an application we give a purely syntactical version of a proof that resolution is exponential on the pigeon-hole principle.

Sidansvarig: Webbredaktion|Sidan uppdaterades: 2012-09-11
Dela:

På Göteborgs universitet använder vi kakor (cookies) för att webbplatsen ska fungera på ett bra sätt för dig. Genom att surfa vidare godkänner du att vi använder kakor.  Vad är kakor?