Re: Complexity of nested optionals

Jorge pointed out to me off list that I forgot to mention that the  
*data* complexity of nested optionals is logspace, which is quite  
normal in the DB world. (You can see that result in the paper where I  
pointed.)

OTOH, he said that they had a results (not included in the paper)  
that the complexity without nesting is NP-hard (not in NP). So, the  
difference between unnested and nested is probably moot.

He also said that he thought it was a worthwhile feature and could be  
made clear and correct, but that we had some decisions to make to  
nail it down. I'll keep up that conversation and report back to the  
working group, with an eye to getting a concrete proposal/presentation.

I'm not sure where this leaves my desire to reraise the issue. I  
think it's still new information, but that I need to do more  
investigation to determine what I think.

A methodological point: One thing I've been looking for as I work  
through the spec for holes, is things which we might add (usually  
clarifications) or subtract (typically features) with an eye to  
having a well, clear, consistent, intelligible specification in the  
time frame we have. The group has produced a language which is very  
expressive, with *interesting* expressivity, but expressivity that is  
not well understood, overall, at least by me, even in the simple  
entailment case. This worries me. That other people who have  
expertise in lots of areas that are foreign lands to me have had  
similar problems indicates that we have a significant challenge  
ahead. I would feel more comfortable with a smaller language this  
time around, with a working group submission for the extra  
functionality to give time for people to really pound on the  
interesting new features. It's unclear that this is a possibility or,  
overall, pragmatically desirable at this time.

This is just my methodology. The goal I have I think is shared by us  
all: A great spec and language by the end of the year. I hope we can  
make it.

Cheers,
Bijan.

Received on Wednesday, 6 September 2006 14:37:42 UTC