Re: question about ShEx

Le 18/12/2015 18:00, Peter F. Patel-Schneider a écrit :
> 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?

Indeed, very good question. And a technical answer.
There is an NP algorithm if we consider that the min and max bounds 
(1,2,3,4,6,7 in your example) are coded in unary (and not in binary) for 
determining the size of the schema.
 From a complexity point of view, it is equivalent to consider that
p@a [1,2]
is a syntactic shortcut for
p@a , p@a?
i.e. equivalent to "unfolding" the multiplicities.

Does it answer your question ?

As Eric explained, such cases are not supposed to occur very often.

Iovka

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


-- 
Iovka Boneva
Associate professor (MdC) Université de Lille
http://www.cristal.univ-lille.fr/~boneva/
+33 6 95 75 70 25

Received on Monday, 4 January 2016 12:16:50 UTC