Peter's question about ShEx complexity

PFPS is asking about NP-completeness. I'm completely unqualified to
answer. Could you respond to this message? I expect that stating the
complexity with and without an included middle is interesting here.

https://lists.w3.org/Archives/Public/public-data-shapes-wg/2015Dec/thread#msg52

* Peter F. Patel-Schneider <pfpschneider@gmail.com> [2015-12-18 09:00-0800]
> With this construct I'm having some difficulty determining whether ShEx
> validation is in NP.  It seems to me that the outer numbers multiply the
> effort required to make the inner partitions, leading to an exponential number
> of choices.   Maybe there is some way to do this bottom up, but it certainly
> doesn't seem obvious to me.
> 
> Is there an NP algorithm for ShEx validation with this feature?
> 
> peter
> 
> 
> On 12/18/2015 01:12 AM, Eric Prud'hommeaux wrote:
> > * Peter F. Patel-Schneider <pfpschneider@gmail.com> [2015-12-17 22:20-0800]
> >> It appears to me that ShEx allows embeddings of cardinalities, as in
> >>
> >> twofoureight {
> >>   { { p @ a [2,2] } [2,2] } [2,2]
> >>  }
> >>
> >> or
> >>
> >> lots {
> >>   { p @a [2,4], p @b [1,3] } [6,7]
> >> }
> >>
> >> is this correct?
> > 
> > In principle, yes, but apart from optional groups, it's rare that one
> > wants to make sure that there are as many a's as there are b's. Optional
> > is quite reasonable, e.g.
> > 
> >   <X> {
> >     :submitter @<UserShape>, :submissionDate xsd:dateTime,
> >     (:resolvedBy @<HackerShape>, :resolutionDate xsd:dateTime)?
> >   }
> > 
> > The other place this frequently comes up is in repetitions of choices:
> > 
> >   <Y> { (:observation .|:analysis .|:diagnosis .)+ }
> > 
> > which can be compiled to
> > 
> >   <Y> {
> >     (:observation .|:analysis .|:diagnosis .),
> >     :observation .*,
> >     :analysis .*,
> >     :diagnosis .*
> >   }
> > 
> > with either a partion or a greedy semantics.
> > 
> > 
> >> peter
> >>
> >>
> >>
> > 

-- 
-ericP

office: +1.617.599.3509
mobile: +33.6.80.80.35.59

(eric@w3.org)
Feel free to forward this message to any list for any purpose other than
email address distribution.

There are subtle nuances encoded in font variation and clever layout
which can only be seen by printing this message on high-clay paper.

Received on Monday, 21 December 2015 16:03:50 UTC