A New Kind of Science: The NKS Forum : Powered by vBulletin version 2.3.0 A New Kind of Science: The NKS Forum > News & Announcements > Post Correspondance Problem site
  Last Thread   Next Thread
Thread Post New Thread    Post A Reply
Jason Cawley
Wolfram Science Group
Phoenix, AZ USA

Registered: Aug 2003
Posts: 712

Post Correspondance Problem site

Emile Post's classic correspondance problem asks whether ordered pairs (or longer sets) of strings can be concatenated to yield the same string, a problem of satisfying a simple constraint. For a trivial example, if you have x1 = {ABB, A} and x2 = {A, BBA} you can take x1x2 and get {ABBA, ABBA}.

The question for any initial set of strings it whether you can bring the sequences into "correspondance" (equal strings on removal of parenthesis) by putting together any of the set you have, in any order. You can vary the number of allowed symbols, the number of parallel strings to match up, and the maximum length of the initial strings, as parameters of the problem.

The NKS book discusses these as "correspondance systems", in the main text on pages 757 and thereabouts, and at length in one of the notes on page 1139.

A graduate student in Alberta has a nice site about the PCP problem that I thought might be of interest to forum members, here -


I hope this is interesting.

Report this post to a moderator | IP: Logged

Old Post 01-03-2005 04:23 PM
Jason Cawley is offline Click Here to See the Profile for Jason Cawley Click here to Send Jason Cawley a Private Message Edit/Delete Message Reply w/Quote
Post New Thread    Post A Reply
  Last Thread   Next Thread
Show Printable Version | Email this Page | Subscribe to this Thread


wolframscience.com  |  wolfram atlas  |  NKS online  |  Wolfram|Alpha  |  Wolfram Science Summer School  |  web resources  |  contact us

Forum Sponsored by Wolfram Research

© 2004-16 Wolfram Research, Inc. | Powered by vBulletin 2.3.0 © 2000-2002 Jelsoft Enterprises, Ltd. | Disclaimer | Archives