Re: XSL Theory

On Fri, 10 Mar 2000 15:49:36 -0500, you wrote:

>Turing machines deal with infinite, input of all patterns. An XSL sheet with
>schema restricted input subset is a much different problem. Even thought the
>input can be infinite in size its pattern is severely restricted to being
>hierarchical and repetitive. For example you can't write a schema that
>describes the sequence of digits in PI.

I think you overestimate the degree of complexity required in a
transformation before undecidable propositions crop up. Consider a
system where:

1) both the domain (input) and range (output) consist solely of
integers

2) the only transformation operations available are addition and
multiplication

3) there exists a conditional construct of some kind (e.g., an IF
statement)

4) there exists a means of looping (e.g., recursion, a GOTO statement,
etc.)

Such a system (which is obviously a small subset of XSLT) has more
than enough complexity to contain undecidable propositions. It's
certainly true that undecidable propositions are unlikely to arise in
"normal" situations. Nevertheless, they are there, and that fact
_guarantees_ that you won't be able to write a theorem prover that
will cover all cases.

-Steve Schafer


 XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list