Betydelsen av sökproblem inom datavetenskapen har lett till många framsteg inom sökteknik. Teknik som utvecklats för ett visst sökproblem är dock inte alltid lätt att tillämpa på andra problem. I denna uppsats tar vi en abstrakt syn på sökproblem genom att beskriva sökprocedurer som särskilda typer av bevis i typteori, med hjälp av proofs-as-program paradigm. Vi undersöker på djupet en stor familj av sökproblem och presenterar ett konstruktivt bevis som leder till ett korrekt sökförfarande för dessa problem. Vi visar hur klassisk logik kan beskriva en typisk användning av icke-lokal kontroll i sökalgoritmen som resulterar när vi utvidgar detta bevis till att omfatta intelligenta backtracking tekniker såsom "con ict-directed backjumping" (CBJ). Vi visar hur man undviker de flesta av de problem som traditionellt förknippas med att extrahera program från formella bevis, genom en Nuprl formalisering som leder till ettrunnable Scheme program. Vi använder detta program för att genomföra CBJ och visa dess värde för Hamiltonian krets problem. Vårt arbete är viktigt för att demonstrera en viktig tillämpning av proofs-as-program paradigm i praktiken, och för att visa den sanna generaliteten av konct-directed backjumping och den lätthet med vilken det nu kan tillämpas på nya problem. Författare namnges i alfabetisk ordning även om Judith Underwood är huvudförfattare. Vi tackar ledamöterna i APES för deras hjälp. Ian Gent och Judith Underwood tackar särskilt Denis Magnus för hans ovärderliga bidrag till deras forskning.
Caldwell, Gent och Underwood har övervägt programextraktion från klassiska bevis i bevisassistenten NuPrl REF.
Search algorithms in type theory
{'venue': 'Theor. Comput. Sci.', 'journal': None, 'mag_field_of_study': ['Computer Science']}