• To: <xml-dev@l...>
• Subject: Undecidability of a Schematron problem
• From: "Robert C. Lyons" <boblyons@u...>
• Date: Tue, 26 Nov 2002 00:02:34 -0500
• Importance: Normal
• Reply-to: <boblyons@u...>

Recently, I was reading about the Post Correspondence Problem
(PCP), which is undecidable (i.e., unsolvable). I realized
that the undecidability of the PCP could be used to prove that
the following problem is undecidable:

     Given a Schematron schema, is there an XML document that
     conforms to this schema?

If you're interested in reading the proof and a description
of the PCP, then please visit
http://www.unidex.com/scp/index.htm.

Best regards,

Bob

<sig name    = 'Bob Lyons'
     title   = 'XML and Java Consultant'
     company = 'Unidex, Inc.'
     phone   = '+1-732-975-9877'
     email   = 'boblyons@u...'
     url     = 'http://www.unidex.com/'
     product = 'XML Convert: transforms flat files to XML and vice versa' />

• Prev by Date: RE: XML, Rich Internet Apps
• Next by Date: Re: What are the arguments *for* XHTML 2.0?
• Previous by thread: RE: RDBMS DB export
• Next by thread: RE: Acrobat SVG and Flash - comparisions? (was Re: What are the arguments *for* XHTML 2.0?)
• Index(es):
  • Date
  • Thread