Re: question about ShEx

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
>>
>>
>>
>

Received on Friday, 18 December 2015 17:00:50 UTC