[XML-DEV Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message]

Re: Infinity

  • From: Tim Bray <tbray@textuality.com>
  • To: "C. M. Sperberg-McQueen" <cmsmcq@blackmesatech.com>
  • Date: Sun, 4 Mar 2018 21:36:36 -0800

Re:  Infinity

On Sun, Mar 4, 2018 at 6:36 PM, C. M. Sperberg-McQueen <cmsmcq@blackmesatech.com> wrote:

I would not like to have to write the test cases for checking that
a conforming processor either accepts a string consisting of an
infinite number of occurrences of the digit ‘0’ followed by the digit
‘5’, or else raises an out-of-resources error, and that the processor
rejects a string consisting of the letter ‘B’ preceded by an infinite
number of occurrences of the digit ‘0’.

​Actually, a state-machine based implementation can report with high confidence, and with strict bounds on memory usage, the presence, or failure to be present, of a '5' after any number of 0's. Infinity isn't a thing that exists in actual texts, so there's no need to state that any given string must be finite.  The closest you can get is say “any number of” and there you go.

BTW, this argument is not entirely theoretical.  Those who remember the Billion Laughs exploit may also remember that my first-gen "Lark" processor sailed through it, where by "sailed through" I mean "completed successfully after a few hours processing with no memory stress".   Because it had a state machine inside.  There is, practically, no limit on the length of the input such a processor can handle. So, if I claim it can manage infinite input, you can't prove me wrong. Fortunately, there's no such thing.

  • Follow-Ups:
    • Re: Infinity
      • From: "C. M. Sperberg-McQueen" <cmsmcq@blackmesatech.com>
    • RE: Infinity
      • From: "Tom Magliery" <tom.magliery@xmetal.com>
    • Re: Infinity
      • From: "Liam R. E. Quin" <liam@w3.org>
  • References:
    • Infinity
      • From: Michael Kay <mike@saxonica.com>
    • Re: Infinity
      • From: Elliotte Rusty Harold <elharo@ibiblio.org>
    • Re: Infinity
      • From: C. M. Sperberg-McQueen <cmsmcq@blackmesatech.com>

[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index]


Purchasing Stylus Studio from our online shop is Easy, Secure and Value Priced!

Buy Stylus Studio Now

Download The World's Best XML IDE!

Accelerate XML development with our award-winning XML IDE - Download a free trial today!

Don't miss another message! Subscribe to this list today.
First Name
Last Name
Subscribe in XML format
RSS 2.0
Atom 0.3

Stylus Studio has published XML-DEV in RSS and ATOM formats, enabling users to easily subcribe to the list from their preferred news reader application.

Stylus Studio Sponsored Links are added links designed to provide related and additional information to the visitors of this website. they were not included by the author in the initial post. To view the content without the Sponsor Links please click here.

Site Map | Privacy Policy | Terms of Use | Trademarks
Free Stylus Studio XML Training:
W3C Member
Stylus Studio® and DataDirect XQuery ™are products from DataDirect Technologies, is a registered trademark of Progress Software Corporation, in the U.S. and other countries. © 2004-2013 All Rights Reserved.