| |
Master thesis: Solving and Creating Difficult Instances of Post's
Correspondence Problem
Presentation slides
-
As a part of CMPUT657 Heuristic Search course, I gave a presentation for Richard Lorentz's paper titled
"Creating Difficult Instances of the Post Correspondence Problem" on March 20, 2001. This is the revised version
of the slides.
-
The following is the slides I used to give a presentation on "Tackling Post's Correspondence Problem"
in the regular GAMES group meeting at the University of Alberta on July 31,2001.
PCP instances
- The 23 hard instances in the records: here
- The 200 hard instances used in the experiments of my thesis: here
- The 3,170 instances in PCP[3,4] unsolved by my PCP solver: here
- The 13,923 instances in PCP[4,3] unsolved by my PCP solver: here
Links
This webpage was created on April 29, 2001
Last modified on March 30, 2002 by Ling Zhao
|
|
|
Introduction
What's PCP?
PCP's theoretical place
Solving hard PCP instances
Masks
Bidirectional probing
Heuristic pruning
Cache scheme
Depth-first iterative deepening
Tail recursion removal
Instances having no solutions
Filters
Masks
Exclusion method
Pattern method
Hard instances list
The known hard instances
Data of the solutions
Documents
Presentation slides
PCP Instances
Links
Next step
Instances unsolved
Pattern method implementation
Where are the applications?
Some conjectures
Contact
Who am I?
Why am I so interested?
How to contact?
|
