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

Re: Decidability

• To: xml-dev@l...
• Subject: Re: Decidability
• From: Miles Sabin <miles@m...>
• Date: Wed, 13 Nov 2002 11:41:10 +0000
• In-reply-to: <3DD1C0FC.50306@p...>
• References: <BD2DBD26EE0BAA48B1A425C7BE7923002CFF9F@c...> <200211121549.05599.miles@m...> <3DD1C0FC.50306@p...>

Paul Prescod wrote,
> "As soon as arithmetics comes into play, tableau approaches
> become very diffcult to use. For example in a concept definition
> parents-of-many-boys = parent ^ has-son >=2 * has-daughter
> (parents-of-many-boys are parents having more than twice as many sons
> than daughters) the consistency problem amounts to checking whether x
> * 2y has a non-negative integer valued solution."
>
> How is this not an arithmetic constraint? Of course the technique
> isn't "general", as in covering all arithmetic. But it is
> nevertheless designed to allow arithmetic constraints.

It is an arithmetic constraint: of a very restricted form.

> My claim is that there is a _SUBSET_ of arithmetic which is
> decidable.

Of _course_ there are subsets of arithmetic which are decidable. And 
there are subsets of XSLT and Java which are decidable too.

In all cases the questions are: Is the subset large enough to be useful 
in practice? And is the decidability game worth the candle anyway?

The first question relates to expressive power: make the restrictions 
too severe and it can be impossible or very difficult to say the things 
you want to say.

The second points to the fact that the 'finite' in 'finite decision 
procedure' can be very, very, very big indeed. Who cares if a decision 
procedure will terminate in finite time if we'll all be long dead 
before it's done? Practically speaking, the system might as well be 
undecidable: decidability != feasibility.

> If you want to continue the discussion I suggest we take it to
> www-rdf-interest where logic experts will be able to weigh in (unless
> you claim to be an expert).

Be my guest ...

Cheers,


Miles

• Follow-Ups:
  • Re: Decidability
    • From: Paul Prescod <paul@p...>

• References:
  • RE: XML/RDF
    • From: Micah Dubinko <MDubinko@c...>
  • Re: equivalentTo vs. XSLT
    • From: Miles Sabin <miles@m...>
  • Decidability
    • From: Paul Prescod <paul@p...>

• Prev by Date: Re: Does WTSIWYG make simplicity moot? (was Re: dtds, schemas, xhtml, and multimedia technologies)
• Next by Date: Re: Tablet PC ink is XML
• Previous by thread: Decidability
• Next by thread: Re: Decidability
• Index(es):
  • Date
  • Thread