# migrating from traditional regexp cardinalities to shexj abstract syntax

From: Eric Prud'hommeaux <eric@w3.org>
Date: Thu, 3 Mar 2016 17:38:23 -0500
To: Iovka Boneva <iovka.boneva@univ-lille1.fr>

Message-ID: <20160303223820.GJ24478@w3.org>
```This email lays out the current cardinality tests in preparation for
adapting them to ShExJ's abstract syntax.

The triple expressions in shexj are one of:

triple constraint: predicate, inverse, value expression, cardinality
allOf: sequence of triple expressions, cardinality
someOf: sequence of triple expressions, cardinality
inclusion: ref to a shape's triple expression.

Currently the permissible cardinality on any of these is {0,∞}.  We
may restrict the permissible cardinalities on allOfs and containers of
allOfs in the future in order to simplify the

The ICDT paper gave the membership formula like:

Σ: edge labels
∆: set of symbols, possibly in Σ
ω: ∆→N: map symbols in ∆ to number of occurrences
e.g. w₀ = ⦃a, a, a, c, c⦄ means {a:3, c:2, *:0}

I(ε) = [0;∞]
I(a[n,m]) = [⌈ω(a)/m⌉;⌊ω(a)/n⌋]
0/∞ = 0
i/∞ = 1 for i ≥ 1
or: I(E₁ ∣ E₂) = I(E₁) ⊕ I(E₂)
m+∞ = ∞+m = ∞
and: I(E₁ ∥ E₂) = I(E₁) ∩ I(E₂)
[n₁;m₁]∩[n₂;m₂]=[max(n₁,n₂);min(m₁,m₂)]
⎧         [0;∞] if ω∆(E) = ε
I(E*) = ⎨         [1;∞] if ω∆(E) ≠ ε and I(E) ≠ 0
⎩             ∅ otherwise
⎧         [0;0] if ω∆(E) = ε
I(E⁺) = ⎨[1;max(I(E))⌉] if ω∆(E) ≠ ε and I(E) ≠ 0
⎩             ∅ otherwise
all ε∥E* are expressed as E⁺

Example:
I(a[n,m]) tests
<S> { :p . } / { <s> :p true }
∆={:p}, ω={:p→1}
I(:p[1,1]) = [⌈1/1⌉;⌊1/1⌋] = [1;1] pass
<S> { :p . } / { <s> :q true }
∆={:p}, ω={:p→0}
I(:p[1,1]) = [⌈0/1⌉;⌊0/1⌋] = [0;0] fail
?⎧<S> { :p .? } / { <s> :q true }
/⎨  ∆={:p}, ω={:p→0}
0⎩  I(:p[0,1]) = [⌈0/1⌉;⌊0/0⌋] = [0;1] pass (adding rule for 0/0=∞)
<S> { :p .{2} } / { <s> :p true }
∆={:p}, ω={:p→1}
I(:p[2,2]) = [⌈1/2⌉;⌊1/2⌋] = [1;0] fail
⅔⎧<S> { :p .{2,3} } / { <s> :p 1 }
/⎨  ∆={:p}, ω={:p→1}
1⎩  I(:p[2,3]) = [⌈1/3⌉;⌊1/2⌋] = [1;0] fail
⅔⎧<S> { :p .{2,3} } / { <s> :p 1,2 }
/⎨  ∆={:p}, ω={:p→2}
2⎩  I(:p[2,3]) = [⌈2/3⌉;⌊2/2⌋] = [1;1] pass
⅔⎧<S> { :p .{2,3} } / { <s> :p 1,2 }
/⎨  ∆={:p}, ω={:p→3}
3⎩  I(:p[2,3]) = [⌈3/3⌉;⌊3/2⌋] = [1;2] pass
⅔⎧<S> { :p .{2,3} } / { <s> :p 1,2,3,4 }
/⎨  ∆={:p}, ω={:p→4}
4⎩  I(:p[2,3]) = [⌈4/3⌉;⌊4/2⌋] = [2;2] fail
?/0 is really modeled as I(I(:p[1,1]) ∣ I(ε)) below

I(ε) tests
<S> { } / { <s> :p true }
∆={:p}, ω={}
I(ε) = [0;∞] pass
?⎧<S> { :p .? } / { <s> :q true }
/⎨  ∆={:p}, ω={:p→0}
0⎩  I(I(:p[1,1]) ∣ I(ε)) = I([0;0] ∣ [0;∞]) = [0;∞]
⅔⎧<S> { :p .{2,3} } / { <s> :p 1 }
/⎨  ∆={:p}, ω={:p→1}
1⎩  I(:p[2,3]) = [⌈1/3⌉;⌊1/2⌋] = [1;0] fail
⅔⎧<S> { :p .{2,3} } / { <s> :p 1 }
/⎨  ∆={:p}, ω={:p→1}
1⎩  I(I(I(:p[2,2]) ∥ I(I(:p[1,1]) ∣ I(ε)))) =
I(I([⌈1/2⌉;⌊1/2⌋] ∥ I([⌈0/1⌉;⌊0/1⌋] ∣ [0;∞]))) =
I(I([1;0] ∥ I([0;0] ∣ [0;∞]))) = I(I([1;0] ∥ [0;∞])) = I([1;0]) fail
⅔⎧<S> { :p .{2,3} } / { <s> :p 1,2 }
/⎨  ∆={:p}, ω={:p→2}
2⎩  I(I(I(:p[2,2]) ∥ I(I(:p[1,1]) ∣ I(ε)))) =
I(I([⌈2/2⌉;⌊2/2⌋] ∥ I([⌈0/1⌉;⌊0/1⌋] ∣ [0;∞]))) =
I(I([1;1] ∥ I([0;0] ∣ [0;∞]))) = I(I([1;1] ∥ [0;∞])) = I([1;1]) pass
⅔⎧<S> { :p .{2,3} } / { <s> :p 1,2,3 }
/⎨  ∆={:p}, ω={:p→3}
3⎩  I(I(I(:p[2,2]) ∥ I(I(:p[1,1]) ∣ I(ε)))) =
I(I([⌈3/2⌉;⌊3/2⌋] ∥ I([⌈0/1⌉;⌊0/1⌋] ∣ [0;∞]))) =
I(I([2;1] ∥ I([0;0] ∣ [0;∞]))) = I(I([2;1] ∥ [0;∞])) = I([2;1]) fail
-- overruns if <s> :p 3 assigned to [2,2] group
I(I([⌈2/2⌉;⌊2/2⌋] ∥ I([⌈1/1⌉;⌊1/1⌋] ∣ [0;∞]))) =
I(I([1;1] ∥ I([1;1] ∣ [0;∞]))) = I(I([1;1] ∥ [1;∞])) = I([1;1]) pass
-- accepts if <s> :p 3 assigned to I(I(:p[1,1]) ∣ I(ε))
⅔⎧<S> { :p .{2,3} } / { <s> :p 1,2,3,4 }
/⎨  ∆={:p}, ω={:p→3}
4⎩  I(I(I(:p[2,2]) ∥ I(I(:p[1,1]) ∣ I(ε)))) =
I(I([⌈4/2⌉;⌊4/2⌋] ∥ I([⌈0/1⌉;⌊0/1⌋] ∣ [0;∞]))) =
I(I([2;2] ∥ I([0;0] ∣ [0;∞]))) = I(I([2;2] ∥ [0;∞])) = I([2;2]) fail
-- overruns if <s> :p 4 assigned to [2,2] group
I(I([⌈3/2⌉;⌊3/2⌋] ∥ I([⌈1/1⌉;⌊1/1⌋] ∣ [0;∞]))) =
I(I([2;1] ∥ I([1;1] ∣ [0;∞]))) = I(I([2;1] ∥ [1;∞])) = I([2;1]) pass
-- overruns if <s> :p 4 assigned to I(I(:p[1,1]) ∣ I(ε))

⅔/1, ⅔/2, ⅔/3, ⅔/4 really modeled as I(:p[2,3]) above

I'd continue here but I need help understanding ω∆(E) ≠ ε and I(E) ≠ 0.

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